【数论】费马小定理
前言
费马小定理(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$。
via サン猫の時間漂流
前言
费马小定理(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$。
via サン猫の時間漂流