拓展Euler定理

本节结论和证明过程均整理来自于 OI Wiki 费马小定理 & 欧拉定理

概述

在本节，我们将通过两个引理，来证明拓展欧拉定理，其表述为：

对于任意正整数 $a,m$ 以及非负整数 $k$ ，我们有
$\begin{cases} a^k\equiv a^{k\mod\varphi(m)}\pmod m&\text{where }\mathrm{gcd}(a,m)=1\\ a^k\equiv a^{\big(k\mod\varphi(m)\big)+\varphi(m)}\pmod m&\text{where }\mathrm{gcd}(a,m)>1,\;k\geqslant\varphi(m)\\ a^k\equiv a^{k}\pmod m&\text{where }\mathrm{gcd}(a,m)>1,\;k<\varphi(m)\\ \end{cases}$
但是注意到，当 $k<\varphi(m)$ 时， $k\mod\varphi(m)$ 就是 $k$ 本身，因此第三种情况可以合并到第一种；此外，当 $a,m$ 互素时，由欧拉定理可知 $a^{\varphi(m)}\equiv1\pmod m$ ，此时 $a$ 再添任意有限个 $\varphi(m)$ 幂次都不影响结果，因此第一种又可以和第二种合并，于是我们可以利用示性函数（当条件满足取 $1$ ，否则取 $0$ ）统一写为
$a^k\equiv a^{\big(k\mod\varphi(m)\big)+\varphi(m)\cdot\mathbb I(k\geqslant\varphi(m))}\pmod m$

引理1

对于任意整数 $a,m\in\mathbb Z$ ，都存在一个最小的正整数 $k_0>0$ ，使得
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$

证明：

若 $a,m$ 互素，则取 $k_0=1$ 即满足条件。

下面考虑不互素的情况：设
$d=\mathrm{gcd}(a,m)=p_1^{s_1}p_2^{s_2}\cdots p_n^{s_n}>1,\;(n>0,\;s_1,s_2,\cdots,s_n>0)$
我们先从直觉上来感受这个引理的内涵：假设取 $k_0$ 充分大——例如极限情况取到无穷大，则 $a^{k_0}$ 含有 $\prod_{i=1}^np_i^\infty$ 作为因子，于是它和 $m$ 的最大公约数中包含每一个 $p_i$ ，且 $p_i$ 的幂次显然就是 $p_i$ 在 $m$ 中的幂次，这意味着 $m$ 除以这个最大公约数后，不再含有任何 $p_i$ 作为因子，因而这个除法结果必然和 $a$ 互素。取满足条件的最小的 $k_0$ 即可。

现在来给出 $a,m$ 不互素情况下的严格证明：我们考虑表
$\begin{cases} m&=p_1^{s_1+\delta_1}p_2^{s_2+\delta_2}\cdots p_n^{s_n+\delta_n}\cdot m''\\ a&=p_1^{s_1+\theta_1}p_2^{s_2+\theta_2}\cdots p_n^{s_n+\theta_n}\cdot a'' \end{cases},\quad(\delta_i\geqslant0,\,\theta_i\geqslant0,\;p_i\not| a'',\,p_i\not| m'',\;\forall i=1,2,\cdots,n)$
它满足如下约束：

$\forall i=1,2,\cdots,n$ ，必有 $\delta_i\theta_i=0$ 。如若不然，存在某个 $i$ 使得 $\delta_i\theta_i>0\Rightarrow\delta_i,\theta_i>0\Rightarrow\min\{\theta_i,\delta_i\}>0$ ，则 $p_i^{s_i+\min\{\delta_i,\theta_i\}}$ 是二者的公约数，但这和 $d$ 的定义矛盾；
$a'',m''$ 互素。如若不然， $a,m$ 还有第 $n+1$ 个素数作为公约数，这和 $d$ 的定义矛盾。

首先，对于任意正整数 $p,q$ ，我们有
$\mathrm{gcd}(a'',m'')=1\Longrightarrow\mathrm{gcd}\big((a'')^p,(m'')^q\big)=1$

