费马小定理

字数 2401 2025-11-17 20:46:31

费马小定理

费马小定理是数论中关于素数模运算的一个基本定理。它表述为：如果 $p$ 是一个素数，且整数 $a$ 不是 $p$ 的倍数（即 $p \nmid a$），那么：

\[a^{p-1} \equiv 1 \pmod{p} \]

这个定理揭示了素数模下幂运算的周期性规律，是许多数论问题和密码学应用的基础。

1. 定理的直观理解
考虑素数 $p = 5$ 和整数 $a = 2$。计算 $2^{5-1} = 16$，而 $16 \div 5 = 3$ 余 $1$，因此 $16 \equiv 1 \pmod{5}$，符合定理。本质上，当 $a$ 与 $p$ 互质时，模 $p$ 的剩余类 $\{1, 2, \dots, p-1\}$ 在乘以 $a$ 后会重新排列，因此所有数的乘积满足：

\[a^{p-1} \cdot (1 \cdot 2 \cdots (p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod{p} \]

由于每个剩余类与 $p$ 互质，可约去公共乘积，得到 $a^{p-1} \equiv 1 \pmod{p}$。

2. 定理的证明

方法一（剩余类重排）：
集合 $S = \{1, 2, \dots, p-1\}$ 是模 $p$ 的简化剩余系。由于 $p \nmid a$，集合 $aS = \{a \cdot 1, a \cdot 2, \dots, a \cdot (p-1)\}$ 也是模 $p$ 的简化剩余系（因为若 $a i \equiv a j \pmod{p}$，则 $i \equiv j \pmod{p}$）。因此：

\[ \prod_{k=1}^{p-1} (a \cdot k) \equiv \prod_{k=1}^{p-1} k \pmod{p} \]

即：

\[ a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p} \]

由于 $(p-1)!$ 与 $p$ 互质，可两边约去，得 $a^{p-1} \equiv 1 \pmod{p}$。

方法二（数学归纳法）：
对 $a$ 进行归纳。基础情况 $a = 1$ 显然成立。假设 $a^{p-1} \equiv 1 \pmod{p}$，考虑 $(a+1)^p$。由二项式定理：

\[ (a+1)^p = \sum_{k=0}^{p} \binom{p}{k} a^k \]

当 $1 \leq k \leq p-1$ 时，二项式系数 $\binom{p}{k} = \frac{p!}{k!(p-k)!}$ 可被 $p$ 整除（因为分子含 $p$，分母不含 $p$），故：

\[ (a+1)^p \equiv a^p + 1 \pmod{p} \]

由归纳假设 $a^p \equiv a \pmod{p}$，代入得 $(a+1)^p \equiv a + 1 \pmod{p}$，即 $(a+1)^{p-1} \equiv 1 \pmod{p}$。

3. 应用示例

计算模幂：求 $3^{100} \mod 7$。由于 $7$ 是素数且 $7 \nmid 3$，费马小定理给出 $3^6 \equiv 1 \pmod{7}$。因为 $100 = 6 \cdot 16 + 4$，所以：

\[ 3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 3^4 = 81 \equiv 4 \pmod{7} \]

结果为 $\boxed{4}$。

素性测试：
费马小定理的逆命题不总是成立（例如 $2^{340} \equiv 1 \pmod{341}$，但 $341 = 11 \times 31$ 是合数），但可用于初步筛选。若对某个 $a$ 有 $a^{n-1} \not\equiv 1 \pmod{n}$，则 $n$ 一定是合数。

4. 推广：欧拉定理
费马小定理可推广到合数模。欧拉定理指出：若 $a$ 与 $n$ 互质，则：

\[a^{\phi(n)} \equiv 1 \pmod{n} \]

其中 $\phi(n)$ 是欧拉函数，表示不超过 $n$ 且与 $n$ 互质的正整数个数。当 $n = p$ 为素数时，$\phi(p) = p-1$，即得费马小定理。

5. 密码学中的应用
费马小定理是RSA加密的核心。在RSA中，选择两个大素数 $p, q$，计算 $n = pq$ 和 $\phi(n) = (p-1)(q-1)$。公钥指数 $e$ 满足 $\gcd(e, \phi(n)) = 1$，私钥指数 $d$ 满足 $e d \equiv 1 \pmod{\phi(n)}$。加密 $c \equiv m^e \pmod{n}$，解密时：

\[c^d \equiv m^{e d} \equiv m^{1 + k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \pmod{n} \]

这里利用了欧拉定理（当 $\gcd(m, n) = 1$ 时），确保解密正确。

费马小定理费马小定理是数论中关于素数模运算的一个基本定理。它表述为：如果 $ p $ 是一个素数，且整数 $ a $ 不是 $ p $ 的倍数（即 $ p \nmid a $），那么： \[ a^{p-1} \equiv 1 \pmod{p} \] 这个定理揭示了素数模下幂运算的周期性规律，是许多数论问题和密码学应用的基础。 1. 定理的直观理解考虑素数 $ p = 5 $ 和整数 $ a = 2 $。计算 $ 2^{5-1} = 16 $，而 $ 16 \div 5 = 3 $ 余 $ 1 $，因此 $ 16 \equiv 1 \pmod{5} $，符合定理。本质上，当 $ a $ 与 $ p $ 互质时，模 $ p $ 的剩余类 $ \{1, 2, \dots, p-1\} $ 在乘以 $ a $ 后会重新排列，因此所有数的乘积满足： \[ a^{p-1} \cdot (1 \cdot 2 \cdots (p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod{p} \] 由于每个剩余类与 $ p $ 互质，可约去公共乘积，得到 $ a^{p-1} \equiv 1 \pmod{p} $。 2. 定理的证明方法一（剩余类重排）：集合 $ S = \{1, 2, \dots, p-1\} $ 是模 $ p $ 的简化剩余系。由于 $ p \nmid a $，集合 $ aS = \{a \cdot 1, a \cdot 2, \dots, a \cdot (p-1)\} $ 也是模 $ p $ 的简化剩余系（因为若 $ a i \equiv a j \pmod{p} $，则 $ i \equiv j \pmod{p} $）。因此： \[ \prod_ {k=1}^{p-1} (a \cdot k) \equiv \prod_ {k=1}^{p-1} k \pmod{p} \] 即： \[ a^{p-1} \cdot (p-1)! \equiv (p-1) ! \pmod{p} \] 由于 $ (p-1) ! $ 与 $ p $ 互质，可两边约去，得 $ a^{p-1} \equiv 1 \pmod{p} $。方法二（数学归纳法）：对 $ a $ 进行归纳。基础情况 $ a = 1 $ 显然成立。假设 $ a^{p-1} \equiv 1 \pmod{p} $，考虑 $ (a+1)^p $。由二项式定理： \[ (a+1)^p = \sum_ {k=0}^{p} \binom{p}{k} a^k \] 当 $ 1 \leq k \leq p-1 $ 时，二项式系数 $ \binom{p}{k} = \frac{p!}{k!(p-k) !} $ 可被 $ p $ 整除（因为分子含 $ p $，分母不含 $ p $），故： \[ (a+1)^p \equiv a^p + 1 \pmod{p} \] 由归纳假设 $ a^p \equiv a \pmod{p} $，代入得 $ (a+1)^p \equiv a + 1 \pmod{p} $，即 $ (a+1)^{p-1} \equiv 1 \pmod{p} $。 3. 应用示例计算模幂：求 $ 3^{100} \mod 7 $。由于 $ 7 $ 是素数且 $ 7 \nmid 3 $，费马小定理给出 $ 3^6 \equiv 1 \pmod{7} $。因为 $ 100 = 6 \cdot 16 + 4 $，所以： \[ 3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 3^4 = 81 \equiv 4 \pmod{7} \] 结果为 $\boxed{4}$。素性测试：费马小定理的逆命题不总是成立（例如 $ 2^{340} \equiv 1 \pmod{341} $，但 $ 341 = 11 \times 31 $ 是合数），但可用于初步筛选。若对某个 $ a $ 有 $ a^{n-1} \not\equiv 1 \pmod{n} $，则 $ n $ 一定是合数。 4. 推广：欧拉定理费马小定理可推广到合数模。欧拉定理指出：若 $ a $ 与 $ n $ 互质，则： \[ a^{\phi(n)} \equiv 1 \pmod{n} \] 其中 $ \phi(n) $ 是欧拉函数，表示不超过 $ n $ 且与 $ n $ 互质的正整数个数。当 $ n = p $ 为素数时，$ \phi(p) = p-1 $，即得费马小定理。 5. 密码学中的应用费马小定理是RSA加密的核心。在RSA中，选择两个大素数 $ p, q $，计算 $ n = pq $ 和 $ \phi(n) = (p-1)(q-1) $。公钥指数 $ e $ 满足 $ \gcd(e, \phi(n)) = 1 $，私钥指数 $ d $ 满足 $ e d \equiv 1 \pmod{\phi(n)} $。加密 $ c \equiv m^e \pmod{n} $，解密时： \[ c^d \equiv m^{e d} \equiv m^{1 + k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \pmod{n} \] 这里利用了欧拉定理（当 $ \gcd(m, n) = 1 $ 时），确保解密正确。