posts - 206, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

费马小定理的证明

Posted on 2008-01-30 01:13 魔のkyo 阅读(2316) 评论(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)


Feedback

# re: 费马小定理的证明  回复  更多评论   

2008-06-03 22:45 by 魔のkyo
补充:关于欧拉定理的证明,只需要补充缩系的概念,证明方法类似。
只有注册用户登录后才能发表评论。