閱讀前，建議可以參考Day1：閱讀指南＆為何選擇這個題目？

▌挑戰簡介

• 題目：計算機概論Ｘ30天

• 挑戰內容：連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程，還有自己學習程式的心得體悟。

• 本篇性質：

  • 適合的人：對密碼學有興趣的人，因為模數運算（mod）是加密算法、密碼學很常用的東西
  • 說明：對於只是單純想寫程式的人（像是寫網頁），不懂mode真的沒關係，不要被嚇到了XD

▌心得

最近學校離散數學課程，上到「同餘」（Mod）的概念，我內心覺得很矇逼。心想「學這個到底要做什麼？」「我知道Ａ數跟那個Ｂ同餘可以幹嘛？」

原來，Mod的概念很常用在密碼學上（像是RSA加密、公鑰匙、私鑰匙），感覺就很酷是吧！
而要理解這些東西，會需要有基礎mod的概念。
因此本篇我要來介紹Mod，期望在之後章節能介紹——費馬小定理、中國餘式定理，還有RSA加密。

▌什麼是Mod

• mod簡單來說，就是指「同餘」

比如說：

4 除以 3 餘 1
10 除以 3 餘 1
我們就可以會說 4≡10 (mod 3) ，意思是「4和10在除以3的情況下是「同餘的」」

其他例子：

5 除以 2 餘 1
7 除以 2 餘 1

因此 5≡7 (mod 2)

▌為什麼需要Mod？

「你沒事求餘數做什麼？」、「知道同餘可以幹嘛啦？」

我完全明白，因為這完全就是我剛學mod的心聲！

Mod的究竟可以幹什麼？

Mod的存在的最重要意義，其實是幫——數據做分類

比如說，如果把所有自然數都除以7，你可以想像只會有7種可能

• 要麼被7整除 N ≡ 0 (mod 7)
• 要麼被7除，餘1 N ≡ 1 (mod 7)
• 要麼被7除，餘2 N ≡ 2 (mod 7)
• 要麼被7除，餘3 N ≡ 3 (mod 7)
• 要麼被7除，餘4 N ≡ 4 (mod 7)
• 要麼被7除，餘5 N ≡ 5 (mod 7)
• 要麼被7除，餘6 N ≡ 6 (mod 7)

所有的自然數在mod 7的情況下，就可以被分成了七組

這有什麼好處？

這意味著，不管是遇到一個多怪數字，像是131231312313131，你都可以把他進行分類（因此你對這個數字不是全然陌生的）

因為至少你知道，在mod7的情況下，他肯定可以被表示為七種之一

實際上 131231312313131 ≡ 2 mod 7

我們可以把一個複雜的大數，用一個較小的數字替換，這整個就簡化了運算的複雜性。

Mod的存在就是為了做分類，讓我們可以用「較小的數字」處理一些平時「很難處理」的數字

▌Mod 的性質

了解Mod的基礎後，還要來在認識3個Mod的性質，之後才能看到mod的妙處

1.因數定理（我自己發明的）

假設

a ≡ b (mod k)

則

k | a-b （意思是k是a-b的因數，k可以整除a-b)

有人可以告訴我這個定理有什麼名字嗎？

為什麼呢？

a ≡ b (mod k)

對於a,b，我們可以把a b改寫如下

a = kq+r
b = kp+r

q、p是什麼不重要，不要管他，反正就是某個整數
重點是：因為a、b同餘，所以我們知道a b一定會有一個共同的餘數r。

那麼

a = kq+r
b = kp+r
a-b = k(q-p)+(r-r)
a-b = k(q-p) 有沒有發現，r就被消掉了！

因此 k | a-b

我們推論出：

a ≡ b (mod k) <=> k | a-b

這個性質之後會用到

2.同餘的相加性質

如果
a = b (mod k)
c = d (mod k)
則
a+c = b+d (mod k)

為什麼呢？

a = b (mod k)可以寫成 根據上面證明的因數定理（這名字我發明的）a ≡ b (mod k) <=> k | a-b
(1)k|a-b

c = d (mod k)可以寫成 根據上面證明的因數定理（這名字我發明的）a ≡ b (mod k) <=> k | a-b
(2)k|c-d

那麼(1)(2)相加，可以得到（因為a-b可以被k整除，c-d也可以被k整除，他們相加當然也可以被k整除）
k|(a-b)+(c-d)

整理一下，就變成
k|(a+c)-(b+d)
那又可以寫成 根據上面證明的因數定理（這名字我發明的）a ≡ b (mod k) <=> k | a-b

