在线词典

费尔马小定理

更新日期:2026-11-12 18:36:46

标题费尔马小定理
内容

费尔马小定理是数论中的一个重要定理,由17世纪法国数学家皮埃尔·德·费尔马提出。该定理在密码学、计算机科学以及数论研究中具有广泛应用。它提供了一种快速判断一个数是否为质数的方法,并且在模运算中有着重要的作用。

一、定理内容

费尔马小定理(Fermat's Little Theorem)的表述如下:

> 如果 $ p $ 是一个质数,且 $ a $ 是一个不被 $ p $ 整除的整数,那么

> $$

> a^{p-1} \equiv 1 \pmod{p}

> $$

换句话说,当 $ p $ 为质数时,$ a $ 的 $ p-1 $ 次幂除以 $ p $ 的余数为 1。

二、定理说明

- 适用条件:$ p $ 必须是质数;$ a $ 不能是 $ p $ 的倍数。

- 逆否命题:如果 $ a^{p-1} \not\equiv 1 \pmod{p} $,则 $ p $ 不是质数。

- 扩展形式:若 $ a $ 与 $ p $ 互质,则 $ a^k \equiv a^{k \bmod (p-1)} \pmod{p} $。

三、应用示例

$ a $ $ p $ $ a^{p-1} \mod p $ 是否成立
2 3 $ 2^2 = 4 \mod 3 = 1 $ 成立
3 5 $ 3^4 = 81 \mod 5 = 1 $ 成立
4 7 $ 4^6 = 4096 \mod 7 = 1 $ 成立
5 11 $ 5^{10} \mod 11 = 1 $ 成立
2 4 $ 2^3 = 8 \mod 4 = 0 $ 不成立

从表中可以看出,当 $ p $ 为质数时,定理成立;而当 $ p $ 为合数时,定理可能不成立。

四、注意事项

- 费尔马小定理的逆命题并不一定成立。即,如果 $ a^{p-1} \equiv 1 \pmod{p} $,并不能断定 $ p $ 是质数。

- 存在一些合数 $ p $,使得对于某些 $ a $,$ a^{p-1} \equiv 1 \pmod{p} $ 成立,这类数称为“卡迈克尔数”(Carmichael numbers)。

五、总结

项目 内容
定理名称 费尔马小定理
提出者 皮埃尔·德·费尔马(Pierre de Fermat)
适用条件 $ p $ 是质数,$ a $ 与 $ p $ 互质
数学表达式 $ a^{p-1} \equiv 1 \pmod{p} $
应用领域 密码学、模运算、素性检测
注意事项 逆命题不成立,存在卡迈克尔数

费尔马小定理虽然形式简单,但其背后蕴含着深刻的数论思想,是现代数学和信息安全技术的重要基础之一。

随便看