最後更新：2026-06-05

模運算（modular arithmetic）是數論的分支，研究整數在固定模數下的餘數性質。若兩整數 a 與 b 相差 n 的倍數，則稱它們在模 n 意義下同餘，記作 a ≡ b (mod n)。本計算機支援三種核心運算：基本模運算、快速模冪，以及模逆元。

模運算（a mod n）

對正整數模數 n，數學定義的模運算 a mod n 是滿足以下恆等式的唯一整數 r：

$a = q \times n + r, \quad 0 \le r < n$

其中 q = ⌊a / n⌋ 為整除商（floor quotient），r 為餘數。此定義保證結果恆為非負數。

計算範例。 以 a = 17、n = 5 為例：

$q = \lfloor 17 / 5 \rfloor = 3, \quad r = 17 - 3 \times 5 = 2$

故 17 mod 5 = 2。以時鐘比喻：在五格的環形刻度盤上走 17 格，最終落在第 2 格。

負數的情形。 以 a = −7、n = 5 為例：

$q = \lfloor -7 / 5 \rfloor = -2, \quad r = -7 - (-2) \times 5 = 3$

故 −7 mod 5 = 3，而非 −2。數學定義確保 r 為非負數；C、JavaScript 等程式語言的 % 運算子採截斷除法，對負被除數會給出 −2，與此不同。

模冪（a^b mod n）

直接計算 a^b 再取餘數，在 b 很大時不可行，因為 a^b 的位數會隨 b 指數成長。快速模冪演算法（平方-乘法演算法）在每個步驟取餘數，使中間值始終維持在 [0, n − 1]，所需乘法次數為 O(log₂ b)。

演算法將指數 b 以二進位分解，從最低有效位開始處理：

• 每步對當前底數平方，並對 n 取餘；
• 若該位元為 1，則將結果乘以當前底數，再對 n 取餘。

計算範例。 以 a = 17、b = 3、n = 5 為例：

$17 \equiv 2 \pmod{5}$

$17^2 \equiv 4 \pmod{5}$

$17^3 = 17^2 \times 17 \equiv 4 \times 2 = 8 \equiv 3 \pmod{5}$

故 17³ mod 5 = 3。直接驗算：17³ = 4913 = 982 × 5 + 3。

此演算法是 RSA 等公開金鑰密碼系統的核心，這些系統中的指數通常達數百位，直接計算在計算上不可行。

模逆元（a⁻¹ mod n）

整數 a 在模 n 下的逆元，是滿足以下條件的整數 x：

$a \times x \equiv 1 \pmod{n}$

模逆元存在的充要條件是 gcd(a, n) = 1，即 a 與 n 互質。

• 當 n 為質數時，1 至 n − 1 的每個整數均有模逆元。
• 當 n 為合數時，與 n 共有公因數的整數不存在模逆元。

擴展歐幾里得演算法可在逆元存在時求出其值。標準歐幾里得演算法只計算最大公因數，擴展版本同時追蹤線性組合係數，找到整數 s 與 t 使得：

$a \times s + n \times t = \gcd(a, n)$

當 gcd(a, n) = 1 時，s 即為所求的模逆元。

計算範例。 以 a = 3、n = 5 為例，對 5 和 3 執行擴展歐幾里得演算法：

• 5 = 1 × 3 + 2
• 3 = 1 × 2 + 1

回代整理：

$1 = 3 - 1 \times 2 = 3 - 1 \times (5 - 1 \times 3) = 2 \times 3 - 1 \times 5$

故 3 × 2 ≡ 1 (mod 5)，即 3⁻¹ ≡ 2 (mod 5)。驗算：3 × 2 = 6 = 1 × 5 + 1。

實際應用

模運算是數學與資訊科學的重要基礎，應用範圍廣泛：

• 公開金鑰密碼學：RSA 加密以明文的大指數模大合數進行，解密則使用加密指數的模逆元。模冪與模逆元的計算效率，直接決定密碼系統的可行性。
• 校驗碼：ISBN-13、IBAN 及信用卡號碼的 Luhn 演算法，均透過模運算偵測輸入錯誤。
• 日曆計算：星期幾以模 7 計算；農曆、復活節等曆法計算也涉及同餘關係。
• 雜湊表：鍵值的 bucket 索引以「鍵 mod 表大小」決定，使資料均勻分布。
• 環形緩衝區：讀寫指標以「索引 mod 容量」循環推進，無需判斷邊界。

整除商與帶餘除法恆等式

對所有滿足 n ≥ 1 的整數對 (a, n)，整除商 q = ⌊a / n⌋ 與餘數 r = a mod n 符合帶餘除法恆等式：

$a = q \times n + r, \quad 0 \le r < n$

本計算機同時顯示 r 與 q，可對任意輸入直接驗證此恆等式。