Posted on 2008-01-30 01:13
魔のkyo 阅读(2449)
评论(1) 编辑 收藏 引用
费马小定理：
a^(p-1) ≡ 1 (mod p) ，gcd(a,p)=1
证明：
构造模p的完全剩余系P = {0，1, 2, … ,p-1}，
因为gcd(a, p) = 1，所以A= {0*a, 1*a, 2*a, … ,(p-1)*a}也是模p的一个完全剩余系。
就是说P和A在模p意义下是相等的。
因为0 ≡ 0a (mod p)，所以 P-{0} 与 A-{0*a}在模p意义下是相等的。
记P'=P-{0},A'=A-{0*a}
令W = πP' = 1 * 2 * 3 * 4 … * (p-1)，Y = πA' = a * 2a *3a * 4a * …(p-1)a = W*a^(p-1) //π表示连乘积
有，W ≡ Y (mod p)
即，W ≡ W*a^(p-1) (mod p)
又因为，(W, p) = 1
则有，1 ≡ a^(p-1) (mod p)