挑战≈ 16 分钟未开始

欧拉定理

核心概念

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

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

它是费马小定理的推广:当 $n=p$ 为质数时 $\varphi(p)=p-1$ ,即化为 $a^{p-1}\equiv1\pmod p$ 。

用途——对合数模降幂:当 $\gcd(a,n)=1$ 时, $a^k \equiv a^{\,k \bmod \varphi(n)} \pmod n$ ,可把巨大的指数先对 $\varphi(n)$ 取模。

直观理解 · 动手试试

费马小定理只能在"质数模"下降幂,而现实里模数常是合数。欧拉定理把那个"回到 $1$ 的周期"从 $p-1$ 推广为 $\varphi(n)$ :只要底数与模互质, $a^{\varphi(n)}$ 就回到 $1$ ,幂便以 $\varphi(n)$ 为周期循环。

于是求"某大数的某高次幂模合数"的标准流程是:① 确认底数与模互质;② 算出 $\varphi(n)$ ;③ 把指数对 $\varphi(n)$ 取模;④ 算余下的小幂。一个看似吓人的 $7^{222} \bmod 10$ ,几步就解决。

欧拉定理

7^k mod 10(φ(10) = 4)

k=1

k=2

k=3

k=4

gcd(7, 10) = 1,所以 7^φ(10) = 7⁴ ≡ 1 (mod 10)。指数可先对 φ(10) = 4 取模。

底数 a7

模 n10

当底数与模互质时,a 的 φ(n) 次幂回到 1(绿色),幂以 φ(n) 为周期循环——这是费马小定理的推广。

例题 1对合数模降幂

求 $7^{222}$ 除以 $10$ 的余数。

▸查看解答步骤

答: 余 9

例题 2指数整除周期

求 $3^{2024}$ 的个位数字。

▸查看解答步骤

答: 末位 1

即时练习

要对模 $10$ 用欧拉定理降幂,需要先求 $\varphi(10)$ 。它等于多少?

$\varphi(10)=4$ 。

$7^{222}$ 除以 $10$ 的余数是多少?

$\varphi(10)=4$ , $222\equiv2\pmod4$ , $7^2=49\equiv9$ 。

$3^{2024}$ 的个位数字是多少?

$\varphi(10)=4$ , $2024\equiv0\pmod4$ , $3^{2024}\equiv3^4\equiv1\pmod{10}$ 。

费马小定理是欧拉定理在模为质数时的特例。

$n=p$ 时 $\varphi(p)=p-1$ ,欧拉定理化为 $a^{p-1}\equiv1\pmod p$ 。

使用欧拉定理 $a^{\varphi(n)}\equiv1\pmod n$ 的前提是?

\gcd(a,n)=1

n

是质数

a

是偶数

a>n

只需底数与模互质, $n$ 可以是合数。

易错点

底数与模不互质仍套用。 如 $\gcd(2,10)=2\neq1$ ,不能直接用欧拉定理,需另想办法(如分别对 $2$ 、 $5$ 的幂讨论)。
指数对 $n$ 取模。 应对 $\varphi(n)$ 取模,不是对 $n$ 。
$\varphi(n)$ 算错。 先正确求出 $\varphi(n)$ 再降幂,这一步错则全错。

下一步

前置知识点

欧拉函数

接下来学习

中国剩余定理

核心概念

直观理解 · 动手试试

7k mod 10(φ(10) = 4)

即时练习

易错点

下一步

7^k mod 10(φ(10) = 4)