这来源于最大公约数的一个性质：若 $\mathrm{gcd}(c,a)=1$ ，则 $\mathrm{gcd}(c,ab)=\mathrm{gcd}(c,b)$ 。

于是，若令 $b\leftarrow a$ ，则从 $\mathrm{gcd}(c,a)=1$ 可以推知 $\mathrm{gcd}(c,a^2)=\mathrm{gcd}(c,a)=1$ ，进而得出 $\mathrm{gcd}(c,a^q)=1$ 。

由最大公约数的交换律，以及再次利用得到的结果，我们就可以从 $\mathrm{gcd}(c,a)=1$ 得出 $\mathrm{gcd}(c^p,a^q)=1$ 。

我们考虑带余除法
$s_i+\delta_i=k_i(s_i+\theta_i)+r_i,\quad(k_i\geqslant0,\;0\leqslant r_i<s_i+\theta_i)$
并令
$k_0=\max\{k_i+\mathbb I_{r_i>0}\}$
其中 $\mathbb I_{r_i>0}$ 是示性函数，仅当 $r_i>0$ 时取 $1$ ，否则取 $0$ ，从而不难看出 $k_0>0$ 。

显然 $k_0$ 就是满足如下条件的最小正整数
$\forall i=1,2,\cdots,n,\quad k_0(s_i+\theta_i)\geqslant s_i+\delta_i$
进而就有
$\forall i=1,2,\cdots,n,\quad \min\{k_0(s_i+\theta_i),s_i+\delta_i\}=s_i+\delta_i$
于是，我们不难发现此时有
$\begin{aligned} \mathrm{gcd}(a^{k_0},m) &=\mathrm{gcd}\Big(\overline{p_1^{k_0(s_1+\theta_1)}p_2^{k_0(s_2+\theta_2)}\cdots p_n^{k_0(s_n+\theta_n)}\cdot (a'')^{k_0}}\;,\;\underline{p_1^{s_1+\delta_1}p_2^{s_2+\delta_2}\cdots p_n^{s_n+\delta_n}\cdot m''}\Big)\\ &=p_1^{\min\{k_0(s_1+\theta_1),s_1+\delta_1\}}p_2^{\min\{k_0(s_2+\theta_2),s_2+\delta_2\}}\cdots p_n^{\min\{k_0(s_n+\theta_n),s_n+\delta_n\}}\cdot\underbrace{\mathrm{gcd}\big((a'')^{k_0},m''\big)}_{=1}\\ &=p_1^{s_1+\delta_1}p_2^{s_2+\delta_2}\cdots p_n^{s_n+\delta_n} \end{aligned}$
且
$m''=m/\mathrm{gcd}(a^{k_0},m)$
于是
$\mathrm{gcd}(a,m'')=1$

□

事实上，如果我们用 $\nu_p(n)$ 表示整数 $n$ 中素数的幂次，则在上面证明中我们可以表示为
$\nu_{p_i}(m)=s_i+\delta_i,\;\nu_{p_i}(a)=s_i+\theta_i$
以及
$k_0=\max\left\{\left\lceil\frac{\nu_{p_i}(m)}{\nu_{p_i}(a)}\right\rceil,i=1,2,\cdots,n\right\}$
当 $a,m$ 不互素时，也可以表示为
$k_0=\max\left\{\left\lceil\frac{\nu_{p}(m)}{\nu_{p}(a)}\right\rceil:\nu_p(a)>0,\forall p\in\mathbb P\right\}$
其中 $\mathbb P$ 是所有素数的集合。

引理1-推论1

设 $k_0$ 是满足引理1中结论的最小的正整数，则 $\forall k\geqslant k_0$ ，我们都有
$\mathrm{gcd}(a^k,m)=\mathrm{gcd}(a^{k_0},m)$
因而
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k},m)}\Big)=\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$

证明：

当 $a,m$ 互素时，显然成立。

