欧拉定理

若\(\gcd(a,m)=1\)，则满足\(a^{\varphi (m)} \equiv 1 \pmod m\)

证明

设\([1,m)\)内与\(m\)互质的数为数列\(\{b_n\}=\{b_1,b_2,b_3,\cdots,b_{\varphi (m)}\}\)

因为\(a,m\)互质且\(b_i,m\)互质，所以数列\(\{A_n\}=\{ab_1,ab_2,ab_3,\cdots,ab_{\varphi(m)}\}\)中每个数都与\(m\)互质，且两两不同。

同时，由\(\gcd(ab_i,m)=1\)可得\(\gcd(ab_i \bmod m,m)=1\)，即每个\(A_i\)除以\(m\)的余数都与\(m\)互质，且余数两两不同。

可以用反证法推出“余数两两不同”。假设存在\(ab_i \equiv ab_j \pmod m\)，那么\(ab_i-ab_j=km\ (k \in \mathbb{Z})\)，即\(a(b_i-b_j)=km\)。由于\(a\)与\(m\)互质，那么只能是\(m \mid (b_i-b_j)\)，即\(b_i \equiv b_j \pmod m\)。这与\(1 \leq b_i,b_j < m\)且\(b_i \neq b_j\)的题设相违背，因此假设不成立。

所以\(\{A_n\}\)中的每个数一定与\(\{b_n\}\)中的一个数同余，且一一对应。

所以\(a^{\varphi (m)}\prod_{i=1}^{\varphi (m)}b_i \equiv \prod_{i=1}^{\varphi (m)}ab_i \equiv \prod_{i=1}^{\varphi (m)}b_i \pmod m\)

所以\(m \mid a^{\varphi (m)}\prod_{i=1}^{\varphi (m)}b_i-\prod_{i=1}^{\varphi (m)}b_i\)

即\(m \mid (a^{\varphi (m)}-1)\prod_{i=1}^{\varphi (m)}b_i\)

又因为\(\gcd(m,\prod_{i=1}^{\varphi (m)}b_i)=1\)

所以\(m \mid a^{\varphi (m)}-1\)

即\(a^{\varphi (m)} \equiv 1 \pmod m\)

费马小定理

当\(p\)为质数，则\(a^{p-1} \equiv 1 \pmod p\)

证明：因为\(p\)为质数时，\(\varphi(p)=p-1\)

扩展欧拉定理

扩展到不要求互质。

\[ a^c \equiv \begin{cases} a^{c \bmod \varphi(m)} &\gcd(a,m)=1 \\ a^c &\gcd(a,m) \neq 1,c<\varphi(m) \\ a^{\left(c \bmod \varphi(m)\right)+\varphi(m)} &\gcd(a,m) \neq 1,c \geq \varphi(m) \end{cases} \pmod m \]

证明

case 1

当\(\gcd(a,m)=1\)时，由欧拉定理知\(a^{\varphi (m)} \equiv 1 \pmod m\)

我们可以把指数\(c\)拆成\(k \times \varphi(m) + \left(c \bmod \varphi(m)\right)\)，那么\(a^c=\left(a^{\varphi(m)}\right)^k \times a^{c \bmod \varphi(m)}\)，再取模，就得到

\[ a^c \equiv a^{c \bmod \varphi(m)} \pmod m \]

case 2

当\(\gcd(a,m) \neq 1\)且\(c < \varphi(m)\)时，
\[ a^c \equiv a^c \pmod m \]

（无需证明）

case 3

当\(\gcd(a,m) \neq 1\)且\(c\geq \varphi(m)\)时，
\[ a^c\equiv a^{(c \bmod \varphi(m))+\varphi(m)} \pmod m \]

证明：

1.转化

要证明上式，只需证\(a\)的任意一个质因子\(p_i\)满足\({p_i}^c \equiv {p_i}^{(c \bmod \varphi(m))＋\varphi(m)} \pmod{m}\)

1.1 证明转化的正确性

如果上式成立，设\(a\)质因数分解的结果为\(a=p_1^{r_1}p_2^{r_2}p_3^{r_3}\cdots\)，其中\(p_i\)为质因数，\(r_i\)为其对应的指数

根据同余式可乘可推出\(({p_i}^c)^{r_i} \equiv ( {p_i}^{(c \bmod \varphi(m))＋\varphi(m)} )^{r_i} \pmod{m}\)

进而\((p_1^{r_1}p_2^{r_2}p_3^{r_3}\cdots)^{c} \equiv (p_1^{r_1}p_2^{r_2}p_3^{r_3}\cdots)^{(c \bmod \varphi(m))＋\varphi(m)} \pmod{m}\)

发现这就是\(a^c \equiv a^{\left(c \bmod \varphi(m)\right)+\varphi(m)} \pmod m\)

2.证明转化后的式子

