## 欧拉定理 前置知识：[欧拉函数](https://oi-wiki.org/math/number-theory/euler/) 若 $\gcd(a,n)=1$ ，则 $a^{\varphi(n)}\equiv 1\pmod n$。 ### 证明 设 $n$ 的简化剩余系为 $\left \{ \overline{r_1},\overline{r_2},\overline{r_3},\cdots,\overline{r_{\varphi(n)}} \right \} $ 若 $a\cdot r_i\equiv a\cdot r_j\pmod n$ ，则 $a\cdot(r_i-r_j)\equiv 0 \pmod n$ ，因为 $\gcd(a,n)=1$ ，所以 $r_i\equiv r_j\pmod n$ 故当 $r_i\ne r_j\pmod n$ 时，$a\cdot r_i\ne a\cdot r_j\pmod p$（注：这些不等于都是取模后的，我太逊了打不出来qwq） 则 $\left \{ \overline{r_1},\overline{r_2},\overline{r_3},\cdots,\overline{r_{\varphi(n)}} \right \} =\left \{ \overline{a\cdot r_1},\overline{a\cdot r_2},\overline{a\cdot r_3},\cdots,\overline{a\cdot r_{\varphi(n)}} \right \}$ 所以 $a^{\varphi(n)}\cdot r_1\cdot r_2\cdot r_3\cdots r_{\varphi(n)}\equiv (a\cdot r_1)\cdot(a\cdot r_2)\cdot(a\cdot r_3)\cdots(a\cdot r_{\varphi(n)})\equiv r_1\cdot r_2\cdot r_3\cdots r_{\varphi(n)}\pmod n$ 两边同时约掉 $r_1\cdot r_2\cdot r_3\cdots r_{\varphi(n)}$ ，故 $a^{\varphi(n)}\equiv 1\pmod n$ ## 扩展欧拉定理 $$ a^b\equiv\begin{cases}a^{b\mod\varphi(n)} &\gcd(a,n)=1 \\a^b &\gcd(a,n)\neq1\land b<\varphi(n) \\ a^{b\mod\varphi(n)+\varphi(n)} &\gcd(a,n)\neq1\land~b\geq\varphi(n)\end{cases}\pmod n $$ ### 证明 第一行：设 $b=q\times\varphi(n)+r,0\le r<\varphi(n)$ 即 $r=b\mod \varphi(n)$ 所以 $a^b\equiv a^{q\times\varphi(n)+r}\equiv (a^{\varphi(n)})^q\times a^r\equiv a^r\equiv a^{b\mod \varphi(n)}$ 第二行显然成立 第三行比较麻烦，我太逊了不会证，可参考： - [（扩展）欧拉定理学习笔记 | Bill Yang's Blog](http://blog.bill.moe/euler-theorem-notes/#证明)，用积性函数证明的。 - [欧拉定理 & 费马小定理 - OI Wiki](https://oi-wiki.org/math/number-theory/fermat/#_6)，也是比较类似的方法证明的。 ## 费马小定理 若 $p$ 为质数，对于任意 $\gcd(a, p)=1$ ，满足 $a^{p-1}\equiv 1\pmod p$，一般用于求逆元中。 ### 证明 带入欧拉定理即可。 Loading... ## 欧拉定理 前置知识：[欧拉函数](https://oi-wiki.org/math/number-theory/euler/) 若 $\gcd(a,n)=1$ ，则 $a^{\varphi(n)}\equiv 1\pmod n$。 ### 证明 设 $n$ 的简化剩余系为 $\left \{ \overline{r_1},\overline{r_2},\overline{r_3},\cdots,\overline{r_{\varphi(n)}} \right \} $ 若 $a\cdot r_i\equiv a\cdot r_j\pmod n$ ，则 $a\cdot(r_i-r_j)\equiv 0 \pmod n$ ，因为 $\gcd(a,n)=1$ ，所以 $r_i\equiv r_j\pmod n$ 故当 $r_i\ne r_j\pmod n$ 时，$a\cdot r_i\ne a\cdot r_j\pmod p$（注：这些不等于都是取模后的，我太逊了打不出来qwq） 则 $\left \{ \overline{r_1},\overline{r_2},\overline{r_3},\cdots,\overline{r_{\varphi(n)}} \right \} =\left \{ \overline{a\cdot r_1},\overline{a\cdot r_2},\overline{a\cdot r_3},\cdots,\overline{a\cdot r_{\varphi(n)}} \right \}$ 所以 $a^{\varphi(n)}\cdot r_1\cdot r_2\cdot r_3\cdots r_{\varphi(n)}\equiv (a\cdot r_1)\cdot(a\cdot r_2)\cdot(a\cdot r_3)\cdots(a\cdot r_{\varphi(n)})\equiv r_1\cdot r_2\cdot r_3\cdots r_{\varphi(n)}\pmod n$ 两边同时约掉 $r_1\cdot r_2\cdot r_3\cdots r_{\varphi(n)}$ ，故 $a^{\varphi(n)}\equiv 1\pmod n$ ## 扩展欧拉定理 $$ a^b\equiv\begin{cases}a^{b\mod\varphi(n)} &\gcd(a,n)=1 \\a^b &\gcd(a,n)\neq1\land b<\varphi(n) \\ a^{b\mod\varphi(n)+\varphi(n)} &\gcd(a,n)\neq1\land~b\geq\varphi(n)\end{cases}\pmod n $$ ### 证明 第一行：设 $b=q\times\varphi(n)+r,0\le r<\varphi(n)$ 即 $r=b\mod \varphi(n)$ 所以 $a^b\equiv a^{q\times\varphi(n)+r}\equiv (a^{\varphi(n)})^q\times a^r\equiv a^r\equiv a^{b\mod \varphi(n)}$ 第二行显然成立 第三行比较麻烦，我太逊了不会证，可参考： - [（扩展）欧拉定理学习笔记 | Bill Yang's Blog](http://blog.bill.moe/euler-theorem-notes/#证明)，用积性函数证明的。 - [欧拉定理 & 费马小定理 - OI Wiki](https://oi-wiki.org/math/number-theory/fermat/#_6)，也是比较类似的方法证明的。 ## 费马小定理 若 $p$ 为质数，对于任意 $\gcd(a, p)=1$ ，满足 $a^{p-1}\equiv 1\pmod p$，一般用于求逆元中。 ### 证明 带入欧拉定理即可。 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