当 $a,m$ 不互素时，由
$\forall i=1,2,\cdots,n,\quad \min\{k_0(s_i+\theta_i),s_i+\delta_i\}=s_i+\delta_i$
不难推出
$\forall i=1,2,\cdots,n,\quad \min\{k(s_i+\theta_i),s_i+\delta_i\}=s_i+\delta_i$
从而
$\begin{aligned} \mathrm{gcd}(a^{k},m) &=p_1^{\min\{k(s_1+\theta_1),s_1+\delta_1\}}p_2^{\min\{k(s_2+\theta_2),s_2+\delta_2\}}\cdots p_n^{\min\{k(s_n+\theta_n),s_n+\delta_n\}}\cdot\underbrace{\mathrm{gcd}\big((a'')^{k},m''\big)}_{=1}\\ &=p_1^{s_1+\delta_1}p_2^{s_2+\delta_2}\cdots p_n^{s_n+\delta_n}=\mathrm{gcd}(a^{k_0},m) \end{aligned}$

引理1-推论2

设 $k_0$ 是满足引理1中结论的最小的正整数，则 $\forall k_1,k_2\geqslant k_0$ ，我们都有
$\mathrm{gcd}(a^{k_1},m)=\mathrm{gcd}(a^{k_2},m)$
因而
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_1},m)}\Big)=\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_2},m)}\Big)=1$

证明：由推论1直接得到。

引理2

设 $a,m$ 是正整数， $k_0$ 为引理1中所述，则我们有
$k_0\leqslant\varphi(m)$
其中 $\varphi(m)$ 为欧拉函数。

证明：

引入引理1最后提到的记号：
$\nu_p(m)=s\iff p^s|m\text{, and }p^{s+1}\not| m$
从而对于 $m$ 的任意素因数 $p$ 有
$\begin{aligned} \varphi(m) &\geqslant\varphi(p^{\nu_p(m)})=(p-1)\cdot p^{\nu_p(m)-1}\quad\text{(By Euler Function)}\\ &\geqslant p^{\nu_p(m)-1}=\big(1+(p-1)\big)^{\nu_p(m)-1}=1+\binom{\nu_p(m)-1}{1}1^{\nu_p(m)-2}\cdot(p-1)+\dots\text{(other binomials)}\\ &\geqslant 1+(\nu_p(m)-1)\cdot(p-1)\\ &\geqslant 1+(\nu_p(m)-1)=\nu_p(m) \end{aligned}$
注意到 $k_0=\max\{k_i+\mathbb I_{r_i>0}\}$ ，其中 $s_i+\delta_i=k_i(s_i+\theta_i)+r_i,\quad(k_i\geqslant0,\;0\leqslant r_i<s_i+\theta_i)$ 如引理1中所定义，从而
$\begin{aligned} k_0 &=\max\left\{\left\lceil\frac{s_i+\delta_i}{s_i+\theta_i}\right\rceil\right\}=\max\left\{\left\lceil\frac{\nu_{p_i}(m)}{\nu_{p_i}(a)}\right\rceil\right\}\\ &\leqslant \max\nu_{p_i}(m)\\ &\leqslant\max\varphi(m)=\varphi(m) \end{aligned}$
即证明了引理2。

证明过程中用到了上取整函数的如下性质：设正整数 $s,u$ ，我们有
$\lceil s/u\rceil\leqslant s$
这是因为，考虑带余除法 $s=ku+r$ ，其中 $0\leqslant k\leqslant s,\;0\leqslant r<u$ ，则
$\lceil s/u\rceil=k+\mathbb I_{r>0}$
如果 $r=0$ ，则 $\mathbb I_{r>0}=0$ ，此时 $\lceil s/u\rceil=k\leqslant s$ 成立；否则， $r>0$ ，此时必有 $u>1$ ，于是 $\lceil s/u\rceil=k+1$ ，假若我们有 $\lceil s/u\rceil> s$ ，则
$k+1>s=ku+r\Rightarrow 1-r>k(u-1)$
因为 $1-r\leqslant0$ ，这说明 $k(u-1)$ 严格小于 $0$ ，但这是不可能的，因为 $u>1,\,k\geqslant0$ 。

引理2-推论1

