本证明参考了李煜东老师《算法竞赛进阶指南》.
我们首先证明欧拉定理,然后推导出费马小定理.
欧拉定理:若(gcd(a,n)=1,a,nin mathbb{Z}),则(a^{phi(n)}equiv 1 pmod{n}).其中(phi(n))为欧拉函数.
设n的简化剩余系为({overline{d_1},overline{d_2},dots,overline{d_{phi(n)}}}).
由定义,设(d_1,d_2,dots,d_{phi(n)})是(phi(n))个和n互质的,小于n的正整数.即:(gcd(n,d_i)=1,i=1,2,...,phi(n)).
由于gcd是积性函数,我们有:(gcd(n,prodlimits_{i=1}^{phi(n)}{d_i})=1).
若(ad_iequiv ad_j pmod{n}),则由a,n互质,我们直接得到:(d_iequiv d_j pmod{n}).
互为逆否命题的命题具有相同真假性.我们有:(d_i ot equiv d_j pmod{n} implies ad_i otequiv ad_j pmod{n})
从剩余系的角度来讲,简化剩余系关于模(n)乘法封闭,故(overline{ad_i})也在简化剩余系中.由于(forall i eq j,d_i eq d_j),集合({overline{d_i}})和({overline{ad_i}})均能表示(n)的简化剩余系,(i=1,2,dots,phi(n)).这里的意思是(forall i=1,2,...,phi(n), exists j=1,2,..,phi(n) , ad_i equiv d_j pmod{n}).
我们可以写出以下式子:$$a^{phi(n)}cdot prodlimits_{i=1}^{phi(n)}d_i equiv prodlimits_{i=1}^{phi(n)}ad_iequiv prodlimits_{i=1}^{phi(n)}d_i pmod{n}$$
由于(gcd(n,prodlimits_{i=1}^{phi(n)}d_i)=1),消去之得到:$$a^{phi(n)}equiv 1 pmod{n}$$
稍微注意一下(prodlimits_{i=1}^{phi(n)}ad_iequiv prodlimits_{i=1}^{phi(n)}d_i pmod{n})这个代换.这里相当于是左右两边(d_i)相乘的顺序不同,但最终的乘积结果相同.原因在上面已经提到了.
当(n)是质数时,(phi(n)=n-1).此时有:$$a^{phi(n)}equiv a^{n-1} equiv 1 pmod{n}$$
证毕.