费马-欧拉定理证明

费马小定理： $a^{p-1} equiv 1 mod p$

引理：若集合{f}={f1,f2,f3...fm-1}中元素对m取模的结果遍历了（1~m-1）所有值，且k与m互质，则{f1k,f2k,f3k...}对m取模的结果同样遍历（1~m-1）所有值

（或者用偏理论的语言描述：如果{a1,a2,a3...am}是m的一个完全剩余系，且k与m互质，则{a1k,a2k...amk}也是m的一个完全剩余系）

证明：

应用反证法，假设:

$fp*kequiv fq*k (mod m)$

于是：

设 $fp*k=a1*m+b1$ ①

$fq*k=a2*m+b1$ ②

②-①，得： $(fq-fp)*k =(a2-a1)*m$

即 $(fq-fp)*k$ 与m不互质

又∵k与m互质

∴ $(fq-fp)$ 与m不互质

不妨设 $(fq-fp)=cm$

于是 $fq=fp+cm$

两侧对m取模，得：

$fqequiv fp (mod m)$

这与{f}是m的一个完全剩余系矛盾

∴假设不成立，原命题得证

即：{f*k}也是m得一个完全剩余系

证明：

构造序列{bn}，令bi=i·a（i<=p-1），则:

$prod bi=(prod i )*a^{n-1}$

又∵ a,p互质，由引理：

∴ $prod i mod pequiv prod (i*a) mod p$

又∵ $prod i*amod p=prod i mod p*a^{p-1}mod p$

∴ $a^{n-1} equiv 1 mod p$

证毕

应用相同方法，可以证明欧拉定理： $a^{phi (p)}equiv 1 mod p$

证明方法完全一致