一、欧拉定理
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，则根据欧拉定理，费马小定理成立。
