Week 14 課程簡報
目標
- 看懂表示法 \(A\equiv B\) \(\mod{n}\)
- 暸解「擴展歐幾里得演算法」實作概念。
選讀
- 模反元素
- 歐拉定理
- 費馬小定理
複習：餘數
\[ \begin{aligned} &42 \div 18 = 2 ... 6\\ &60 \div 18 = 3 ... 6\\\\ &42 = 2 \cdot 18 + 6\\ &60 = 3 \cdot 18 + 6 \end{aligned} \]
同餘（Modular arithmetic）
當除以\(18\)的時候，\(42\)與\(60\)的餘數都是\(6\)。
\[ 42 \equiv 60 \mod{18} \]
同餘：加法與乘法可以結合
若
\[
a \equiv b \mod n \\c \equiv d \mod n
\]
則
\[
a+c \equiv b+d \mod n\\a\times c \equiv b\times d \mod n
\]
最大公因數：定義
能夠整除 \(A,B\) 的最大正整數。
考慮 \(\gcd(A, B) = g\)
- 兩個參數 \(A,B\) 的定義域為整數\(Z\)，
- 值域 \(g\) 為自然數\(N\)＆\(0\)
最大公因數：性質1
\(gcd(A, B) = gcd(|A|, |B|)\)
藉由絕對值，我們可以把參數的定義域放大到所有整數。
最大公因數：性質2
\(gcd(A, 0) = |A|\)
可以整除 \(A\) & \(0\) 的正整數就是\(|A|\)。
最大公因數：性質3
\(gcd(A, B) = gcd(A\%B, B)\)
最重要的性質，我們熟悉的輾轉相除法的根據。
Note: 「%」取餘數
複習：輾轉相除法
別名：歐幾里德演算法
\[ \begin{aligned} 78 &\div 66 = 1 ... 12\\ 66 &\div 12 = 5 ... 6\\ 12 &\div 6 = 2 ... 0\\ &\Rightarrow 6 \end{aligned} \]
核心問題
若：\(g = gcd(A, B)\)
尋找一組整數對\((x,y)\)
使得：\(x\cdot A + y \cdot B = g\)
擴展歐幾里得演算法
沒辦法一次到位解決的問題，可以分多次解決
範例：
\(A = 786, B = 186\)，請尋找一組整數對\((x,y)\)
使得 \(x\cdot A + y \cdot B = gcd(A, B)\)
我們可以從輾轉相除法的過程找到靈感
step 1
考慮數列R，為輾轉相除法的過程餘數。
| 數列R | 目標 |
|---|---|
| 786 | |
| 186 | |
| 42 | |
| 18 | |
| 6 | \(6 = x\cdot 786+ y \cdot 186\) |
step 2
如何分次解決呢？
| 數列R | 目標 |
|---|---|
| 786 | \(786 = 1\cdot 786+ 0 \cdot 186\) |
| 186 | \(186 = 0\cdot 786+ 1 \cdot 186\) |
| 42 | |
| 18 | |
| 6 | \(6 = x\cdot 786+ y \cdot 186\) |
step 3
\(\because 786 \div 186 = 4 ... 42\)
\(\therefore 42 = (1) \cdot 786 + (-4) \cdot 186\)
\(42\)可拆解為 \(786\) & \(186\) 的整數倍和。
| 數列R | 目標 |
|---|---|
| 786 | \(786 = 1\cdot 786+ 0 \cdot 186\) |
| 186 | \(186 = 0\cdot 786+ 1 \cdot 186\) |
| 42 | \(42 = 1 \cdot 786+ -4 \cdot 186\) |
| 18 | |
| 6 | \(6 = x\cdot 786+ y \cdot 186\) |
step 4
\(\because 186 \div 42 = 4 ... 18\)
\(\therefore 18 = (1) \cdot 186 + (-4) \cdot 42\)
\(18\)可拆解為 \(186\) & \(42\) 的整數倍和。
又 \(\because 42\) 可成功分解成 A,B 的整數倍和。
\(\therefore 18\) 可成功分解成 A,B 的整數倍和。
| R | 目標 |
|---|---|
| 786 | \(786 = 1\cdot 786+ 0 \cdot 186\) |
| 186 | \(186 = 0\cdot 786+ 1 \cdot 186\) |
| 42 | \(42 = 1 \cdot 786+ -4 \cdot 186\) |
| 18 | \(18 = 1 \cdot 186+ -4 \cdot (1 \cdot 786+ -4 \cdot 186)\) |
| 6 | \(6 = 1 \cdot (1 \cdot 786+ -4 \cdot 186)+ -2 \cdot (1 \cdot 186+ -4 \cdot (1 \cdot 786+ -4 \cdot 186))\) |
| 6 | \(6 = 9\cdot 786+ (-38) \cdot 186\) |
結論
| R | 786 | 168 | 42 | 18 | 6 |
|---|---|---|---|---|---|
| X | 1 | 0 | 1 | -4 | 9 |
| Y | 0 | 1 | -4 | 17 | -38 |
講到這裡，我想這個表格就可以足夠引導各位自行完成演算法，在學習的演算法時，有時候了解核心思路之後自己寫出來，會很有成就感，也會具有更靈活運用的能力。
解題思路上面有點類似動態規劃：「小事化了、大事化小」
