证明对任意质数P,整数A,B,有(A + B)^P mod P = A^P + B^P
RT
[解决办法]
很简单的多项式展开。
(A+B)^P = A^P + C(P,1) * A * (B^(P-1)) + C(P,2) * (A^2) * (B^(P-2)) + ... + C(P,P-1) * (A^(P-1)) * B + B^P
其中 P | C(P,i), i ∈[1,P-1]，这是因为
C(P,i) = P*(P-1)*...*(P-i+1) / (1*2*...*i)
分子一定含有P，而分母一定不含有P，并且P是质数，所以它可以整除P。
所以(A + B)^P mod P = （ A^P + B^P ） mod P
[解决办法]
C(p,k) = p!/(k!*(p-k)!);
当k!*(p-k)!)=1时, p=2,k=1, 显然有 p|C(p,k)
当k!*(p-k)!)>1时, C(p,k) = p * (p-1)!/(k!*(p-k)!) 为整数
由于P为质数故 (k!*(p-k)!)|p 不成立, 故(k!*(p-k)!)|(p-1)!
综上 p | C(p,k);
所以 (A + B)^P % P =
(A^P + C(P,1) * A * (B^(P-1)) + ... + C(P,P-1) * (A^(P-1)) * B + B^P) % P
= (A^P + B^P) % P;
