挑战≈ 16 分钟未开始

费马小定理

核心概念

费马小定理:设 $p$ 是质数。

若 $\gcd(a, p) = 1$ ,则 $a^{p-1} \equiv 1 \pmod p$ ;
对任意整数 $a$ ,都有 $a^{p} \equiv a \pmod p$ 。

用途:把巨大的幂在模 $p$ 下迅速降次——指数可以先模 $p-1$ (当底数与 $p$ 互质时)。

例:模 $7$ 时,只要 $7\nmid a$ ,就有 $a^6 \equiv 1$ ,于是 $a^n \equiv a^{\,n \bmod 6}$ 。

直观理解 · 动手试试

费马小定理是同余里的"降幂神器"。直接算 $a^{100}$ 是天文数字,但在模 $p$ 的世界里, $a^{p-1}$ 就回到了 $1$ ,相当于每 $p-1$ 步幂就"绕一圈"。于是天大的指数 $n$ ,只要看它除以 $p-1$ 的余数即可。

它和"幂的循环节"是同一回事的精确版:循环节的长度一定整除 $p-1$ 。所以遇到"求某大数模质数"的题,第一反应就是:底数与 $p$ 互质吗?互质就用费马小定理把指数模 $p-1$ ,问题瞬间缩小。

费马小定理

2ⁿ mod 7（n = 1 … 6）

n=1

n=2

n=3

n=4

n=5

n=6

gcd(2, 7) = 1，所以 2⁶ ≡ 1 (mod 7)。求大幂时,指数可先模 6。

底数 a2

质数 p7

当底数与质数 p 互质时,a 的 (p−1) 次幂必回到 1(绿色)。这让任意大的指数都能先对 p−1 取模,瞬间降幂。

例题 1用费马小定理降幂

求 $2^{100}$ 除以 $7$ 的余数。

▸查看解答步骤

答: 余 2

例题 2对一切 a 成立的形式

说明:对任意整数 $a$ , $a^5 - a$ 都能被 $5$ 整除。

▸查看解答步骤

答: 恒成立

即时练习

由费马小定理, $a^{6} \pmod 7$ 在 $\gcd(a,7)=1$ 时等于多少?

$a^{7-1}=a^6\equiv1\pmod7$ 。

$2^{100}$ 除以 $7$ 的余数是多少?

$2^6\equiv1$ , $100\equiv4\pmod6$ , $2^4=16\equiv2\pmod7$ 。

$3^{100}$ 除以 $7$ 的余数是多少?

$3^6\equiv1\pmod7$ , $100\equiv4\pmod6$ , $3^4=81\equiv81-77=4\pmod7$ 。

对任意整数 $a$ , $a^7 - a$ 一定能被 $7$ 整除。

费马小定理 $a^7\equiv a\pmod7$ ,故 $7\mid(a^7-a)$ 。

使用费马小定理 $a^{p-1}\equiv1\pmod p$ 的前提是?

p

为质数且

\gcd(a,p)=1

a

为质数

p

为偶数

a > p

要求模 $p$ 为质数,且底数 $a$ 与 $p$ 互质。

易错点

底数与 $p$ 不互质仍用第一式。 若 $p\mid a$ ,则 $a^{p-1}\not\equiv1$ ;此时用 $a^p\equiv a$ 的形式。
指数模错数。 互质时指数模的是 $p-1$ ,不是 $p$ 。
模数不是质数也套用。 费马小定理要求模为质数;合数模需用欧拉定理。

下一步

前置知识点

同余初步

接下来学习

进位制

核心概念

直观理解 · 动手试试

2n mod 7（n = 1 … 6）

即时练习

易错点

下一步

2ⁿ mod 7（n = 1 … 6）