Euler’s Theorem: If a and n are positive integers with \(\gcd(a, n) = 1\), then:

\(a^{\varphi(n)} \equiv 1 \pmod{n}\)

Here, \(\varphi(n)\) is Euler’s totient function, which counts the number of positive integers up to n that are coprime with n.

欧拉定理：若 \(a, n\) 为正整数，且 a 与 n 互质（即 \(\gcd(a, n)=1\)），则：
\(a^{\varphi(n)} \equiv 1 \pmod{n}\)
其中 \(\varphi(n)\) 为欧拉函数，表示不超过 n 且与 n 互质的正整数的个数。

补充说明（Key Notes）

1. 前提条件：a 与 n 必须互质（\(\gcd(a,n)=1\)），否则定理不成立。
2. 特殊情况：当 n 为质数 p 时，\(\varphi(p)=p-1\)，此时欧拉定理退化为费马小定理：\(a^{p-1} \equiv 1 \pmod{p}\)（其中 a 不是 p 的倍数）。

欧拉函数 \(\boldsymbol{\varphi(n)}\) 超简明计算总结

定义：\(\varphi(n)\) 表示 \(1\sim n\) 里，和 n最大公约数为 1 的整数个数。

计算公式（直接背）

设 p 为质数

1. 单个质数\(\varphi(p)=p-1\)例：\(\varphi(5)=4,\ \varphi(7)=6\)
2. 质数的次方 \(p^k\)\(\boldsymbol{\varphi(p^k)=p^k – p^{k-1}}\)易错：不能写成 \((\varphi(p))^k\)例子：

\(\varphi(5^3)=125-25=\boldsymbol{100}\)

\(\varphi(5^2)=25-5=\boldsymbol{20}\)

\(\varphi(5^1)=5-1=\boldsymbol{4}\)

3. 两个互质的数相乘若 \(\gcd(a,b)=1\)，则\(\varphi(ab)=\varphi(a)\cdot\varphi(b)\)例：\(\varphi(15)=\varphi(3\times5)=\varphi(3)\varphi(5)=2\times4=8\)
4. 万能总公式（任意自然数）先把 n 分解质因数：\(n=p_1^{k_1}p_2^{k_2}\dots p_m^{k_m}\)\(\boldsymbol{\varphi(n)=n\cdot\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)\dots\left(1-\dfrac{1}{p_m}\right)}\)

手把手算 3 道典型题

1. 算 \(\varphi(125)=\varphi(5^3)\)

\(\varphi(125)=125\times\left(1-\dfrac15\right)=100\)

2. 算 \(\varphi(12)=\varphi(2^2\times3)\)\(\varphi(12)=12\times\left(1-\dfrac12\right)\times\left(1-\dfrac13\right)=4\)
3. 算 \(\varphi(7)\)（质数）\(\varphi(7)=7-1=6\)
4. \(\begin{align*} \varphi(5^1)&=5^1-5^0=5-1=4\\ \varphi(5^2)&=5^2-5^1=25-5=20\\ \varphi(5^3)&=125-25=100 \end{align*}\)

如果你要求$$a^n \pmod m$$an(modm)

并且 $\gcd(a,m)=1$gcd(a,m)=1，就可以把指数 $n$n 先对 $\varphi(m)$φ(m) 取模，再去算。更准确地说，$$a^n \equiv a^{\,n \bmod \varphi(m)} \pmod m$$an≡anmodφ(m)(modm)

但要注意一个小细节：
如果 $n$n 本身已经不小于 $\varphi(m)$φ(m)，你通常可以写成$$a^n = a^{k\varphi(m)+r} \equiv (a^{\varphi(m)})^k a^r \equiv a^r \pmod m$$an=akφ(m)+r≡(aφ(m))kar≡ar(modm)

其中 $0 \le r < \varphi(m)$0≤r<φ(m)。

什么时候能用

必须满足 aaa 和 mmm 互素。
如果 $\gcd(a,m)\ne 1$gcd(a,m)=1，这个定理一般不能直接用。

---

和费马小定理的关系

费马小定理是欧拉定理的特例：

当 $m=p$m=p 是素数时，$\varphi(p)=p-1$φ(p)=p−1，所以$$a^{p-1}\equiv 1\pmod p \qquad (\gcd(a,p)=1)$$ap−1≡1(modp)(gcd(a,p)=1)

这就是费马小定理。

---

例子

求$$7^{100} \pmod{20}$$7100(mod20)

因为 $\gcd(7,20)=1$gcd(7,20)=1，且$$\varphi(20)=8$$φ(20)=8

所以$$7^{100}\equiv 7^{100\bmod 8}=7^4 \pmod{20}$$7100≡7100mod8=74(mod20)

而$$7^2=49\equiv 9,\quad 7^4\equiv 9^2=81\equiv 1 \pmod{20}$$72=49≡9,74≡92=81≡1(mod20)

所以答案是$$7^{100}\equiv 1\pmod{20}$$7100≡1(mod20)

---

你做题时的标准套路

1. 先看能不能分解模数。
2. 算 $\varphi(m)$φ(m)。
3. 检查底数和模数是否互素。
4. 用 $a^{\varphi(m)}\equiv 1\pmod m$aφ(m)≡1(modm) 降幂。
5. 需要的话再结合 CRT（中国剩余定理）分别处理。

---

真题练习

Q1 2024 AMC 10B Problems/Problem 18
How many different remainders can result when the th power of an integer is divided by ?

Q2 2011 AMC 10B Problems/Problem 23

What is the hundreds digit of 

Q2 用二项式定理更简单，先用欧拉数做吧，以后会再重做的

Q3 2025 AMC 12B Problems/Problem 9

What is the tens digit of ?

欧拉降幂

Q4 2010 AMC 12A Problems/Problem 23

The number obtained from the last two nonzero digits of  is equal to . What is ?

求 \(90!\) 去掉末尾所有 0 之后的最后两位数字

考点：阶乘末尾消零、勒让德质因数指数、欧拉定理降幂、模运算、中国剩余定理，AMC10 高频难题

Q1 B 2

Q2 D 6

Q3 C5

Q4 A 12