模反元素（modular inverse）

在普通算術裡，除以 3 就是乘以 1/3，也就是能把 3 變回 1 的那個數。在時鐘式的模算術裡，你只保留對 m 的餘數，沒有分數——但你仍可以問：哪個整數乘上 a，會在模 m 下給出餘數 1？那個數就是 a 的模反元素，記作 a^(-1) mod m，它就是你在模算術裡「除法」的方式。例如模 7 時 3 的反元素是 5，因為 3*5 = 15 餘 1。

精確地說，a^(-1) mod m 是落在 0..m-1 範圍、使 a*x = 1 mod m 的整數 x。關鍵事實是它何時存在：反元素存在的充要條件是 gcd(a, m) = 1，也就是 a 與 m 沒有共同因數。理由是貝祖恆等式——gcd(a, m) = 1 表示存在整數 x、y 使 a*x + m*y = 1，把這式子讀作模 m 會消掉 m*y 項，剩下 a*x = 1 mod m，故 x 就是反元素。這給出標準演算法：對 (a, m) 跑擴展歐幾里得演算法，取其係數 x，再化到 0..m-1。當 m 為質數時還有費馬小定理，給出 a^(-1) = a^(m-2) mod m，可用快速模冪計算。

模反元素在數論演算法裡無所不在。它讓你解線性同餘式 a*x = b mod m（兩邊乘 a^(-1)），讓中國餘數定理的重建公式得以運作，也是 RSA 的核心——其中私密解密指數正是公開指數對某個數的反元素。要記住的一個誠實陷阱：不是每個元素都有反元素。模 12 時，4 沒有反元素，因為 gcd(4, 12) = 4 而非 1——沒有任何 4 的倍數會在模 12 下餘 1。所以在假設能做除法之前，你必須先檢查 gcd 是否為 1。