同餘與模運算一次搞懂：時鐘算術與餘數的威力

現在是九點，航班五個小時後起飛。沒有人會回答「十四點」。你會說兩點，而且想都沒想就說出來了，因為鐘面上沒有十四。小時數在十二點繞回去，然後重新開始。從你會看時間開始，你就一直在做模運算，只是從來沒見過它的記號。

整個主題就是這樣。挑一個要繞回去的數，忘掉所有完整的圈數，只保留你最後落在哪裡。這一個習慣，也就是只保留餘數，之所以值得寫一篇文章，是因為它能解決那些正面硬算看起來不可能的問題：一個七十位數的個位數是多少、一個巨大的數能不能被 9 整除、為什麼信用卡號碼有效或無效，以及一段訊息怎麼能被打亂，讓只有指定的讀者才能還原。

本文要呈現的是那幅圖像：餘數到底是什麼、為什麼你可以在計算之前先化簡、碰到負數和次方會發生什麼事，以及唯一真正的難處，也就是除法，是從哪裡來的。

餘數是你落腳的地方，不是剩下的東西

標準的定義說，$a \bmod n$ 是 $a$ 除以 $n$ 的餘數。這是對的，但也正是這個主題讓人覺得像苦差事的原因，因為「餘數」聽起來像除法之後剩下的零頭，是事後才想到的東西。

比較好的圖像是：一條圓形跑道，上面有 $n$ 個刻度，編號從 $0$ 到 $n-1$。要求 $a \bmod n$，就從 $0$ 出發，沿著跑道走 $a$ 步。你停下來的地方就是答案。在有 5 個刻度的跑道上走 17 步，會完整繞三圈（15 步），再多走 2 步，所以你停在刻度 2。因此 $17 \bmod 5 = 2$。完整的圈數是商，你落腳的地方是餘數。

這幅圖像做到了定義沒有做到的兩件事。它讓餘數永遠落在 $0$ 到 $n-1$ 的範圍內，因為只有這些刻度。它也解釋了為什麼兩個數即使差距很大，在模 $n$ 之下也可以「相同」：在 5 個刻度的跑道上，$2$、$17$、$102$ 和 $5{,}000{,}002$ 全都停在刻度 2。它們相差的只是圈數，而跑道不記得圈數。

數學家把這個想法寫成同餘式：

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

讀作「在 5 個刻度的跑道上，17 落在 2 落腳的地方」。三條線的符號不是等號，因為 17 和 2 並不相等。它的意思是，對任何只在乎跑道上位置的問題，它們可以互相替換。精確的版本是：$a \equiv b \pmod{n}$ 表示 $n$ 整除 $a - b$，也就是說這兩個數相差整數圈。

加法和乘法只在乎你在哪裡

這個事實讓模運算成為一個工具，而不只是一個稀奇的東西。如果你要把兩個數相加再求餘數，可以先求各自的餘數，把餘數相加，再化簡一次。答案完全相同。減法和乘法也一樣。

在跑道上這是顯而易見的。加 17 就是走 17 步，也就是三圈再多 2 步。那三圈讓你回到出發的位置，什麼都沒改變，所以加 17 的效果和加 2 完全相同。藏在數字裡的圈數是無用的重量，而它們經過加法和乘法之後仍然是無用的重量，因為 $n$ 的倍數乘以任何數，仍然是 $n$ 的倍數。

寫出來，設 $a = qn + r$、$b = pn + s$：

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

第一個括號裡的全都是圈數。只有 $rs$ 留下來，所以 $ab \bmod n$ 就是 $rs \bmod n$。餘數帶著這個問題所需要的全部資訊。

這就是為什麼 Math Zen 算術主題裡的提示，說要一步一步化簡，而不是去算完整的值。假設你想求 $123 \times 456 \bmod 7$。你可以乘出 56,088 再除以 7 做長除法。或者你可以注意到 $123 = 119 + 4$，所以 $123 \equiv 4$，而 $456 = 455 + 1$，所以 $456 \equiv 1$，答案就是 $4 \times 1 = 4$。兩次小小的化簡，取代了一個四位數的乘法。習慣是：如果你只在乎餘數，就永遠不要讓一個數長到超過 $n$。

負數往另一個方向走

跑道的圖像也能處理最常讓人絆倒的情況。$-3 \bmod 5$ 是多少？

在 5 個刻度的跑道上，從 0 往回走 3 步。你經過 4，再經過 3，然後落在 2。所以 $-3 \equiv 2 \pmod{5}$。負數只是朝相反方向走的一段路，概念和直覺理解負數中的相同，而餘數仍然是你落腳的地方，仍然介於 $0$ 和 $n-1$ 之間。

