费马定理
费马定理
若p是素数，a是正整数且不能被p整除，则：
a^(p-1)≡1(mod p)
证明：
- 令X为小于p的正整数集合：X={1, 2, ..., p-1}
- 令Y为a乘以X内的所有元素对p取模：Y={a mod p, 2a mod p, ..., (p-1)a mod p}
- 证明Y中元素互不相等：假设Y中有ia≡ja(mod p)，由于a与p互素，因此i≡j(mod p)，则i=j，矛盾
- 由于Y中元素互不相等，则X与Y两个集合的内容相同
- 因此a*2a*...*(p-1)a≡1*2*...*(p-1) (mod p)
- 即(p-1)! * a^(p-1) ≡ (p-1)! (mod p)
- 由于(p-1)!与p互素，则a^(p-1)≡1(mod p)
欧拉定理
欧拉函数φ(n)：小于n的整数中与n互素的数的个数 性质：设m，n是两个素数，则
φ(m*n)=φ(m)*φ(n)
欧拉定理：设a，m互素，则
a^φ(m)≡1(mod m)
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023 年 06 月，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录