费马定理

费马定理

若p是素数，a是正整数且不能被p整除，则：

a^(p-1)≡1(mod p)

证明：

1. 令X为小于p的正整数集合：X={1, 2, ..., p-1}
2. 令Y为a乘以X内的所有元素对p取模：Y={a mod p, 2a mod p, ..., (p-1)a mod p}
3. 证明Y中元素互不相等：假设Y中有ia≡ja(mod p)，由于a与p互素，因此i≡j(mod p)，则i=j，矛盾
4. 由于Y中元素互不相等，则X与Y两个集合的内容相同
5. 因此a*2a*...*(p-1)a≡1*2*...*(p-1) (mod p)
6. 即(p-1)! * a^(p-1) ≡ (p-1)! (mod p)
7. 由于(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)