费马小定理 & 欧拉定理

设 $p$ 是素数。对于任意整数 $a$ 且 $p\nmid a$，都成立 $a^{p-1}\equiv 1(\mathrm{mod}p)$.

设 $p$ 是素数。对于任意整数 $a$，都成立 $a^p\equiv a(\mathrm{mod}p)$.

设 $p$ 是素数，且 $p\nmid a$。首先证明：对于 $i=1,2,\cdots ,p-1$，余数 $iamodp$ 各不相同。反证法。如果有 $1\le i<j<p$ 使得

$$iamodp=jamodp.⟺(j-i)a\equiv 0.(\mathrm{mod}p)$$

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

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

$$\prod _{i=1}^{p-1}i=\prod _{i=1}^{p-1}(iamodp)\equiv \prod _{i=1}^{p-1}ia=a^{p-1}\prod _{i=1}^{p-1}i.(\mathrm{mod}p)$$

这说明

$$(a^{p-1}-1)\prod _{i=1}^{p-1}i\equiv 0.(\mathrm{mod}p)$$

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

注意到费马小定理的第二种表述对于所有 $a\in \mathbf{N}$ 都成立，因此，可以考虑使用数学归纳法。负整数的情形容易转化为非负整数的情形。

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

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

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

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

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

对于整数 $m>0$ 和整数 $a$，且 $gcd(a,m)=1$，有 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$，其中，$\phi (\cdot )$ 为 欧拉函数。

与费马小定理的证明一类似，仍然是取一个与 $m$ 互质的数列，再进行操作。考虑集合

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

这是模 $m$ 的 既约剩余系。根据欧拉函数的定义可知，$|R|=\phi (m)$。类似上文，将它们乘以 $a$ 相当于对该集合重新排列：

$$R=\{armodm:r\in R\}.$$

这是因为，容易验证 $gcd(ar,m)=1$ 且不同的 $r_1,r_2\in R$ 对应的 $a{r}_{1}modm$ 和 $a{r}_{2}modm$ 也一定不同。因此，有

$$\prod _{r\in R}r\equiv \prod _{r\in R}ar=a^{\phi (m)}\prod _{r\in R}r.(\mathrm{mod}m)$$

再次重复之前的论证，消去 $\prod _{r\in R}r$，就得到 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$。

对于任意正整数 $m$、整数 $a$ 和非负整数 $k$，有

$$a^k\equiv \{\begin{array}{ll}{a}^{kmod\phi (m)},& gcd(a,m)=1,\\ a^k,& gcd(a,m)\ne 1,k<\phi (m),\\ a^{(kmod\phi (m))+\phi (m)},& gcd(a,m)\ne 1,k\ge \phi (m).\end{array}(\mathrm{mod}m)$$

首先说明，存在 $k_0\in \mathbf{N}$，使得整数 $a$ 和 $m^{\prime }:={\displaystyle \frac{m}{gcd(a^{k_0},m)}}$ 互素。为此，设 ${\nu }_p(n)$ 是整数 $n$ 的质因数分解中素数 $p$ 的幂次，那么，不妨取

$$k_0=max\{\lceil {\displaystyle \frac{{\nu }_p(m)}{{\nu }_p(a)}}\rceil :{\nu }_p(a)>0\}.$$

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

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

$$b\equiv a^k.(\mathrm{mod}m)$$

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

$${\displaystyle \frac{b}{gcd(a^{k_0},m)}}={\displaystyle \frac{a^{k_0}}{gcd(a^{k_0},m)}}\cdot a^{k-k_0}.(\mathrm{mod}{m}^{\prime })$$

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

$${\displaystyle \frac{b}{gcd(a^{k_0},m)}}\equiv {\displaystyle \frac{a^{k_0}}{gcd(a^{k_0},m)}}\cdot a^{(k-k_0)mod\phi (m^{\prime })}.(\mathrm{mod}{m}^{\prime })$$

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

$$b\equiv a^{k_0}\cdot a^{(k-k_0)mod\phi (m^{\prime })}=a^{k_0+(k-k_0)mod\phi (m^{\prime })}.(\mathrm{mod}m)$$

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

此处得到的参数比扩展欧拉定理中的更紧，但是相对来说，这些参数的计算并不容易。可以说明，这些参数可以放宽到扩展欧拉定理中的情形。首先，利用 欧拉函数的表达式 可知，因为 $m^{\prime }\mid m$，所以 $\phi (m^{\prime })\mid \phi (m)$。也就是说，$\phi (m)$ 也是它的循环节。其次，$k_0$ 也可以放宽到 $\phi (m)$。这是因为对于所有 $m\in {\mathbf{N}}_{+}$ 和任意 $p\mid m$，都有

$$\begin{array}{rl}\phi (m)& \ge \phi (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{array}$$

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

$$k_0\le max\{{\nu }_p(m):p\in \mathbf{P}\}\le \phi (m).$$

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

利用 $A\uparrow \uparrow B$ 的定义，递归计算即可。要计算 $(A\uparrow \uparrow B)modM$，只需要应用扩展欧拉定理，计算 $(A\uparrow \uparrow (B-1))mod\phi (M)$。由于 $\phi (\phi (n))\le n/2$ 对所有 $n\ge 2$ 都成立，所以，递归过程一定在 $O(\log M)$ 步内完成。由于需要应用扩展欧拉定理，所以需要区分当前的计算结果是否严格小于当前模数。为此，只需要在取余的时候多判断一步即可。另外，需要注意边界情况的处理。