a+c = b+d (mod k)

3.同餘的相乘性質

如果
a = b (mod k)
c = d (mod k)
則
aXc = bXd (mod k)

為什麼呢？

a = b (mod k)可以寫成 根據上面(1)證明的因數定理a ≡ b (mod k) <=> k | a-b
k|a-b
則乘上c也成立，變成
K|c(a-b) ---- (1)

c = d (mod k)可以寫成 根據上面(1)證明的因數定理a ≡ b (mod k) <=> k | a-b
k|c-d
則乘上b也成立，變成
K|b(c-d) ---- (2)

上面(1)(2)相加

K|c(a-b)＋b(c-d)
k|ac-bc+bc-bd
k|ac-bd
因此，根據根據上面(1)證明的因數定理
ac = bd (mod k)

同餘相乘的性質延伸

上面的相乘同餘定理，可以在繼續延伸兩個性質

(1)平方同餘定理

如果
a = b (mod k)
則
a^n=b^n (mod k)

因為
a = b (mod k)
a = b (mod k)
可以相乘
那麼a^2=b^2 (mod k)
繼續推演，就可以得到 a^n=b^n (mod k)

(2)倍數同餘定理

如果
a = b (mod k)
則
ma=mb (mod k)

因為當 m = m (mod k) 一定成立
那麼ma=mb (mod k) 也是理所當然的
繼續推演，就可以得到 ma=mb (mod k)

現在我們有三個武器，終於可以來做點事了

• 同餘的因數定理：a ≡ b (mod k) <=> k | a-b
• 同餘的加法性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> a+c = b+d (mod k)
• 同餘的相乘性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> ac = bd (mod k)
  • 次方公式 a ≡ b (mod k) <=> a^n ≡ b^n (mod k)
  • 倍方公式 a ≡ b (mod k) <=> am ≡ bm (mod k)

例題(1)

15^8001 X 22^4781 X 11^3 除以7的餘數為多少

.....這鬼知道喔，這大到連電腦都算不出來好嗎

沒關係，我們可以用mod

首先，我們知道
15 ≡ 1 (mod 7) 我用大腦想出來的
22 ≡ 1 (mod 7) 我用大腦想出來的
11 ≡ 4 (mod 7) 這我用大腦想出來的

則

15^8001 ≡ 1^8001 (mod 7) 根據上面同餘的相乘性質的次方公式
22^4781 ≡ 1^4781 (mod 7) 根據上面同餘的相乘性質的次方公式
11^3 ≡ 4^3 (mod 7) 根據上面同餘的相乘性質的次方公式

然後上面三條可以相乘 (根據上面同餘的相乘性質)

15^8001 X 22^4781 X 11^11 ≡ 1^8001 X 1^4781 X 4^3 (mod 7)
15^8001 X 22^4781 X 11^11 ≡ 64 (mod 7)
然後因為 64 ≡ 1 (mod 7)

好...好累，對，所以...
15^8001 X 22^4781 X 11^3 ≡ 1 (mod 7)

所以餘1

有沒有很厲害！我竟然算得出來
還有我竟然可以把 15^8001 這種鬼數字
化解成
15^8001 ≡ 1 (mod 7) 的形式！

這就是 數學的力量！

mod的意義，就是把複雜的數字，用簡單的方式表達

例題(2)

4793316+7890323 除以7 會餘多少？（夭壽喔，不想算4793316+7890323）

假設我們知道下面

4793316 ≡ 3 (mod 7)
7890323 ≡ 0 (mod 7)

那根據同餘的加法性質，可以得出

4793316+7890323 ≡ 3(mod 7)

我們根本不用知道4793316+7890323是多少，也可以算出它會餘3

mod的意義，就是即使你根本不知道那複雜的數字是多少，也可以用簡單的方式算出答案

總結

• Mod的存在就是為了幫數字做分類，讓我能更好的處理大數問題

• Mod的好處是讓我們可以用「簡單的數字」方便處理「很難處理」的大數

• 希望之後的章節我有機會用mod解釋一些實用性的算法wow

• 同餘的因數定理：a ≡ b (mod k) <=> k | a-b

• 同餘的加法性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> a+c = b+d (mod k)

• 同餘的相乘性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> ac = bd (mod k)

  • a ≡ b (mod k) <=> a^n ≡ b^n (mod k)
  • a ≡ b (mod k) <=> am ≡ bm (mod k)