什麼是模運算計算機?
模運算又稱「時鐘運算」:當數字達到固定的模數 \(n\) 後就會循環歸零。這個計算機會計算 \((a \text{ op } b) \bmod n\) 形式的算式,其中運算可以是加法、減法、乘法,或單純把一個數 \(a\) 對 \(n\) 取模。計算結果一律回傳最小非負餘數,也就是介於 0 到 \(n - 1\) 之間的數字。
如何使用
先輸入 \(a\) 的值,選擇運算方式,再填入 \(b\)(選「僅取模」時會忽略 \(b\)),最後設定模數 \(n\)。計算機會先算出原始算式的值,再對 \(n\) 取模。負數結果會被轉換到標準的 \(0 \ldots n-1\) 範圍內,因此 \(-1 \bmod 12\) 會得到 11,而不是 \(-1\)。
公式說明
核心關係式為 $$r = (a \text{ op } b) \bmod n.$$ 由於程式語言中的取餘運算可能產生負值,我們改用歐幾里得形式 $$r = ((x \bmod n) + n) \bmod n,$$ 以確保結果必為非負。這與數論、密碼學與雜湊運算中採用的數學慣例完全一致。
範例演算
假設 \(a = 17\)、運算為加法、\(b = 25\)、\(n = 12\)。先計算 $$17 + 25 = 42,$$ 接著求 \(42 \bmod 12\):因為 \(42 = 3 \times 12 + 6\),所以餘數為 6。換句話說,在 12 小時制的時鐘上,17 + 25「小時」會落在第 6 個位置。
更多含負數與乘法的計算範例
在每個情況中,計算機都會回傳最小非負餘數 \(r\),即唯一滿足 \(0 \le r < n\) 且對某個整數 \(q\) 有 \(\text{raw} = n\cdot q + r\) 的值。模數 \(n\) 必須是正整數。
範例 1:原始結果為負數的減法
計算 \((5 - 23) \bmod 7\)。
- 原始結果:\(5 - 23 = -18\)。
- 除法:\(-18 = 7 \cdot (-3) + 3\),因此商為 \(-3\),餘數為 \(3\)。驗算:\(-18 + 21 = 3\)。
- 最終餘數:3。
範例 2:乘法
計算 \((47 \times 19) \bmod 10\)。
- 原始結果:\(47 \times 19 = 893\)。
- 除法:\(893 = 10 \cdot 89 + 3\),因此商為 \(89\),餘數為 \(3\)。
- 最終餘數:3。(捷徑:mod 10 時只需考慮末位數字,而 \(7 \times 9 = 63\) 的末位是 3。)
範例 3:負數的普通取模
計算 \(-29 \bmod 6\)。
- 原始值:\(-29\)(普通取模不需要第二個運算數)。
- 除法:\(-29 = 6 \cdot (-5) + 1\),因此商為 \(-5\),餘數為 \(1\)。驗算:\(-29 + 30 = 1\)。
- 最終餘數:\(1\)。
請注意,商是向下取整(朝負無窮大方向),而不是朝零取整。正是這一點確保餘數介於 0 與 \(n-1\) 之間。
情境比較:相同輸入,不同運算
| a | b | n | 運算 | 原始結果 | 最終餘數 |
|---|---|---|---|---|---|
| 17 | 25 | 12 | 加法 | 42 = 12·3 + 6 | 6 |
| 17 | 25 | 12 | 減法 | −8 = 12·(−1) + 4 | 4 |
| 17 | 25 | 12 | 乘法 | 425 = 12·35 + 5 | 5 |
| −7 | 未使用 | 5 | 普通取模 | −7 = 5·(−2) + 3 | 3 |
| 17 | 25 | 1 | 乘法 | 425 = 1·425 + 0 | 0 |
當 \(n = 1\) 時,每個整數都與 0 同餘,因此結果總是 0。
注意:歐幾里得式(最小非負)餘數可能與某些程式語言回傳的帶符號餘數不同。在 C、C++、Java 和 JavaScript 中,% 運算子朝零截斷,因此 -7 % 5 得到 \(-2\),而本計算機得到 \(3\)。當模數為正時,Python 的 % 得到 \(3\),與歐幾里得結果一致。只要帶符號餘數為負,兩個值就恰好相差 \(n\)。
常見問題
「mod」是什麼意思?它代表除法後的餘數。例如 \(13 \bmod 5 = 3\),因為 \(13 = 2 \times 5 + 3\)。
為什麼我輸入的負數變成正數了?因為我們回傳的是最小非負餘數。例如 \(-7 \bmod 5 = 3\),因為加上兩個 5(\(-7 + 10 = 3\))後就落在 \(0 \ldots 4\) 的範圍內。
如果 \(n = 1\) 會怎樣?任何整數對 1 取模都同餘於 0,所以結果永遠是 0。