先证明几个简单的结论吧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两两互质立刻得知
温馨提示：答案为网友推荐，仅供参考