欧拉函数
定义
所有满足小于$m$且与$m$互质的数的个数，称为欧拉函数，记为$\varphi(m)$。
计算公式
将$m$分解质因数，得$m=p_1^{a_1}p_2^{a_2}…p_n^{a_n}$
则$\varphi(m)=m\prod\limits_{i=1}^{n}(1-\dfrac{1}{p_i})$
证明
对于任意一个$p_i$，它的所有倍数在$[1,m]$内是均匀分布的。
因此$\dfrac{1}{p_i}$实际上就是在$[1,m]$内有占多少部分的数(不是多少个数)是$p_i$的倍数。而$1-\dfrac{1}{p_i}$就是$[1,m]$中有占多少部分的数不是$p_i$的倍数。
将两式相乘，比如$(1-\dfrac{1}{p_i})(1-\dfrac{1}{p_j})$，即为$[1,m]$中有占多少部分的数既不是$p_i$的倍数，也不是$p_j$的倍数。
而$\prod\limits_{i=1}^{n}(1-\dfrac{1}{p_i})$，就是$[1,m]$中有多少部分的数不能被所有$m$的质因数整除。显然它们都与$m$互质。
将上式乘上$m$，就由占比得到了个数，因此$\varphi(m)=m\prod\limits_{i=1}^{n}(1-\dfrac{1}{p_i})$
欧拉定理
当$a$与$m$互质时，$a^{\varphi(m)}\equiv 1\pmod{m}$
证明
设m的缩系为$R=\{x_1,x_2,…,x_{\varphi(m)}\}$
另一个集合$S=\{p_i|p_i=a\times x_i\bmod m,1\le i\le \varphi(m),i\in Z\}$
需要证明以下两个结论。
1.$p_i\not\equiv p_j\pmod{m}(1\le i,j\le \varphi(m),i,j\in Z)$
假设$p_i\equiv p_j\pmod{m}$
则$p_i-p_j\equiv 0\pmod{m}$
$\therefore p_i-p_j=km$
$\therefore a(x_i-x_j)=km$
$\therefore a(x_i-x_j)\equiv 0\pmod{m}$
$\therefore \gcd(a,m)=1$,则$x_i-x_j\equiv 0\pmod{m}$
$\therefore x_i-x_j=km$
上式显然不成立，由反证法得证。
2.$p_i\bmod m$与$m$互质
$\because \gcd(a,m)=1,\gcd(x_i,m)=1$
$\therefore \gcd(p_i,m)=1$
由欧几里得算法原理得$\gcd(p_i,m)=\gcd(p_i\bmod m,m)=1$
因此得证。
综上所述，$R=S$
$\therefore p_1p_2…p_{\varphi(m)}\equiv x_1x_2…x_{\varphi(m)}\pmod{m}$
$\therefore a^{\varphi(m)}x_1x_2…x_{\varphi(m)}\equiv x_1x_2…x_{\varphi(m)}\pmod{m}$
$\therefore a^{\varphi(m)}\equiv 1\pmod{m}$
费马小定理
当$m$为质数时，$a^{m-1}\equiv 1\pmod{m}$
证明
由于$m$为质数，$\varphi(m)=m-1$
由欧拉定理得$a^{\varphi(m)}\equiv 1\pmod{m}$
因此$a^{m-1}\equiv 1\pmod{m}$