当前位置：首页 → 问答吧 → 证明对任意质数P,整数A,B,有(A + B)^P mod P = A^P + B^P

证明对任意质数P,整数A,B,有(A + B)^P mod P = A^P + B^P

时间：2011-11-14

来源：互联网

作者: lerry1024 发布时间: 2011-11-14

很简单的多项式展开。

(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

作者: gogdizzy 发布时间: 2011-11-14

引用 1 楼 gogdizzy 的回复:

很简单的多项式展开。

(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) ……

也就是LZ的题目写得不对喽

作者: mougaidong 发布时间: 2011-11-14

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;

作者: keeya0416 发布时间: 2011-11-14

呀没看到1楼已经回答了
楼主请无视我的回答吧
1楼正解

作者: keeya0416 发布时间: 2011-11-14