欧拉定理与费马小定理

算 $2^{100} \bmod 13$ 时，把一百个 $2$ 乘开再取模当然不行。欧拉定理和费马小定理看起来只是在说「某个幂次同余 $1$」，真正要回答的却是：指数太大时，幂可以怎么降，以及什么时候不能降。下面把定理、初等证明、手算和代码放在一起。

一次同余关心的是乘法能不能反过来；这两个定理关心的是乘法重复很多次以后会不会回到 $1$。两件事在互素时碰到一起：能回到 $1$，就有逆，指数也才能安全地缩短。

欧拉函数先记清

对正整数 ，欧拉函数 表示 里与 互素的个数。例如 ，，（只有 ），（）。

常用公式：若 $n=p_1^{k_1}\cdots p_r^{k_r}$ 是素因子分解，则

素数 $p$ 时 $\varphi(p)=p-1$。素幂更好记：$\varphi(p^k)=p^k-p^{k-1}$，也就是丢掉那些被 整除的数。两个互素的正整数还满足 。

手算几个常用值，后面降幂会反复用到：

$\varphi(12)=4$ 容易算错。$12=2^2\cdot 3$，所以 $\varphi(12)=12\cdot(1-1/2)\cdot(1-1/3)=4$，既约剩余只有 。再算一个：，。后面降幂，指数要模的就是这个 。它不是「循环节的最小长度」，只是一个保证能整除循环节的上界。同一个模下，不同底数的真实周期可以不同，但都整除 。

两个定理

欧拉定理。 若 $\gcd(a,n)=1$，则

费马小定理。 若 $p$ 是素数且 $p\nmid a$，则

费马是欧拉的特例：素数模上 $\varphi(p)=p-1$，而 $p\nmid a$ 正好就是 $\gcd(a,p)=1$。有时也写成 $a^p\equiv$，这一式对 也成立，因为两边都是 。后一种写法看起来更宽，却不能推广到合数模，后面易错一节会对照。

两个定理都要求「底数和模互素」。缺了这一条，$a^{\varphi(n)}\equiv 1$ 可以立刻失败。互素保证 $a$ 在模 $n$ 下可逆，乘法才像在一个封闭的集合里打转，而不是慢慢掉进被 $n$ 的素因子吸住的轨道。

为什么成立：剩余系相乘

证明不必上群论。核心是：与 $n$ 互素的剩余，乘上一个也与 $n$ 互素的 $a$，只是被重新排了一遍。

设 $n>1$，把模 $n$ 下与 $n$ 互素的剩余列出来，共 $\varphi(n)$ 个：

这就是一组既约剩余系。因为 $\gcd(a,n)=1$，每个 $ar_i$ 仍与 $n$ 互素：公共素因子既不能来自 $a$，也不能来自 $r_i$。它们还两两不同余：若 ，则 ；再由 得到 ，也就是 。于是

也是一组既约剩余系，只是顺序不同。两边各自相乘，模 $n$ 应当相等：

乘积 $P=r_1\cdots r_{\varphi(n)}$ 本身也与 $n$ 互素，因而有逆。两边同乘 $P^{-1}$，就得到

素数模时，既约剩余系就是 $1,2,\dots,p-1$，同一论证给出 $a^{p-1}\equiv 1$。

用 $n=10$、$a=3$ 把重排看清楚。既约剩余是 $1,3,7,9$。乘 $3$ 之后变成

也就是 $3,9,1,7$，还是那四个数。两边相乘：

右边乘积是 $189\equiv 9$，与 $10$ 互素，可以约掉，留下 $3^4\equiv 1\pmod{10}$。这就是欧拉定理的一个具体实例。

群论的说法更短：模 $n$ 的既约剩余构成乘法群，阶为 $\varphi(n)$，于是每个元素的阶整除群阶。上面的相乘论证，其实就是在初等语言里把这件事写出来。不必先学群，也能把「为什么幂会回到 $1$」讲完。关键步骤只有三件：乘 $a$ 仍落在既约剩余里、乘完只是重排、乘积 $P$ 可约。任何一步依赖 $\gcd(a,n)=1$，所以前提不是装饰。

降幂：指数先模 $\varphi(n)$

若 $\gcd(a,n)=1$ 且 $k\ge 0$，由欧拉定理立刻有

其中 $r=k\bmod\varphi(n)$。也就是说，底数先收进 $[0,n)$，指数再模 $\varphi(n)$。注意 $r$ 取在 到 之间；若 恰好是 的倍数，余数是 ，这时应回到 ，不要写成 再忘了核对前提。

