Fermat

$$
ia \bmod p = ja \bmod p. \iff (j-i)a\equiv 0.\pmod p
$$

但是，$(j-i)$ 和 $a$ 都不是 $p$ 的倍数，这显然矛盾．

换句话说，这些余数是 $\{1,2,\cdots,p-1\}$ 的一个排列．因此，有

$$
\prod_{i=1}^{p-1}i = \prod_{i=1}^{p-1}(ia\bmod p) \equiv \prod_{i=1}^{p-1}ia = a^{p-1}\prod_{i=1}^{p-1}i.\pmod p
$$

这说明

$$
(a^{p-1}-1)\prod_{i=1}^{p-1}i \equiv 0. \pmod{p}
$$

也就是说，等式左侧是 $p$ 的倍数，但是 $i=1,2,\cdots, p-1$ 都不是 $p$ 的倍数，所以，只能有 $p\mid (a^{p-1}-1)$，亦即费马小定理成立．

归纳起点为 $0^p\equiv 0\pmod p$，显然成立．假设它对于 $a\in\mathbf N$ 成立，需要证明的是，它对于 $a+1$ 也成立．由二项式定理可知

$$
(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1.
$$

除了首尾两项，组合数的表达式 $\dbinom{p}{k} = \dfrac{p!}{k!(p-k)!}$ 中，$p$ 都能整除分子，而不能整除分母，因此，这些系数对于 $k\neq 0,p$ 都是 $p$ 的倍数．因此，有

$$
(a+1)^p \equiv a^p + 1\equiv a + 1. \pmod{p}
$$

其中，第二步应用了归纳假设．因此，利用数学归纳法可知，费马小定理成立．

$$
R = \{r\in\mathbf N : 0 < r < m,~\gcd(r,m)=1\}.
$$

这是模 $m$ 的 [既约剩余系](./basic.md#同余类与剩余系)．根据欧拉函数的定义可知，$|R|=\varphi(m)$．类似上文，将它们乘以 $a$ 相当于对该集合重新排列：

$$
R = \{ar\bmod m: r\in R\}.
$$

这是因为，容易验证 $\gcd(ar,m)=1$ 且不同的 $r_1,r_2\in R$ 对应的 $ar_1\bmod m$ 和 $ar_2\bmod m$ 也一定不同．因此，有

$$
\prod_{r\in R}r \equiv \prod_{r\in R}ar = a^{\varphi(m)}\prod_{r\in R}r. \pmod{m}
$$

再次重复之前的论证，消去 $\prod_{r\in R}r$，就得到 $a^{\varphi(m)}\equiv 1\pmod m$．

$$
a^k \equiv \begin{cases}
a^{k \bmod \varphi(m)},                &\gcd(a,m) =  1,                   \\
a^k,                                   &\gcd(a,m)\ne 1, k <   \varphi(m), \\
a^{(k \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, k \ge \varphi(m).
\end{cases} \pmod m
$$

$$
k_0 = \max\left\{\left\lceil\dfrac{\nu_p(m)}{\nu_p(a)}\right\rceil : \nu_p(a)>0\right\}.
$$

因为 $m$ 中所有和 $a$ 的公共素因子的幂次都已经包含在 $a^{k_0}$ 中，所以，$a$ 就与 $m$ 中剩下的因子 $m'=\dfrac{m}{\gcd(a^{k_0},m)}$ 互素．

进而，对 $k\ge k_0$ 考察同余关系

$$
b\equiv a^k. \pmod m
$$

由于 $\gcd(a^{k_0},m)=\gcd(a^k,m)\mid b$，所以，将等式两侧（包括模数）同时除以 $\gcd(a^{k_0},m)$，就有

$$
\dfrac{b}{\gcd(a^{k_0},m)} = \dfrac{a^{k_0}}{\gcd(a^{k_0},m)}\cdot a^{k-k_0}. \pmod{m'}
$$

此时，因为 $a$ 与模数 $m'$ 互素，可以直接应用欧拉定理，得到

$$
\dfrac{b}{\gcd(a^{k_0},m)} \equiv \dfrac{a^{k_0}}{\gcd(a^{k_0},m)}\cdot a^{(k-k_0)\bmod\varphi(m')}. \pmod{m'}
$$

因此，再将因子 $\gcd(a^{k_0},m)$ 乘回去，就得到

$$
b \equiv a^{k_0}\cdot a^{(k-k_0)\bmod\varphi(m')} = a^{k_0 + (k-k_0)\bmod\varphi(m')}. \pmod{m}
$$

这就得到了扩展欧拉定理的形式．式子说明，循环节的长度是 $\varphi(m')$，而进入循环节之前的长度为 $k_0$．

此处得到的参数比扩展欧拉定理中的更紧，但是相对来说，这些参数的计算并不容易．可以说明，这些参数可以放宽到扩展欧拉定理中的情形．首先，利用 [欧拉函数的表达式](./euler-totient.md) 可知，因为 $m'\mid m$，所以 $\varphi(m')\mid\varphi(m)$．也就是说，$\varphi(m)$ 也是它的循环节．其次，$k_0$ 也可以放宽到 $\varphi(m)$．这是因为对于所有 $m\in\mathbf N_+$ 和任意 $p\mid m$，都有

$$
\begin{aligned}
\varphi(m) &\ge \varphi(p^{\nu_p(m)}) = (p-1)p^{\nu_p(m)-1} \ge p^{\nu_p(m)-1} \\
&= (1+(p-1))^{\nu_p(m)-1} \ge 1 + (p-1)(\nu_p(m)-1) \\
&\ge 1 + (\nu_p(m)-1) = \nu_p(m).
\end{aligned}
$$

其中，第二行的不等式利用了二项式展开，并只保留常数项和一次项．因此，有

$$
k_0 \le \max\{\nu_p(m):p\in\mathbf P\}\le \varphi(m).
$$

这就完全证明了所述结论．

$$
A \uparrow\uparrow B =
\begin{cases}
1 , & B = 0,\\
A\uparrow(A\uparrow\uparrow(B-1)), & B > 0.
\end{cases}
$$

规定 $0^0=1$．