设 $k_0$ 是满足引理1中结论的最小的正整数， $\varphi$ 是欧拉函数，则
$\mathrm{gcd}(a^{\varphi(m)},m)=\mathrm{gcd}(a^{k_0},m)$
因而
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{\varphi(m)},m)}\Big)=\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$

证明：

由引理2和引理1-推论1立即可得。

拓展欧拉定理证明

基本（但不优雅）的形式

设 $a,m$ 是正整数，由引理1，可知存在一个最小的 $k_0$ 使得
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$
对于任意正整数
$k\geqslant k_0$
则由引理1的推论1得知有如下条件成立
$\mathrm{gcd}(a^k,m)=\mathrm{gcd}(a^{k_0},m),\quad \mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k},m)}\Big)=1$
现在考虑满足如下同余式的整数 $b$ ：
$b\equiv a^k\pmod m$
从中不难看出， $a^k,m$ 的公约数必然也是 $b$ 的公约数，由此并利用同余式的等价变形可以得到
$\frac{b}{\mathrm{gcd}(a^{k},m)}\equiv \frac{a^k}{\mathrm{gcd}(a^{k},m)}\pmod{\frac m{\mathrm{gcd}(a^{k},m)}}$

事实上这个等价变形中我们省略叙述了一部分：同余式有等价变形 $zx\equiv zy\pmod n\iff x\equiv y\pmod{n/\mathrm{gcd}(z,m)}$ ，在上式中，模部分实际上应该是
$\mod\frac m{\mathrm{gcd}\big(m,\underline{\mathrm{gcd}(a^k,m)}\big)}$
但一个整数和其任意正因数的最大公约数显然还是该因数本身：
$\mathrm{gcd}\big(m,\underline{\mathrm{gcd}(a^k,m)}\big)=\underline{\mathrm{gcd}(a^k,m)}$
从而从形式上好像是等式两边包括模数都同时除以了 $\mathrm{gcd}(a^k,m)$ ，但一定要注意我们这里省略的步骤。

或等价写为
$\frac{b}{\mathrm{gcd}(a^{k_0},m)}\equiv \frac{a^{k_0}\cdot a^{k-k_0}}{\mathrm{gcd}(a^{k_0},m)}\pmod{\frac m{\mathrm{gcd}(a^{k_0},m)}}$
令
$m''=\frac m{\mathrm{gcd}(a^{k_0},m)}$
因为 $\mathrm{gcd}(a,m'')=1$ ，由欧拉定理可知 $a^{\varphi(m'')}\equiv1\pmod{m''}$ ，则由带余除法 $k-k_0=c\cdot\varphi(m'')+r$ 我们就有 $a^{k-k_0}=(a^{\varphi(m'')})^c\cdot a^r\equiv 1^c\cdot a^r\equiv a^r\pmod{m''}$ ，代入上面同余式得到
$\frac{b}{\mathrm{gcd}(a^{k_0},m)}\equiv \frac{a^{k_0}}{\mathrm{gcd}(a^{k_0},m)}\cdot a^r\pmod{m''}$

注意！ 同余代换只能发生在两个整数乘积时，对其中一个整数做替换。例如上面的过程中，因为 $a^{k_0}/\mathrm{gcd}(a^{k_0},m)$ 是整数， $a^{k-k_0}$ 也是整数，因此把 $a^{k-k_)}$ 代换为模 $m''$ 同余的 $a^r$ 是没有问题的，但是，假若我们表示为
$\frac{a^s\cdot a^{k-s}}{\mathrm{gcd}(a^{k_0},m)}\in\mathbb Z$
且 $\mathrm{gcd}(a^{k_0},m)$ 不能整除 $a^s$ 时，此时 $\frac{a^s}{\mathrm{gcd}(a^{k_0},m)}$ 不是整数，则不能对 $a^{k-s}$ 做同余代换！切记！