更细一点：真正最小的循环节是 $a$ 模 $n$ 的阶，记作 $\mathrm{ord}_n(a)$，它整除 $\varphi(n)$，但不一定等于 $\varphi(n)$。手算时用 已经够把指数压下来；若还想再短，可以继续试 的因子。竞赛里除非明确要最小阶，否则不必硬找。

例一：费马降幂

算 $2^{100}\bmod 13$。$13$ 是素数且不整除 $2$，所以 $2^{12}\equiv 1\pmod{13}$。

验算小的：$2^4=16\equiv 3$，对。若愿意再缩，会发现 $2^{12}$ 的阶其实是 $12$ 本身，这里已经不能更短。

再算一个稍大的：$5^{33}\bmod 17$。$17$ 是素数，$5$ 不被它整除，$\varphi(17)=16$。

指数多出来的正好是 $1$，结果就是底数自己。这类题如果不先模 $16$，很容易在中间平方时算乱。

例二：合数模用欧拉

算 $3^{100}\bmod 10$。$\gcd(3,10)=1$，$\varphi(10)=4$，故 。

个位是 $1$，和 $3$ 的幂循环 $3,9,7,1$ 一致。这就是「求一个数的个位」最常见的做法：模 $10$，再用 $\varphi(10)=4$ 看循环。

再看 $7^{222}\bmod 15$。$\gcd(7,15)=1$，$\varphi(15)=8$，所以 。

$7^2=49\equiv 4$，$7^4=(7^2)^2\equiv 16\equiv 1$。等等， 已经是 了？再乘一次核对：，，确实 。于是阶是 而不是 ，可以继续降：

欧拉给出合法的上界，具体数字还可能更小。先用 $\varphi(n)$ 保证正确，再观察中间幂是否提前回到 $1$，两步都不矛盾。

例三：指数余 $0$ 时别写成 $a^0$

算 $7^{12}\bmod 13$。$\varphi(13)=12$，指数恰好整除。正确结论是 $7^{12}\equiv 1\pmod{13}$，不是 碰巧对了就以为规则是「余 等于 」。若换成 本身，那是另一道题：指数已经是 ，不必再用定理。

差别在「谁的 $0$」。$k=0$ 是原指数，规定 $a^0=1$（通常还要求 $a$ 与模的关系另说）。$k\bmod\varphi(n)=0$ 且 ，表示原指数是 的正倍数，应当用 。写代码时更稳妥的做法是：先保证指数为正，再取 ；若取完是 ，用 而不是 。

例四：末两位

求 $7^{100}$ 的末两位，就是 $7^{100}\bmod 100$。$\gcd(7,100)=1$，，于是

余下的 $7^{20}$ 再用快速幂，不必碰「一百个 $7$ 相乘」。末三位同理，模改成 $1000$。模数变大时，$\varphi(n)$ 仍然只负责缩指数，真正的乘法次数交给二进制平方。

模逆：费马倒过来就是除法

$\gcd(a,n)=1$ 时，$ax\equiv 1\pmod n$ 有唯一解，这个解叫 $a$ 模 $n$ 的逆元。欧拉定理直接给出一个显式公式：

所以

素数模上就是大家更熟的

例如求 $3$ 模 $7$ 的逆：$3^{5}=243$。$243\div 7=34\cdot 7+5$，故 。验算 。

合数模同样能用。求 $3$ 模 $10$ 的逆：$\varphi(10)=4$，于是 $3^{-1}\equiv 3^{3}=27\equiv 7\pmod{10}$。验算 。求 模 的逆：，故 。前面已经算过 ，所以 。，，于是逆是 。验算 。

有了逆，除法就变成乘法。例如解 $3x\equiv 4\pmod 7$：先取 $3^{-1}\equiv 5$，再 $x\equiv 5\cdot 4=20\equiv 6\pmod 7$。这只覆盖互素、因而恰好一解的情形。分数同余也一样： 应读成 ，不是把整数除法的商硬塞进去。一般模数上，扩展欧几里得往往比快速幂更省事，也不依赖先算出 。费马 / 欧拉这条路的价值在于：当你已经在做大指数幂，或者模是素数、 很好算时，求逆可以和降幂用同一套快速幂。一次同余在不互素时有几个解、怎么找特解，是另一篇文章的事，这里不展开。

Python 快速幂

降幂把指数从 $k$ 收到 $\varphi(n)$ 量级，但 $\varphi(n)$ 本身仍可能很大。二进制快速幂把乘法次数降到 $O(\log k)$。想法是把指数写成二进制。以 $3^{13}\bmod 10$ 为例，，于是

只要不断平方得到 $3,3^2,3^4,3^8$，再按比特位拣出来相乘。每一步都立刻取模，中间数不会涨起来：

