若n整除a的n次方减去b的n次方,那么n整除后者除以a-b的商?

若n整除a的n次方减去b的n次方,那么n整除后者除以a-b的商?

先证明几个简单的结论吧

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两两互质立刻得知