先證明幾個簡單的結論吧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兩兩互質立刻得知
先證明幾個簡單的結論吧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兩兩互質立刻得知