
先证明几个简单的结论吧
1. 若 n 为质数,那么结论成立
证明: n | (a^n - b^n) => a^n - b^n = 0 (mod n)
因为 n 是质数,由费马小定理有 a^n = a (mod n) , b^n = b (mod n)
于是 a^n - b^n = a - b = 0 (mod n)
所以可以设 a - b = kn
所以 a = b+kn
现在考虑 (a^n - b^n)/(a-b) = a^(n-1)+a^(n-2) * b + ... + b^(n-1)
代入 a = b+kn
得到 右边 = (b+kn)^(n-1)+(b+kn)^(n-2) * b + ... + b^(n-1)
对 n 取模得到
b^(n-1) + b^(n-2)*b + ... + b^(n-1) * b^0 = n*b^(n-1) = 0 (mod n),被 n 整除
2. 若 n 为合数,且 p 是 n 的素因子,那么有 p 整除 (a^n - b^n)/(a-b)
证明: 记 n = p*t,因为 n | a^n - b^n,所以 p | a^n - b^n => a^n - b^n = 0 (mod p)
由费马小定理有 a^p = a (mod p) , b^p = b (mod p)
所以 a^n - b^n = a^(pt) - b^(pt) = a^t - b^t = 0 (mod p)
可设 a^t - b^t = m*p
现在考虑 a^n - b^n = [a^t]^p - [b^t]^p = (a^t - b^t)[(a^t)^(p-1)+(a^t)^(p-2) * (b^t) + ... + (b^t)^(p-1) ]
所以 (a^n - b^n)/(a-b) = (a^t)^(p-1)+(a^t)^(p-2) * (b^t) + ... + (b^t)^(p-1)
代入 a^t =b^t + m*p
得到 右边 = (b^t+mp)^(p-1)+(b^t+mp)^(p-2) * (b^t) + ... + (b^t)^(p-1)
对 p 取模得到 右边 = p*(b^t)^(p-1) = 0 (mod p),被 p 整除
3. 若 n 为合数,且 p1, p2, ..., pk 是 n 的不同素因子,那么有 p1*p2*...*pk 整除 (a^n - b^n)/(a-b)
证明:根据结论2,显然。
4. n | (a^n - b^n)/(a-b)
证明: 挖坑待续......我要先去给老板搬砖了
=============回来填坑==========
4. 若 n 为合数,且 n 的唯一分解为 p1^(α_1)*p2^(α_2)* ... *pk^(α_k),那么 对任意1 <= i <= k有,pi^(α_i) 整除 (a^n - b^n)/(a-b)
证明:不失一般性设 a和b都不被pi^α_i整除。 否则假设a被pi^α_i整除,由pi^α_i整除a^n - b^n可得b被pi^α_i整除。于是要考察的式子都含有这个因子,命题显然成立。
首先由欧拉定理得到
a^phi(pi^α_i) =1(mod pi^α_i)
也即 a^(pi^α_i - pi^(α_i-1) ) = 1(mod pi^α_i)
对上面这个式子简单变形可以得到两个有用的等式
a^n = a^(n/pi) (mod pi^α_i) (1)
a^(n-n/pi) = a^(n/pi^α_i) (mod pi^α_i) (2)
由(1)得到
a^(n/pi) = b^(n/pi) (mod pi^α_i) (3)
由(2)(3)及题设得到
a^(n-n/pi) = b^(n-n/pi) (mod pi^α_i) (4)
也就是
a^(n/pi^α_i) = b^(n/pi^α_i) (mod pi^α_i) (5)
(为什么(4)的指数可以用减法?因为a,b和模数互质,根据裴蜀定理使得求逆元的不定方程有解)
接下来
a^n-b^n = (a^(n/pi^α_i))^(pi^α_i) - (b^(n/pi^α_i))^(pi^α_i)
= [a^(n/pi^α_i) - b^(n/pi^α_i)]
[a^(n/pi^α_i))^(pi^α_i-1) + ... + b^(n/pi^α_i))^(pi^α_i-1)] (mod pi^α_i)
套用(5)的结论整理要考察的那个式子,得到上式等于
[a^(n/pi^α_i) - b^(n/pi^α_i)] *
[a^(n/pi^α_i))*(pi^α_i)] = 0 (mod pi^α_i)
于是上式的第二个因式被 pi^α_i 整除
5. n | (a^n - b^n)/(a-b)
证明: 由定理4以及每个pi^α_i两两互质立刻得知