捷徑是：一直加圈數，直到這個數變成正的。$-3 + 5 = 2$。要求 $-14 \bmod 5$，就加 15（三圈），得到 1。計算機與程式語言對負數餘數的規定不一致，有些會對 $-14 \bmod 5$ 回傳 $-4$，所以在考試中，答案一律寫成跑道上非負的那個刻度，並在相信計算機之前先確認它的慣例。

減法也是同樣的道理。$3 - 8 \pmod{5}$ 是 $-5$，正好往回一圈，所以答案是 0。或者先化簡：$8 \equiv 3$，所以 $3 - 3 = 0$。

巨大次方的個位數

這個問題最能讓人相信這個主題值得認識，它也是「先化簡」規則的直接結果。

一個數的個位數就是這個數除以 10 的餘數，因為十位、百位以及更高的位數都是 10 的倍數，在 10 個刻度的跑道上都回到 0。所以「$7^{100}$ 的個位數是多少」這個問題，就是「$7^{100} \bmod 10$ 是多少」，你完全不需要算出 $7^{100}$。

取而代之的是，看著 7 的次方在 10 個刻度的跑道上一步步走，每次都化簡：

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

一旦碰到 1，週期就重新開始：7、9、3、1、7、9、3、1，週期是 4。因為 $100 = 4 \times 25$，第一百次方正好落在一個完整週期的尾端，與 $7^4$ 是同一個位置，所以它的個位數是 1。

每一個底數在模 10 之下都有一個週期，而且大多很短。2 的次方依序走過 2、4、8、6。3 的次方走過 3、9、7、1。5 和 6 的次方則動也不動。方法永遠一樣：一邊算一邊化簡，找出週期的長度，把指數除以週期長度，而那個除法的餘數就告訴你現在在週期的哪個位置。這是指數中重複相乘的概念，只不過是在圓形跑道上，而不是在直線上進行。

為什麼「9 的數字和判別法」成立

大家都學過，一個數的各位數字加起來是 9 的倍數，這個數就能被 9 整除，但幾乎沒有人學過為什麼。模運算把它變成一行就能說完的論證。

在 9 個刻度的跑道上，十是一圈再多一格：$10 \equiv 1 \pmod{9}$。那麼 $100 = 10 \times 10 \equiv 1 \times 1 = 1$，而 10 的每一個次方也都同餘於 1。所以像 $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ 這樣的數，會同餘於 $4 + 5 + 2 + 7 = 18 \pmod{9}$，而 18 在 9 個刻度的跑道上是 $0$，所以 4,527 能被 9 整除。數字和不是什麼小把戲。它就是這個數本身，只是放在模 9 之下來看。

3 的判別法也是同樣的道理，因為 $10 \equiv 1 \pmod{3}$ 也成立。11 的判別法來自 $10 \equiv -1 \pmod{11}$，這讓 10 的次方在 $1$ 和 $-1$ 之間交替，得到交錯數字和。所有被要求背下來的整除判別法，都是同一個事實：「把 10 的次方化簡」，只是套用在不同的跑道上。

檢查碼：錢包裡的模運算

每一個 ISBN、每一張信用卡號碼和每一個條碼，結尾都有一個數字，它唯一的工作就是當一個餘數。

13 位數 ISBN 的最後一碼是這樣選的：十三個數字的加權和（權重交替為 1 和 3）要同餘於 $0 \pmod{10}$。只要打錯一個數字，總和就會落在 10 個刻度的跑道上別的地方，掃描器就會拒絕它。信用卡使用 Luhn 演算法，這是一種稍微更聰明的加權，也同樣是靠檢查模 10 的總和，來抓出大部分兩個相鄰數字被對調的情況。

這些是一個大得多的應用的樸素近親。現代加密建立在這個事實上：在非常大的 $n$ 之下，把一個數取次方再取模很容易，但沒有秘密金鑰就想把這個過程反推回去卻不容易。你在上面為 $7^{100}$ 做的找週期，就是同一個運算，只是放大到有數百位的數字，而一邊算一邊化簡的規則，是它能夠被算出來的唯一原因。

除法是跑道開始顛簸的地方

加法、減法和乘法在跑道上的行為，與它們在數線上完全一樣。除法則不然，這個主題「很難」的名聲，也只有在這裡才名副其實。

