模反元素

$a$ 在模 $m$ 下的反元素 (modular inverse) 是滿足 $ax\equiv1\pmod m$ 的 $x$,記作 $a^{-1}$;它讓模運算有「除法」。存在 ⟺ $\gcd(a,m) = 1$(Bézout:$ax + my = 1$ 的 $x$ 就是反元素)。

求法:擴展歐幾里得(通用)、費馬小定理 $a^{p-2}$($m$ 為質數)、小模數直接試。算例:$7^{-1}\bmod 26$:$7\cdot15 = 105 = 4\cdot26 + 1$,所以是 15;$4$ 在模 $10$ 沒有反元素(gcd 為 2,$4x$ 永遠是偶數)。

有反元素的元素構成乘法群 $U(m)$,大小 $\varphi(m)$。仿射密碼的解密、RSA 私鑰 $d = e^{-1}\bmod\varphi(N)$、橢圓曲線的點加法、有限體上的除法,都需要模反元素。