那么现在要证明的东西已经转化，考虑如何证得\({p_i}^c \equiv {p_i}^{(c \bmod \varphi(m))＋\varphi(m)} \pmod{m}\)（以下简称\(p_i\)为\(p\)）

2.1 若\(m,p\)互质

问题转化为case 1的情况。为了防止你翻上去，我再推一遍：

\(\gcd(m,p)=1 \Longrightarrow p^{\varphi(m)} \equiv 1 \pmod m\)（欧拉定理）

可以将指数\(c\)拆成\(k \times \varphi(m) + \left(c \bmod \varphi(m)\right)\)，那么\(p^c=(p^{\varphi(m)})^k \times p^{c \bmod \varphi(m)}\)

再对\(m\)取模，就得到\(p^c \equiv (p^{\varphi(m)})^k\times p^{c \bmod \varphi(m)} \equiv 1^k\times p^{c \bmod \varphi(m)} \equiv p^{c \bmod \varphi(m)} \equiv p^{(c \bmod \varphi(m))+\varphi(m)} \pmod m\)

2.2 若\(p,m\)不互质

由于\(p\)为质数，则\(m\)必定\(\geq 2p\)。

设\(m=s\times p^r\)，其中\(r=\lfloor\frac{m}{p}\rfloor\)（看作把\(m\)质因数分解后含有\(p^r\)，剩下的都在\(s\)里，剩下的\(s\)不含因数\(p\)），那么\(\gcd(s,p^r)=\gcd(s,p)=1\)

根据欧拉定理\(p^{\varphi(s)} \equiv 1 \pmod s\)

因为\(s,p^r\)互质，所以\(\varphi(m)=\varphi(s)\times \varphi(p^r)\)（欧拉函数是积性函数），即\(\varphi(s) \mid \varphi(m)\)

结合欧拉定理\(p^{\varphi(s)} \equiv 1 \pmod{s}\)可得

\(p^{\varphi(m)} = (p^{\varphi(s)})^{\varphi(p^r)} \equiv 1^{\varphi(p^r)} = 1 \pmod{s}\)

同时乘以\(q^r\)得到

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

\(m=s\times p^r\)，则\(p^{r+\varphi(m)} \equiv p^r \pmod{m}\)

题设条件\(c\geq \varphi(m)\)，显然\(\varphi(m)\geq r\)

本蒟蒻觉得这一点也不显然，花了好久才证明出\(\varphi(m)\geq r\)……QAQ
下面附上我的证明方法（我觉得应该有更简单的方法）

首先\(\varphi(m)=\varphi(s)\times \varphi(q^r) \geq \varphi(p^r)\)（等号在\(s=1,2\)时取到）

\(\varphi(p^r)=p^r-p^{r-1}=(p-1)\times p^{r-1} \geq p^{r-1}\)（\(p\geq 2\)，等号在\(p=2\)时取到）

数学归纳法\(p^{r-1}\geq r\)：\(r=1\)时显然成立，假设\(r=i\)时\(p^{i-1}\geq i\)成立，可推知\(p^{i}=p\times p^{i-1}\geq 2\times p^{i-1}=p^{i-1}+p^{i-1}\geq p^{i-1}+1=i+1\)成立，因此\(p^{r-1}\geq r\)对任意的\(p,r\in \mathbb{Z},p\geq 2,r\geq 1\)成立

把上面所有的不等号串起来，就是\(\varphi(m)\geq r\)

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

记\(f(x)=x\bmod m\;(x\geq \varphi(m))\)，上式表明：对于任意的正整数\(x\)，\(f(x+\varphi(m))=f(x)\)。反过来\(f(x)=f(x-\varphi(m))\)，但要注意定义域：此时\(x\)要满足\(x-\varphi(m)\geq \varphi(m)\)，即\(x\geq 2\varphi(m)\)。

如果要计算\(f(c)\)，可以递推上面那个式子，每次让\(c-=\varphi(m)\)，但只有\(c\geq 2\varphi(m)\)时才可以这样操作。

我们知道，如果递推条件改成\(c\geq \varphi(m)\)，显然最后递推得到的值为\(c\bmod \varphi(m)\)。但现在条件是\(c\geq 2\varphi(m)\)，发现递推条件相差为\(\varphi(m)\)，\(c\geq 2\varphi(m)\)比\(c\geq \varphi(m)\)少减一次\(\varphi(m)\)。所以只需把这一次\(\varphi(m)\)加回来就好了，即\(f(c)=f((c\bmod \varphi(m))+\varphi(m))\)，也就是
\[ a^c\equiv a^{(c \bmod \varphi(m))+\varphi(m)} \pmod m \]

用途

再也不用担心指数爆炸了！！指数也可以取模了

题目

BZOJ3884（推公式）

BZOJ4869（+线段树）

---

参考CSDN博主「CaptainHarryChen」的证明思路。十分感谢。

原文链接：https://blog.csdn.net/can919/article/details/82318115