在一般的數線上，除以 4 就是乘以 $\tfrac{1}{4}$，也就是乘以 4 會得到 1 的那個數。在 12 個刻度的跑道上，有沒有哪個刻度乘以 4 會落在 1？全部試一遍：$4 \times 1 = 4$、$4 \times 2 = 8$、$4 \times 3 = 12 \equiv 0$、$4 \times 4 = 16 \equiv 4$，而 4、8、0 的規律會永遠重複。它從不碰到 1。所以在 12 個刻度的跑道上，沒有「除以 4」這回事。

原因是 4 和 12 有共同因數。從 4 的倍數出發，加上或減去幾圈 12，你得到的仍然是 4 的倍數，所以永遠不可能落在 12 的倍數之後的 1。改試試 5：$5 \times 5 = 25 = 24 + 1 \equiv 1$，所以 5 在 12 個刻度的跑道上是它自己的倒數，除以 5 沒有問題。規則是：當且僅當 $a$ 與 $n$ 除了 1 以外沒有共同因數時，$a$ 在模 $n$ 之下才有倒數。

這個規則有個驚人的結果。如果 $n$ 是質數，從 $1$ 到 $n - 1$ 的每個數都與它沒有共同因數，所以每一個非零的刻度都有倒數，你可以自由地做除法。質數跑道就是四則運算全都行得通的跑道，這在很大程度上說明了，為什麼質數（質數有無限多個保證了它們的供應）位居數論和密碼學的中心。

錯誤從哪裡來

模運算的零件很少，所以錯誤也相應地很特定。

第一個是化簡了指數而不是底數。在 $7^{100} \bmod 10$ 中，你可以把 7 化簡成模 10（它本來就是），也可以在知道週期長度之後，把指數化簡成模週期長度，但你不可以把 100 化簡成模 10 然後去算 $7^0$。指數活在另一條跑道上，也就是大小等於週期長度的那一條，把兩條跑道混在一起，是這個主題中最常見的單一錯誤。

第二個是負的餘數。$-14 \bmod 5$ 是 1，不是 $-4$。它們在跑道上是同一個位置，但只有其中一個是慣用的名稱，而參考答案要的是非負的那個。

第三個是在沒有檢查倒數是否存在時就做除法。只有當某個因數與模數沒有共同因數時，才可以把它從同餘式的兩邊約掉。從 $4 \times 2 \equiv 4 \times 5 \pmod{12}$ 出發（這是成立的，因為兩邊都是 8），你不能約掉 4 而得出 $2 \equiv 5$，那是錯的。約分時被你丟掉的圈數，必須是原本那條跑道的圈數。

第四個是忘了在最後化簡。在 7 個刻度的跑道上得到 $rs = 21$ 然後寫下 21，嚴格說不算錯，但也不算答案。答案是跑道上的一個刻度，而 21 是三圈，所以那個刻度是 0。

Math Zen 的定位

Math Zen 的算術主題為模運算設有專屬的分級，而且它的進程是圍繞著「先化簡」的習慣設計，而不是圍繞著記號。前面的題目要求簡單的餘數，以及小模數的同餘，直到「我會落在哪裡」變成自動反應。中間的分級混入負數與乘積，重點是在相乘之前先化簡每一個因數，並寫出非負的餘數。後面的分級是個位數與週期長度的題目，它們是競賽試卷與入學考試上會出現的題型，也會懲罰任何想要算出完整次方的人。

因為每次練習都很短，而且題目會以間隔的時間再回來，就像數學練習的間隔複習所描述的，找週期這個動作會變成反射，而不是一個要翻出來查的程序。大多數人並沒有一個讀一章就能補好的模運算漏洞。他們缺的是一幅從來沒有人為他們畫出的圖像，也就是跑道，以及大約四十次從來沒有做過的練習。

重點整理

模運算是在有 $n$ 個刻度的圓形跑道上做的算術。餘數是你走了 $a$ 步之後落腳的地方，完整的圈數被忘掉，而當兩個數落在同一個刻度，它們就是同餘的。因為圈數對和與積沒有任何貢獻，你可以在加法或乘法之前，把每個數都化簡成它的餘數，而這一項允許，把原本不可能的計算，例如 $7^{100}$ 的個位數，變成你可以用手追蹤的短週期。整除判別法就是 10 的次方在模 9、模 3 或模 11 之下的化簡。檢查碼是用來抓出打字錯誤的餘數。只有當一個數與跑道沒有共同因數時，除法才行得通，這就是質數跑道很特別的原因。

當模運算的題目卡住時，就畫出跑道。問自己每一部分落在哪裡，一邊算一邊化簡，並讓指數待在它自己的跑道上。答案是介於 $0$ 和 $n - 1$ 之間的一個刻度，而這幅圖像會比公式更早帶你到那裡。