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

▌挑戰簡介

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

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

• 本篇性質：

  • 適合閱讀的人：
    • 對密碼學有興趣的人，因為模數運算（mod）是加密算法、密碼學很常用的東西
    • 一定要有mod同餘的基礎（不然會看不懂）
    • 請參考Day 14:[離散數學]同餘（Mod）是什麼？
  • 說明：對於只是單純想寫程式的人（像是寫網頁），不懂mode真的沒關係，不要被嚇到了XD

▌中國餘式定理 Chinese remainder theorem

中國南北朝時期（公元5世紀）的數學著作《孫子算經》，當中有一個古老的問題

有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

翻譯成白話文，就是有一個X，他除以3會餘2，除以5會餘3，除以7會餘2，請為X是多少

寫成公式就是以下：

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

怎麼解呢

先不要探究怎麼會有這麼傻逼的問題，總之來算算看

首先，這解法會應用上一章節，所提到的Mod運算三個武器之二

• 同餘的因數定理：a ≡ b (mod k) <=> k | a-b
• 同餘的加法性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> a+c = b+d (mod k)

所以如果不懂這兩個公式，建議去閱讀Day 14:[離散數學]同餘(Mod)可以幹什麼？

x ≡ 2 (mod 3) ----(1)
x ≡ 3 (mod 5) ----(2)
x ≡ 2 (mod 7) ----(3)

這個要算太難了，需要一點拆解

首先：設x＝a+b+c

x ≡ 2 (mod 3) 就可以變成 a+b+c ≡ 2 (mod 3)
然後根據同餘的加法性質，可以拆成以下三條

a ≡ 2 (mod 3) 
b ≡ 0 (mod 3)
c ≡ 0 (mod 3)

因為只要modㄧ樣，就可以相加變回 a+b+c = x ≡ 2 (mod 3)

x ≡ 3 (mod 5) 根據同餘的加法性質，可以拆成以下三條

a ≡ 0 (mod 5) 
b ≡ 3 (mod 5)
c ≡ 0 (mod 5)

因為只要modㄧ樣，就可以相加變回 a+b+c = x ≡ 3 (mod 5)

x ≡ 2 (mod 7) 根據同餘的加法性質，可以拆成以下三條

a ≡ 0 (mod 7) 
b ≡ 0 (mod 7)
c ≡ 2 (mod 7)

因為只要modㄧ樣，就可以相加變回 a+b+c = x ≡ 2 (mod 7)

整理一下，可以分成三組

a ≡ 2 (mod 3) 
a ≡ 0 (mod 5)
a ≡ 0 (mod 7) 

b ≡ 0 (mod 3)
b ≡ 3 (mod 5)
b ≡ 0 (mod 7)

c ≡ 0 (mod 3)
c ≡ 0 (mod 5)
c ≡ 2 (mod 7)

這樣就比較好做一點，可以開始分別找出 a b c是誰

尋找a

a ≡ 2 (mod 3) 
a ≡ 0 (mod 5)
a ≡ 0 (mod 7) 

因為a可以被5、7整除，因此a是35的倍數
a = 35p
=> 35p ≡ 2 (mod 3)
=> 3 | 35p-2 根據同餘的因數定理
=> 可以得知p=1 會成立（這裡要自己代代看）
因此a是35 （當然a有很多可能性）

尋找b

b ≡ 0 (mod 3)
b ≡ 3 (mod 5)
b ≡ 0 (mod 7)

因為b可以被3、7整除，因此b是21的倍數
b = 21p
=> 21p ≡ 3 (mod 5)
=> 5 | 21p-3 根據同餘的因數定理
=> 可以得知p=3 會成立（這裡要自己代代看）
因此b是63 （當然b有很多可能性）

尋找c

c ≡ 0 (mod 3)
c ≡ 0 (mod 5)
c ≡ 2 (mod 7)

因為c可以被3、5整除，因此c是15的倍數
c = 15p
=> 15p ≡ 2 (mod 7)
=> 7 | 15p-2 根據同餘的因數定理
=> 可以得知p=2 會成立（這裡要自己代代看）
因此c是30 （當然b有很多可能性）

找出x囉

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

因為x=a+b+c，a=35，b=63，c=30
因此，x=128

寫成公式就是以下：

128 ≡ 2 (mod 3)
128 ≡ 3 (mod 5)
128 ≡ 2 (mod 7)

因此x有可能128囉！

但要注意x可能有很多種可能

找通解

尋找一個可以同時被 3 5 7整除的數
比如說105t好了，則

128  ≡ 2 (mod 3)
105t ≡ 0 (mod 3)

128 ≡ 3 (mod 5)
105t ≡ 0 (mod 5)

128 ≡ 2 (mod 7)
105t ≡ 0 (mod 7)

根據同餘的加法性質，就變成

128+105t ≡ 2 (mod 3)
128+105t ≡ 3 (mod 5)
128+105t≡ 2 (mod 7)

因此 128+105t (這是通解）
適當調整t，可以找出最小值

比如說t＝-1時
x=23，因此x的最小解是23