欧拉定理

定理：设$a, p$均为正整数，且$\gcd(a, p) = 1$，即$a$和$p$互质，则
$$a^{\varphi(p)} \equiv 1 \mod p$$
其中，$\varphi(p)$是$p$的欧拉函数。

证明

我们基于模$p$的同余类构造一个集合$S$，包含所有小于$p$且与$p$互质的整数：
$$S = \left \{ x_1, x_2, \dots , x_{\varphi(p)} \right \}$$

其中$\varphi(p)$表示集合中元素的个数。

假设我们将集合$S$中的每一个元素都乘以$a$（这里$a$与$p$互质），并取模$p$，得到集合$T$：
$$T = \{ax_1 \bmod p, a x_2 \bmod p, \dots, a x{\varphi(p)} \bmod p \}$$

证明$T$与$S$中元素互不相同

由于$a$和$p$互质，$ax_i \bmod p$与$x_i$在同余算式中保持一一对应关系，所以$T$中的元素不会重复，并且$T$中的元素依然是小于$p$且与$p$互质的整数。这意味着$T$实际上就是$S$的一个排列。

因此，我们有以下等式：
$$x_1 x_2 \dots x_{\varphi(p)} \equiv (a x_1) (a x_2) \dots (a x_{\varphi(p)}) \bmod{p}$$

可以将右边的表达式提取出$a$的幂次项：

$$x_1 x_2 \dots x_{\varphi(p)} \equiv a^{\varphi(p)} \cdot x_1 x_2 \dots x_{\varphi(p)} \bmod{p}$$

因为$x_1 x_2 \dots x_{\varphi(p)}$与$p$互质，可以在同余式中消去它们，得到：

$$$a^{\varphi(p)} \equiv 1 \bmod{p}$$

与费马小定理的联系

当$p$为质数时，$\varphi(p) = p - 1$，此时欧拉定理退化为费马小定理。