Python 自带的 pow(a, k, n) 就是这件事，竞赛里直接用即可。自己写一遍，是为了看清：每次平方、遇到奇数位再乘一次，中间结果始终收在模 $n$ 里。不要先算完 $a^k$ 再 % n，那会在大指数时把整数撑得过大，也失去取模的意义。

有了 $\varphi(n)$，欧拉降幂可以写成：

euler_pow 里对「余数为 $0$」的处理，对应前面例三：指数是 $\varphi(n)$ 的正倍数时，应落到 $a^{\varphi(n)}\equiv 1$，而不是误用 $a^0$。euler_phi 按素因子筛，时间大约是 ，对普通竞赛里的模数够用；若 到 以上，需要先分解再套公式。

易错：$a$ 与 $n$ 不互素

定理的前提是 $\gcd(a,n)=1$。少检查这一条，降幂会算错，逆元也会不存在。这是这两个定理最常见的误用。

直接套公式会错

$2$ 与 $6$ 不互素，$\varphi(6)=2$，但

$2$ 的幂模 $6$ 只能是 $2$ 或 $4$，永远到不了 $1$。所以不存在 $2$ 模 $6$ 的逆，也不能写 $2^k\equiv 2^{k<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>}$。若有人把 收成 ，得到 ，而真值是 ，错得干净。

再看 $4^{2}\bmod 6$：$4^2=16\equiv 4$，而 $4^{\phi (6)}=4^2\equiv 4\mathrm{\ne }1$。同一类错误。根子在于：乘 不再是既约剩余系上的重排。模 的既约剩余只有 ，里面根本没有 。证明的第一步就已经走不下去。

再举一个竞赛里更像真题的：求 $6^{10}\bmod 8$。$\varphi(8)=4$，若误用欧拉会去算 $6^{10\bmod 4}=6^{2}=36\equiv 4\pmod 8$。真值要直接看幂次：，，，之后一直是 。所以 ，不是 。原因也很具体：，每次多一个因子 ，而 ，三次就补齐，幂被 整除。互素检查一旦漏掉，答案可以错到另一个剩余类。

费马那条「对所有 $a$」的写法

$a^p\equiv a\pmod p$ 对素数 $p$ 确实恒成立，包括 $p\mid a$。不要把它推广成 $a^n\equiv a($：合数里这叫卡迈克尔条件，大多数 不满足。例如 。再如 ，，故 。看到「费马对所有 都对」就往合数上搬，是第二类常见笔误。

指数可以降，但模的不是 $\varphi(n)$

有时 $\gcd(a,n)>1$，仍可能对某个更小的指数出现循环，那是 $\lambda(n)$（卡迈克尔函数）或直接观察幂次序列的事，不能默认模 $\varphi(n)$。例如 $2$ 模 $8$：幂次是 $$，从某次起钉在 ，谈不上模 的循环。竞赛里更常见的安全策略是：

• 先算 $d=\gcd(a,n)$。
• $d=1$，才用欧拉 / 费马降指数。
• $d>1$，不要降指数；直接快速幂，或先把 $n$ 拆成素因子幂再中国剩余定理拼回来。拆开之后，在每个素幂上单独判断：要么已经互素，要么幂次高到把这个素因子吃完。

$a$ 是 $n$ 的倍数时更简单：$a^k\equiv 0\pmod n$（$k\ge 1$）。例如 ，这时谈 没有意义。

求 $\varphi(n)$ 本身也会错

降幂正确的前提是 $\varphi(n)$ 算对。$n=p^k$ 时是 $p^k-p^{k-1}$，不是 。，不是 ；，而 。把合数模当成素数模，是另一类常见笔误。 不是 ，，若误用 也能凑到 ，但中间降幂的余数会偏。

还有一个隐蔽错误：指数很大、却以字符串或递推形式给出时，要先确认底数与模互素，才能把指数模 $\varphi(n)$。题目若写成求 $a^b\bmod n$ 且 $b$ 有上百位，标准做法是在互素时算 $b\bmod\varphi(n)$；不互素就不能先缩 。

和一次同余的边界

互素时，欧拉定理给出逆，于是 $ax\equiv b\pmod n$ 变成一次乘法。不互素时，逆不存在，方程仍可能有解，判别靠 $\gcd(a,n)$ 是否整除 $b$，解法走扩展欧几里得。那是线性同余自己的故事。欧拉 / 费马管的是乘法群里的幂：能降的指数、能写出的逆、以及前提失效时为什么必须停手。

手算时先问互素，再问 $\varphi(n)$，最后才快速幂。这三步分开，定理就不会被当成万能的「指数随便模一模」。幂回到 $1$，是互素剩余系被重新排列之后的必然结果；一旦底数踏出这个集合，排列不再发生，公式也就到此为止。