再次乘以 $\mathrm{gcd}(a^{k_0},m)$ 就有
$b\equiv a^{k_0+r}\pmod m$
因为 $r$ 是带余除法的余数， $0\leqslant r<\varphi({m''})$ ，不妨记为 $r=(k-k_0)\mod{\varphi(m'')}$ ，于是我们得到了一个直接结果
$a^k\equiv a^{k_0+\big((k-k_0)\mod{\varphi(m'')}\big)}\pmod m,\quad k\geqslant k_0$

另一方面，当 $k<k_0$ 时，可以直接计算得到
$a^k\equiv a^{k}\pmod m,\quad k< k_0$

■

但是一般要求得这样的 $k_0$ 仍然是困难的。因此，我们可以将指数部分适当放宽，这样虽然增加了计算量，但是可以得出与 $k,a,m$ 直接相关的简单形式。

宽松（但简单）的形式

现在，我们来宽松一下，利用引理2的推论1结果
$\mathrm{gcd}(a^{\varphi(m)},m)=\mathrm{gcd}(a^{k_0},m)$
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{\varphi(m)},m)}\Big)=\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$
我们首先考虑 $k\geqslant \varphi(m)$ 的情况，此时由上一小节的中间结果得到
$\frac{b}{\mathrm{gcd}(a^{\varphi(m)},m)}\equiv\frac{a^{\varphi(m)}\cdot a^{k-\varphi(m)}}{\mathrm{gcd}(a^{\varphi(m)},m)}\pmod{m''}$
考虑带余除法
$k=w\cdot\varphi(m)+r,\quad(0\leqslant r<\varphi(m))$
以及利用欧拉函数如下性质
$m''|m\Longrightarrow \varphi(m'')|\varphi(m)\Rightarrow \varphi(m)=c\cdot\varphi(m'')$
因为 $a,m''$ 互素所以 $a^{\varphi(m'')}\equiv1\pmod{m''}$ ，从而
$a^{k-\varphi(m)}=a^{(w-1)\varphi(m)+r}=\big((a^{\varphi(m'')})^{c\cdot(w-1)}\cdot a^r\big)\equiv1^{c\cdot(w-1)}\cdot a^r=a^r\pmod{m''}$
对同余式做同余代换得到
$\frac{b}{\mathrm{gcd}(a^{\varphi(m)},m)}\equiv\frac{a^{\varphi(m)}\cdot a^{r}}{\mathrm{gcd}(a^{\varphi(m)},m)}\pmod{m''}$
两边同时乘以 $\mathrm{gcd}(a^{\varphi(m)},m)$ ，就有
$b\equiv a^{\varphi(m)+r}\pmod m$
将 $r$ 写为 $k\mod{\varphi(m)}$ ，我们就得到了
$a^k\equiv a^{\varphi(m)+(k\mod\varphi(m))}\pmod m,\quad k\geqslant\varphi(m)$

另一方面，当 $k<\varphi(m)$ 时， $k$ 除以 $\varphi(m)$ 的余数就是 $k$ 本身，也即
$\big(k\mod\varphi(m)\big)=k$
因此可以直接计算（利用快速幂）
$a^k\equiv a^k\pmod m,\quad k<\varphi(m)$
合起来可以统一用示性函数表示为（我们用 $\exp_a$ 来表示 $a$ 的幂）
$\exp_a k\equiv \exp_a\big(k\mod\varphi(m)+\varphi(m)\cdot\mathbb I_{k\geqslant\varphi(m)}\big)\pmod m$
注意，当 $a,m$ 互素时，总有 $a^{\varphi(m)}\equiv1\pmod m$ ，此时总有
$\begin{aligned} \exp_a\big(k\mod\varphi(m)+\varphi(m)\cdot\mathbb I_{k\geqslant\varphi(m)}\big) &=a^{k\mod\varphi(m)}\cdot \big(a^{\varphi(m)}\big)^{\mathbb I_{k\geqslant\varphi(m)}}\\ &\equiv a^{k\mod\varphi(m)}\cdot 1^{\mathbb I_{k\geqslant\varphi(m)}}=a^{k\mod\varphi(m)}\cdot 1\\ &=a^{k\mod\varphi(m)}\pmod m \end{aligned}$
因此互素实际上是上面这个等式的特殊情况。