若 $b\ge\varphi(m)$ ，则有：

\Large a^b\equiv a^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m

$\LaTeX$ ：\Large a^b\equiv a^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m

下面来证明这一式子。

显然，若 $m=1$ ，式子成立。下面的证明只讨论 $m>1$ 。

回顾欧拉定理：若 $(a,m)=1$ ，则 $a^{\varphi(m)}\equiv1\pmod m$ 。

1

设 $p$ 为质数，令 $m=p^r\times s$ ，且 $(s,p)=1$ （就是把 $m$ 中的一个质因子全部提出来）。

由欧拉定理可得：

p^{\varphi(s)}\equiv1\pmod s\tag i

引理：若 $a\equiv b\pmod m$ ， $c\equiv d\pmod m$ ，则有 $ac\equiv bd\pmod m$

由引理可得，若将 $\text{(i)}$ 式自乘 $\varphi(p^r)$ 次，设 $k\in N$ （即 $k$ 是自然数），可得：

\begin{aligned} &(p^{\varphi(s)})^{\varphi(p^r)}\equiv1\pmod s\\\\ \implies&p^{\varphi(m)}\equiv1\pmod s\\\\ \implies&p^{\varphi(m)}=ks+1\\\\ \implies&p^{\varphi(m)+r}=ksp^r+p^r\\\\ \implies&p^{\varphi(m)+r}=km+p^r\\\\ \implies&p^{\varphi(m)+r}\equiv p^r\pmod m\\\\ \end{aligned}

于是，我们得到第一个式子。若 $p$ 是 $m$ 的质因子，若令 $m=p^r\times s$ ，且满足 $(s,p)=1$ ，则有下式：

\large p^{\varphi(m)+r}\equiv p^r\pmod m\tag1

至此， $r$ 仍没有从 $p$ 和 $m$ 的桎梏中解放出来。接下来，我们要解放 $r$ 。

2

首先，我们需要证明一个不等式，为后面的证明奠基：

一个不等式

\large r\le\varphi(p^r)\le\varphi(m)

注：这里的字母都是第 1 步证明里面的字母，关系满足第 1 步证明里的关系**。本文所涉及的字母，一定是声明过的**。这个式子成立的条件是 $p>1,r\ge1$ ，而质数显然都是大于 $1$ 的。

证明：

易得， $\varphi(p^r)\le\varphi(s)\varphi(p^r)=\varphi(m)$ 。这里证明了式子的右端。接下来证明式子的左端。

易得， $\varphi(p^r)=p^r-p^{r-1}=p^{r-1}(p-1)$ 。

因为 $p>1$ ，所以 $\varphi(p^r)\ge p^{r-1}$ 。这里进行了一步缩小。

设函数 $f(r)=p^{r-1}-r$ 。如果证明了 $f(r)$ 在区间 $[1,+\infty)$ 上 $r$ 取整数的离散区间上单调不降，且 $f(r)_{\min}\ge0$ ，即函数值不小于 $0$ ，则式子的左端即可成立。

$\LaTeX$ ：[1,+\infty)

\begin{aligned} &\text{ }f(r+1)-f(r)\\\\ =&\text{ }p^r-r-1-p^{r-1}+r\\\\ =&\text{ }p^{r-1}(p-1)-1\\\\ \end{aligned}

因为 $p-1\ge1$ ， $p^{r-1}\ge1$ ，所以上式不小于 $0$ 。证毕。

故 $f(r)_{\min}=f(1)=p^0-1=0$ 。

所以原不等式成立。

新的同余式

设 $c\ge\varphi(m)$ ，因为”一个不等式“成立，所以 $c\ge r$ 。保证了 $p^{c-r}$ 是整数。式 $\text{(1)}$ 两端同乘以 $p^{c-r}$ ，可得：

p^{c-r}\times p^r\equiv p^{c-r}\times p^{\varphi(m)+r}\pmod m

即同余式：

\large p^c\equiv p^{\varphi(m)+c}\pmod m\tag2

将 $(2)$ 式迭代，可得同余式：

\large p^c\equiv p^{k\varphi(m)+c}\pmod m\tag3

这两个式子成立的条件是： $p$ 是 $m$ 的质因子， $c\ge\varphi(m)$ 。

3

显然，任意的 $b\ge\varphi(m)$ ， $b$ 可表示为 $b\bmod \varphi(m)+\varphi(m)+k\varphi(m)$ 。

因为 $c\ge\varphi(m)$ ，故若令 $c=b\bmod\varphi(m)+\varphi(m)$ ，由式 $\text{(3)}$ 可得：

p^{b\text{ mod }\varphi(m)+\varphi(m)}\equiv p^{b\text{ mod }\varphi(m)+\varphi(m)+k\varphi(m)}=p^b\pmod m

即同余式：

\large p^{b\text{ mod }\varphi(m)+\varphi(m)}\equiv p^b\pmod m\tag4

这个式子成立的条件是： $p$ 是 $m$ 的质因子， $b\ge\varphi(m)$ 。

看！这个式子的形式和我们要证的式子大致相同了！现在的工作只是将 $p$ 换为任意数了。

4

设 $(a,m)=d$ ， $a=qd$ ， $b\ge\varphi(m)$ 。则：

\begin{aligned} &\text{ }a^b\bmod m\\\\ =&\text{ }(qd)^b\bmod m\\\\ =&\text{ }(q^bd^b)\bmod m\\\\ =&\text{ }(q^b\bmod m)(d^b\bmod m) \bmod m \end{aligned}

显然 $(q,m)=1$ ，由欧拉定理可得：

q^b\equiv q^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m\tag{ii}

设 $p_i$ 是 $d$ 的质因子，则

d^b\equiv\prod_i(p_i^b\bmod m)^{c_i}\pmod m

显然， $p_i$ 是 $m$ 的质因子。因 $b\ge\varphi(m)$ ，可以套用式 $\text{(4)}$ 可得

\begin{aligned} &\text{ }d^b\\\\ \equiv&\text{ }\prod_i(p_i^{b\text{ mod }\varphi(m)+\varphi(m)}\bmod m)^{c_i}\pmod m\\\\ \equiv&\text{ }(\prod_ip_i^{c_i})^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m\\\\ \equiv&\text{ }d^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m\tag{iii} \end{aligned}

将 $\text{(ii)(iii)}$ 两式相乘，可得：

(qd)^b\equiv (qd)^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m

即我们想要证明的：

\Large a^b\equiv a^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m

这个式子成立的条件是： $b\ge\varphi(m)$ 。

至此，我们完成了扩展欧拉定理的证明。~~为了证明这个破式子，居然用了 1373 词。~~

应用

求 $a^b \bmod m$ （ $b$ 极大，有 $20000000$ 位）。P5091 【模板】扩展欧拉定理。
求 $2^{2^{2^{2^{\dots}}}}\bmod m$ （递归式求法）。P4139 上帝与集合的正确用法。

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/96dc68c46198/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 数论

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158

扩展欧拉定理及其证明

1

2

一个不等式

新的同余式

3

4

应用