一、欧拉定理
1、定义
若a与n互质,则aφ(n)≡1a^{\varphi (n)} \equiv 1aφ(n)≡1 (mod n)。
其中φ(n)\varphi (n)φ(n)指欧拉函数:小于n的正整数中与n互质的个数。
2、证明
我们假设n的质因子分别是:p1,p2,...,pφ(n)p_1,p_2,...,p_{\varphi(n)}p1,p2,...,pφ(n),记为序列1。
若给每一项都乘a,得序列2:ap1,ap2,...,apφ(n)ap_1,ap_2,...,ap_{\varphi(n)}ap1,ap2,...,apφ(n)。
因为aaa与n互质,且pip_ipi与n互质,因此apiap_iapi也与n互质。且apiap_iapi % n各不相同。这个可以用反证法证得:若假设api≡apjap_i \equiv ap_japi≡apj (mod n),则两边同除以a,得pi≡pjp_i \equiv p_jpi≡pj,又因为pip_ipi和pjp_jpj是n的质因子,其互不相同,则原假设不成立。
则可得序列2对n取余所得余数就是序列1,小于n的正整数且与n互质的数有且只有φ(n)\varphi (n)φ(n)个,就是这个序列1。
因此将序列2模n后累乘起来和序列1累乘起来的结果是相同的(模n等同于同余n),即可得:aφ(n)⋅(a1⋅a2⋅...⋅aφ(n))≡a1⋅a2⋅...⋅aφ(n)a^{\varphi(n)} \cdot (a_1\cdot a_2\cdot ... \cdot a_{\varphi(n)}) \equiv a_1\cdot a_2\cdot ... \cdot a_{\varphi(n)}aφ(n)⋅(a1⋅a2⋅...⋅aφ(n))≡a1⋅a2⋅...⋅aφ(n) (mod n)
两边同时除以a1⋅a2⋅...⋅aφ(n)a_1\cdot a_2\cdot ... \cdot a_{\varphi(n)}a1⋅a2⋅...⋅aφ(n)可得aφ(n)≡1a^{\varphi(n)} \equiv 1aφ(n)≡1 (mod n)。
二、费马小定理
1、定义
若a与n互质,且n为质数,则an−1≡1a^{n-1}\equiv1an−1≡1 (mod n)。
2、证明
费马小定理其实就是欧拉定理的一个特殊情况,当n是质数时,小于n的正整数都和n互质,所以他的欧拉函数就等于an−1a^{n-1}an−1,即aφ(n)=an−1a^{\varphi(n)}= a^{n-1}aφ(n)=an−1,则根据欧拉定理,费马小定理成立。