定义#

若 $p$ 是素数，且 $\gcd(a,p) = 1$ ，则

另一种形式：若 $p$ 是素数，则

证明#

构造集合 $A=\{1,2,\dots,p-1\}$ ，将集合中每一个数都乘以 $a$ 再模 $p$ ，即 $r_n=n\times a \bmod p$ ，得到新集合 $B=\{r_1,r_2,r_3,\dots,r_{p-1}\}$ 。

则有 $A = B$ ，这是因为 $\forall x,y \in A, \; x \neq y$ ，有 $ax-ay=a(x-y)\not\equiv 0 \pmod{p}$，即 $ax \not\equiv ay \pmod{p}$ ，故 $p-1$ 个 $r_n$ 互不相同。

于是就得到了 $B$ 其实也是 $\{1,2,\dots,p-1\}$，和 $A$ 一样。

所以

即

因为 $(p-1)!$ 与 $p$ 互质，可以两边都除以 $(p-1)!$ 即得证。

定义#

欧拉函数 $\varphi(n)$ 表示所有小于 $n$ 的数中与 $n$ 互质的数的个数。

性质#

对于质数 $p$ ，由定义立即有 $\varphi(p) = p-1$

欧拉函数是积性函数，这意味着若 $\gcd(a,b)=1$ 有 $\varphi(a\times b) = \varphi(a)\times\varphi(b)$

还有很多有趣的性质，感兴趣可以自行了解。

定义#

若 $\gcd(a,m)=1$ ，则

不难发现欧拉定理是费马小定理的推广，费马小定理是欧拉定理当 $m$ 为质数的特例。

证明#

欧拉定理的证明也和费马小定理的证明很像，考虑所有小于 $m$ 与 $m$ 互质的数的集合 $\Phi=\{c_1,c_2,\dots,c_{\varphi(m)}\}$

再记 $a\Phi=\{ac_1,ac_2,\dots,ac_{\varphi(m)}\}$

同上，不难验证 $c_n$ 也是互异的，且 $c_n$ 与 $m$ 互质， $a\Phi$ 也是所有小于 $m$ 与 $m$ 互质的数的集合。所以

接下来就顺理成章了

拓展学习：群论中的拉格朗日定理

应用#

由 $a^{\varphi(m)}\equiv1\pmod{m}$ 可以得到

• 在实际应用中，可以使用欧拉定理对指数降幂

• 欧拉定理还可以应用到RSA加密算法中

定义#

扩展欧拉定理：

也就是说，假如 $a,m$ 不互质且 $n$ 不够大，那降幂。假如 $a,m$ 不互质且 $n$ 足够大，可以降幂，但是需要在指数上多加一个 $\varphi(m)$

证明#

扩展欧拉定理的证明相对就没有其他两个定理简单了，所以我咕咕咕了