【数论】费马小定理


前言#

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

对于任意素数 pp,如果 aa 是一个整数,且 aa 不是 pp 的倍数,则有 ap11(modp)a^{p-1} ≡ 1 (\mod p)

应用#

模逆元计算#

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

根据费马小定理,如果 aapp 互质(aa 不是 pp 的倍数),则有 ap11(modp)a^{p-1} ≡ 1 (\mod p)。将等式两边同时乘以 a1a^{-1}(a 的模 p 逆元),得到 a1ap2(modp)a^{-1} ≡ a^{p-2} (\mod p)。这意味着 ap2a^{p-2} 就是 aa 在模 pp 下的逆元。

所以,如果要计算 aa 在模 pp 下的逆元,只需计算 ap2modpa^{p-2} \mod p,即可得到 bb,使得 (a×b)modp=1(a \times b) \mod p = 1