【数论】费马小定理

前言#

费马小定理（Fermat’s Little Theorem）是数论中的一个重要定理，它与素数和模运算相关。定理的表述如下：

对于任意素数 $p$，如果 $a$ 是一个整数，且 $a$ 不是 $p$ 的倍数，则有 $a^{p-1} ≡ 1 (\mod p)$。

应用#

模逆元计算#

在模运算中，给定两个整数 $a$ 和 $p$，我们想要找到整数 $b$，使得 $(a \times b) \mod p = 1$。这里 $a$ 和 $p$ 必须互质，即它们没有共同的因子。费马小定理提供了一种计算模逆元的方法：

根据费马小定理，如果 $a$ 和 $p$ 互质（$a$ 不是 $p$ 的倍数），则有 $a^{p-1} ≡ 1 (\mod p)$。将等式两边同时乘以 $a^{-1}$（a 的模 p 逆元），得到 $a^{-1} ≡ a^{p-2} (\mod p)$。这意味着 $a^{p-2}$ 就是 $a$ 在模 $p$ 下的逆元。

所以，如果要计算 $a$ 在模 $p$ 下的逆元，只需计算 $a^{p-2} \mod p$，即可得到 $b$，使得 $(a \times b) \mod p = 1$。