# 現代密碼學之數學基礎

:::spoiler 目錄
[toc]
:::

# 模運算與輾轉相除法

本節要介紹的是模運算（Modular Operations）和輾轉相除法（Euclidean Algorithm），它們可以說是密碼學計算的基礎。本段會引入一些代數術語，以精準深入的講述這些概念，不過我們先從生活一點的例子開始介紹：

## 同餘基本運算

1. 假設今天星期三，請問過了 $10000$ 天以後是星期幾呢？

假設：

1 星期一
2 星期二
3 星期三
4 星期四
5 星期五
6 星期六
0 星期日

則這個問題可以用模 7 加法來處理，也就是取餘數：

$3 + 10000\pmod 7=0$ （即 $3+10000$ 除以 $7$ 的餘數）

所以得解， $10000$ 天以後是星期日

2. 假設今天是星期三，請問 10000 天以前是星期幾？

這個問題可以用模 7 減法來處理

$3 - 10000\pmod 7=6$

所以得解， $10000$ 天以前是星期六

3. 請問 ISBN-13 978-626-353-894-8 是否合乎標準？

其實一般書籍所用的 ISBN 碼（International Standard Book Number）的最後一個數字是校驗位，它的目的是為了避免書籍在翻印、傳輸或手動輸入 ISBN 碼的過程中產生錯誤，而它就是利用模運算來達成這項功能的。

任何一本書的 ISBN-13 為 13 位之數碼：

$a_1a_2a_3\cdots a_{13}$

所有數字都在 ${0, 1, 2, \cdots, 9}$ 之中。

則 ISBN-13 必須滿足：

$$
\sum_{i=1}^{12}{w_ia_i}+a_{13}\pmod{10}=0\\
\left\{
\begin{matrix}
w=1, \text{if i is odd}\\
w=3, \text{if i is even}
\end{matrix}
\right.
$$

因此以剛剛的 ISBN-13 978-626-353-894-8 為例：

$$
(9\cdot 1+7\cdot 3+8\cdot 1+6\cdot 3+2\cdot 1+6\cdot 3+3\cdot 1+5\cdot 3+3\cdot 1+8\cdot 3+9\cdot 1+4\cdot 3)+8\pmod{10}\\
=142+8\pmod{10}=0
$$

因此這是正確的 ISBN-13，到全國新書資訊網也是查得到的喔！


## 同餘的代數結構

模運算主要的運算對象是**同餘類**。本段會以同餘為主角，提到同餘的代數結構及順道講解相關的代數知識

### 等價關係、等價類

在數學有定義許多類型的「關係」，而這邊要介紹的是集合論中所定義的「等價關係」。

:::info
**定義**：等價關係

一個關係 $\sim$ 在集合 $S$ 上被稱作等價關係若且唯若滿足以下三條性質：

1. **自反性 reflexive**：自己與自己等價
$\forall s\in S, [s\sim s]$
2. **對稱性 symmetric**：你跟我等價代表我跟你等價
$\forall x, y\in S, [x\sim y\Rightarrow y\sim x]$
3. **遞移性 transitive**：我跟你等價、你跟他等價=>我跟他等價
$\forall x, y, z\in S, [x\sim y\ \land\ y\sim z\Rightarrow x\sim z]$

**定義**：等價類

$S$ 之上的一個元素 $s$ 的等價類是收集了所有跟 $s$ 等價的元素所構成的集合，記作 $[s]$ ，形式一點來說就是

$$
[s] := \{t:t\sim s\} \subset S
$$

由於自反性 $s\sim s$ ，所以 $[s]$ 非空集合
:::

其實等價關係的定義只是建立一個**相等的概念**，以免在許多特殊情況下，我們難以描述某兩個量具備相等的概念，這邊將舉幾個簡單的例子：

1. 定義實數 $\mathbb{R}$ 上一個特殊的關係 $R$ 稱作"平方關係"，滿足： $xRy\iff\forall x, y\in\mathbb{R}, x^2=y^2$ ，試證明 $R$ 為一個等價關係。如果是等價關係，則寫出它的等價類

首先證明自反性：對於所有 $x\in\mathbb{R}$ ，可以發現 $xRx\iff x^2=x^2$ 均成立，所以 $R$ 滿足自反性

再來證明對稱性：對於所有 $x, y\in\mathbb{R}$ 有 $xRy\iff x^2=y^2$ ，因為等式關係的對稱性有 $y^2=x^2\iff yRx$ ，所以 $R$ 也滿足對稱性

最後證明遞移性：對於所有 $x, y, z\in\mathbb{R}$ 且 $xRy\iff x^2=y^2$ 和 $yRz\iff y^2=z^2$ ，根據等式的遞移性有 $x^2=y^2=z^2\Rightarrow x^2=z^2$ ，所以 $R$ 也有遞移性

因此關係 $R$ 是一種等價關係，得證。

元素 $a\in\mathbb{R}$ 在平方關係下的等價類可以表示為 $[a]=\{a^2=y^2, y\in\mathbb{R}\}$ 不過因為我們知道只有 $a, -a$ 會有一樣的平方值，因此可寫成：
$$
[a]=
\left\{
\begin{matrix}
\{a, -a\}, \text{if } a\neq 0\\
\{0\}, \text{if } a=0
\end{matrix}
\right.
$$

2. 定義實數 $\mathbb{R}$ 上一個特殊的關係 $R$ 稱作"小於關係"，滿足 $xRy\iff \forall x, y\in\mathbb{R}, x<y$ ，試證明 $R$ 為一個等價關係。如果是等價關係，則寫出它的等價類

首先證明自反性：首先取 $x\in\mathbb{R}$ 立馬就可以發現 $x < x$ 不可能成立，因為不滿足自反性，所以小於關係並非等價關係

### 同餘關係、同餘類

其實同餘關係是一種等價關係：

:::success
**證明**：同餘關係為一種等價關係

令 $n\in\mathbb{N}$ ，和 $a, b, c\in\mathbb{Z}$

1. 自反性： $a\equiv a\pmod{N}$ 成立
2. 對稱性： $a\equiv b\pmod{N}\iff b\equiv a\pmod{N}$ 成立
3. 遞移性： 有 $a\equiv b\pmod{N}$ 和 $b\equiv c\pmod{N}$ ，則 $a\equiv c\pmod{N}$ 成立

因此同餘關係為一種等價關係
:::

所以在 $N\in\mathbb{N}, a, b\in\mathbb{Z}$ ，在 $a\equiv b\pmod{N}$ 時，所有與 $a$ 同餘的整數所形成的集合，即：

$$
[a]=\{b\in\mathbb{Z}\ | \ a\equiv b\pmod{N}\}
$$

稱之為 $a$ 的同餘類，而所有的同餘類所形成的集合，即為：

$\mathbb{Z}/n=\{[x]\ | \ x\in\mathbb{Z}\}$

一般讀作"Z mod n"，也可以用 $\mathbb{Z}_n$ 或是 $\mathbb{Z}/n\mathbb{Z}$ 來表示

以下將舉一些簡單的範例：

1. $5\equiv 16\equiv -6\pmod{11}$
$[5]=\{x\in\mathbb{Z}\ | \ x\equiv 5\pmod{11}\}=[16]=[-6]$
$\mathbb{Z}/11=\{[0], [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]\}$
2. $2\equiv 9\equiv -5\equiv 10005\pmod{7}$
$[2]=\{x\in\mathbb{Z}\ |\ x\equiv 2\pmod{7}\}=[9]=[-5]=[10005]$
$\mathbb{Z}/7=\{[0], [1], [2], [3], [4], [5], [6]\}$

在集合 $\mathbb{Z}/n$ 上可定義加法、減法及乘法。
而除法有時可定義、有時不行，這要看除數是否存在乘法反元素。
這些計算以同餘類的術語，定義如下：

$a, b\in\mathbb{Z}, n\in\mathbb{N}$

* $[a]+[b]:=[a+b]=\{x\ |\ x\equiv a+b\pmod{n}\}$
* $[a]-[b]:=[a-b]=\{x\ |\ x\equiv a-b\pmod{n}\}$
* $[a]\cdot[b]:=[a\cdot b]=\{x\ |\ x\equiv a\cdot b\pmod{n}\}$

這邊放上兩張 $\mathbb{Z}/7$ 下的加法表和乘法表以增進理解：

|$+$| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 0 |
| 2 | 2 | 3 | 4 | 5 | 6 | 0 | 1 |
| 3 | 3 | 4 | 5 | 6 | 0 | 1 | 2 |
| 4 | 4 | 5 | 6 | 0 | 1 | 2 | 3 |
| 5 | 5 | 6 | 0 | 1 | 2 | 3 | 4 |
| 6 | 6 | 0 | 1 | 2 | 3 | 4 | 5 |

|$\times$| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 0 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 0 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 0 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 0 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 0 | 6 | 5 | 4 | 3 | 2 | 1 |

為了更清楚解釋同餘的代數結構，這邊要先代入一點抽象代數中群、體、環的定義

### 群(Group)

:::info
**定義**：群(Group)

群是一種有封閉性、结合律、單位元素、反元素的代數結構 （非空集合 + 二元運算）。

以 $\bullet$ 代表集合內的二元運算，一個群 $(G, \bullet)$ 必須滿足以下四大公理（Axiom）：

1. 封閉性： $\forall a, b\in G\Rightarrow a\bullet b\in G$
2. 结合律：$\forall a, b, c\in G\Rightarrow (a\bullet b)\bullet c=a\bullet(b\bullet c)$
3. 單位元素：$(\forall a\in G)(\exists e)\Rightarrow e\bullet a = a\bullet e = a$
4. 反元素：令 $e$ 為單位元素，則 $(\forall a\in G)(\exists b)\Rightarrow a\bullet b = b\bullet a = e$。此處 $b$ 為反元素，但一般都用 $a^{-1}$ 表示反元素

**定義**：交換群 a.k.a 阿貝爾群(commutative group, abelian group)

滿足交換律的群即為交換群。
一個交換群 $(G, \bullet)$ 除了群原本滿足的所有公理外，還要再加一條公理：

* 交換律： $\forall a, b\in G\Rightarrow a\bullet b = b\bullet a$

:::

> 如果存在一個的結構滿足群的全部公理，唯獨沒有《反元素》，那麼就稱之為《么半群》(Monoid) ，如果連《單位元素》也沒有，那麼就稱之為《半群》
> 如果《么半群》(Monoid)滿足交換律，又可稱為《可交換么半群》或《阿貝爾么半群》

#### 範例

* 整數 $\mathbb{Z}$ 和加法運算滿足群的所有公理，還滿足交換律，因此 $(\mathbb{Z}, +)$ 是交換群
* 自然數 $\mathbb{N}$ 的加法運算不存在反元素（因為單位元素為 $0$ ，但自然數沒有負數，所以 $(\forall a\in \mathbb{N} \wedge a\ne 0)(\nexists a^{-1})$），所以 $(\mathbb{N}, +)$ 不是一個群
* 非零有理數 $\mathbb{Q}/\{0\}$ 和乘法運算滿足群的所有公理，還滿足交換律，因此 $(\mathbb{Q}/\{0\}, \times)$ 可以形成一個交換群；但整數 $\mathbb{Z}$ 的乘法運算不存在反元素（因為單位元素為 1 ，但 $a^{-1}$ 無法用整數表達），所以 $(\mathbb{Z}, \times)$ 不是一個群
* 集合 $\mathbb{F}_2=\{0, 1\}$ 和 XOR 運算 $\oplus$ （$1\oplus1=0\oplus0=0$ 、 $1\oplus0=0\oplus1=1$）滿足群的所有公理，還滿足交換律，因此 $(\mathbb{F}_2, \oplus)$ 也是交換群
* 線性代數的矩陣可以相加也可以相乘。加法可以形成一個群；但乘法中因為有些矩陣不存在反矩陣，所以矩陣和乘法不構成群

#### 應用

1. [src1](https://zhuanlan.zhihu.com/p/352197597)
2. [src2](https://zhuanlan.zhihu.com/p/402197369)
3. [src3](https://chowkafat.net/Rubik2.html)
4. [src4](https://chowkafat.net/Rubik3.html)
5. [src5](https://zhuanlan.zhihu.com/p/146886527)

### 體(Field)

> 在台灣翻譯為《體》，在中國翻譯則為《域》

:::info
**定義**：體(Field)

體是一種可進行兩個運算（如：加法、乘法）的代數結構。體的概念是數體（Number System）以及四則運算的推廣。

群包含一個運算，而體則是包含兩個運算，像是《實數和加法與乘法》，就形成了一個體

一般習慣將體的兩個運算，用加號與乘號代表，寫為 $(F, ＋, \times)$ 。

一個體必須滿足下列公理：

1. $(F, ＋)$ 為一個交換群； $(F, \times)$ 也為一個交換群
2. $\forall a, b, c\in F$ 中 $\times$ 對 $+$ 有分配律 $a\times (b+c)=a\times b + a\times c$ 和 $(b+c)\times a=b\times a+c\times a$

具有分配律的雙重交換群結構 $(F, ＋, \times)$ ，就稱為體

:::

#### 範例

* 實數 $\mathbb{R}$的乘法和加法$(\mathbb{R}/\{0\}, +, \times)$ 是一個體
* 複數 $\mathbb{C}$的乘法和加法$(\mathbb{C}/\{0\}, +, \times)$ 是一個體
* 整數 $\mathbb{Z}$ 的乘法和加法 $(\mathbb{Z}/\{0\}, +, \times)$ 不是一個體
* （自然數對**某質數**取餘後的元素的集合）的乘法和加法可以形成一個體，這種類型的體被稱為[有限體](https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E5%9F%9F)
* 線性代數當中的向量沒有定義乘法，但是有內積與外積，這其中一個原因是向量的乘法運算無法形成一個群，詳細可參考[線性代數裡的代數結構](https://ccjou.wordpress.com/2011/09/16/%E7%B7%9A%E6%80%A7%E4%BB%A3%E6%95%B8%E8%A3%A1%E7%9A%84%E4%BB%A3%E6%95%B8%E7%B5%90%E6%A7%8B/)

### 環(Ring)

:::info
**定義**：環(Ring)

環和體很像，差異是環的 $(\times)$ 可以沒有反元素，也就是說環 $(S, +, \times)$ 滿足：

1. $(S, +)$ 為一交換群
2. $(S, \times)$ 為一么半群
:::

> 若一個環 $(S, +, \times)$ 滿足環所有的性質，且 $\times$ 還滿足交換律則稱為交換環（commutative ring）
> 換句話說就是一個為交換群、一個為可交換么半群

#### 範例

* 整數 $\mathbb{Z}$ 的加法與乘法 $(\mathbb{Z}, +, \times)$ 是一個環。因為整數乘法不存在反元素，所以 $(\mathbb{Z}, +, \times)$ 不能成為體

### 相關名詞

#### 零因子(zero divisor)

:::info
**定義**：零因子(zero divisor)

在一個環 $(S, +, \times)$ 當中，假設 $(a\in S, a\ne 0)$ 為左零因子，則下式成立

$$
(\exists b\in S)(b\ne 0 )\Leftrightarrow a\times b=0
$$

類似地，假設 $(a\in S, a\ne 0)$ 為右零因子，則下式成立

$$
(\exists b\in S)(b\ne 0 )\Leftrightarrow b\times a=0
$$

若 $a$ 滿足以上兩條件，則 $a$ 即為 $S$ 的零因子
:::

> 在交換環中，左零因子與右零因子是等價的。一個既不是左零因子也不是右零因子的非零元素稱為正則的。

##### 性質

* 左零因子或右零因子不可能是可逆元素
* $\mathbb{Z}/n$ 包含零因子，若且唯若 $n$ 是合數；如果 $n$ 是質數， $\mathbb{Z}/n$ 是一個體，因此沒有零因子，因為每個非零元素都是可逆的。
* 一個非退化的交換環（$0 \ne 1$）若沒有零因子，則是一個[整環](https://zh.wikipedia.org/zh-tw/%E6%95%B4%E7%8E%AF)。

> 為什麼質數模下，所有非零元素都可逆的原因後面一點會介紹

### 整數同餘交換環 Z/n

表示 $\mathbb{Z}/n$ 的元素時，通常會在每一個同餘類中各取一個元素形成**代表系統（Representative System）** 來代表 $\mathbb{Z}/n$ ，如 $\mathbb{Z}/3$ 可以以代表系統 $\{0, 1, 2\}$ 或 $\{3, 4, 8\}$ 代表之。

但在 $\mathbb{Z}/n$ 上，一般還是習慣取代表系統

$$
\{0, 1, 2, 3, \cdots, n-1\}
$$

代表之；有時候為了方便計算，也會取代表系統

$$
\{-\lceil \frac{n-1}{2}\rceil, \cdots, -2, -1, 0, 1, 2, \cdots, \lceil \frac{n-1}{2}\rceil\}
$$

或是

$$
\{-\lfloor \frac{n-1}{2}\rfloor, \cdots, -2, -1, 0, 1, 2, \cdots, \lfloor \frac{n-1}{2}\rfloor\}
$$

且已知 $\mathbb{Z}/n$ 的加法運算滿足以下性質：

* 封閉性：若同餘類 $x, y\in\mathbb{Z}/n$ ，則 $x+y\in\mathbb{Z}/n$ 恆成立
* 結合律：若同餘類 $x, y, z\in\mathbb{Z}/n$ ，則 $(x+y)+z=x+(y+z)$ 恆成立
* 加法單位元素： $(\forall x\in \mathbb{Z}/n)(\exists 0=[0])\Rightarrow 0+x = x+0 = x$ 恆成立
* 加法反元素：$(\forall a\in\mathbb{Z}/n)(\exists (-a))\Rightarrow a+ (-a) = (-a)+ a = 0$ 恆成立
* 交換律：若同餘類 $x, y\in\mathbb{Z}/n$ ，則 $x + y=y+x$ 恆成立

因此 $\mathbb{Z}/n$ 滿足交換群所有的公理，即 $(\mathbb{Z}/n, +)$ 為交換群。

此時可以再加上乘法，考慮 $(\mathbb{Z}/n, +, \times)$

已知 $(\mathbb{Z}/n, +)$ 為交換群，先單獨看 $(\mathbb{Z}/n, \times)$

* 封閉性：若同餘類 $x, y\in\mathbb{Z}/n$ ，則 $x\times y\in\mathbb{Z}/n$ 恆成立
* 結合律：若同餘類 $x, y, z\in\mathbb{Z}/n$ ，則 $(x\times y)\times z=x\times (y\times z)$ 恆成立
* 乘法單位元素： $(\forall x\in\mathbb{Z}/n)(\exists 1=[1])\Rightarrow x\times 1=1\times x=x$ 恆成立
* 交換律：若同餘類 $x, y\in\mathbb{Z}/n$ ，則 $x\times y=y\times x$ 恆成立

因為不滿足存在乘法反元素，所以 $(\mathbb{Z}/n, \times)$ 為可交換么半群。

> $(\mathbb{Z}/n, \times)$ 不總是存在乘法反元素，這也是為什麼沒有定義除法的原因

$(\mathbb{Z}/n, +)$ 為交換群加上 $(\mathbb{Z}/n, \times)$ 為可交換么半群，根據前面講到的，我們可以稱 $(\mathbb{Z}/n, +, \times)$ 為交換環（Commutative Ring）。

不過為什麼 $\mathbb{Z}/n$ 下乘法不總是存在反元素呢？在此之前要先了解什麼是同餘類 $[a]$ 在 $\mathbb{Z}/n$ 下「乘法反元素」？

其實這等同是在解以下同餘方程式：

$$
ax\equiv 1\pmod n
$$

因此我們接下來要介紹能夠解上面方程式的數學工具

## 輾轉相除法（Euclidean Algorithm）

### 帶餘除法 a.k.a 歐幾里德除法（Euclidean division）

帶餘除法是一種數學中一種基本的算術計算方式。

:::info
**定義**：帶餘除法

給定一個被除數 $a$ 和一個除數 $b$ ，帶餘除法會給出一個整數 $q$ 和一個界於一定範圍的整數 $r$ ，使得以下等式成立：

$a=bq+r$

餘數 $r$ 的範圍一般會限定在 $[0, b)$ 之中，有時候為了計算需要也會限定在 $[-\frac{b}{2}, \frac{b}{2})$ 之間，而之所以要這樣限定是為了讓滿足等式的 $q$ 只有一個。

此時的 $q$ 稱為帶餘除法的商，整個等式一般表示為：

$a\div b=q\cdots r$

代表「 $a$ 除以 $b$ 等於 $q$ ，餘 $r$」，如果餘數 $r$ 為零，則稱 $b$ 整除 $a$ ，且定義除數 $b$ 不可為零
:::

與以上定義相伴的還有一個公式：

* 整數與整數的帶餘除法中，只要餘數的範圍總共只有 $\left\vert b\right\vert$ 個整數（如：　$\{0, 1, \cdots, \vert b\vert-1 \}$），並且任何兩個數之差都不是 $b$ 的倍數，那麼帶餘除法的商 $q$ 唯一存在

:::success
**證明**：整數與整數的帶餘除法中，只要餘數的範圍總共只有 $\left\vert b\right\vert$ 個整數，並且任何兩個數之差都不是 $b$ 的倍數，那麼帶餘除法的商 $q$ 唯一存在

假設餘數範圍集合為 $R=\{r_1, r_2, \cdots, r_{\left\vert b\right\vert}\}$ ，其中任兩數的差都不是 $b$ 的倍數。那麼可以將全體整數的集合分割成以下集合的[互斥聯集（Disjoint Union）](https://zh.wikipedia.org/wiki/%E4%B8%8D%E4%BA%A4%E5%B9%B6)

$\mathbb{Z}=\sqcup_{k\in\mathbb{Z}}{\{r_1+kb, r_2+kb, \cdots, r_{\left\vert b\right\vert} + kb\}}=\sqcup_{k\in\mathbb{Z}}{R_k}$

---

先證明這樣的劃分下，不會有集合有交集：

利用反證法，假設集合 $R_k$ 和 $R_l$ 有交集，這代表它們至少有一個元素是相同的，因此有：

$$
r_i + kb=r_j + lb\\
\Rightarrow r_i-r_j=lb-kb\\
\Rightarrow r_i-r_j=(l-k)b
$$

與原本的 $R$ 中任兩數的差都不是 $b$ 的倍數的假設矛盾，得證

---

接著再證明，任何整數都必定屬於某個 $R_k$

設一整數 $s\in\mathbb{Z}$ ，那麼會存在一個整數 $q_s$ 使得 $bq_s\le s\le b(q_s+1)$ ，也就是說存在 $\{0, 1, \cdots, \vert b\vert-1 \}$ 之中的某個數 $t_s$ ，使得 $s=bq_s+t_s$ ；

而對於餘數集合　$R=\{r_1, r_2, \cdots, r_{\left\vert b\right\vert}\}$　之中的每個數 $r_i$ 也都各自有 $\{0, 1, \cdots, \vert b\vert-1 \}$ 中的一數 $t_i$ 和一個整數 $q_i\in\mathbb{Z}$ ，使得 $r_i=bq_i+t_i$ 。

一樣用反證法的思路，假設 $s$ 不屬於任何的 $R_k$ ，這代表前面構成 $s$ 的 $t_s$ 也不能和 $R$ 之中任何一個 $r_i$ 對應到同一個 $t_i$ ，這代表 $\{0, 1, \cdots, \vert b\vert-1 \}$ 之中除了 $R$ 的 $\vert b\vert$ 個元素以外要再擠一個 $s$ 進來，代表一共有 $\vert b\vert + 1$ 個元素屬於 $\{0, 1, \cdots, \vert b\vert-1 \}$。

根據 [鴿籠原理](https://zh.wikipedia.org/wiki/%E9%B4%BF%E5%B7%A2%E5%8E%9F%E7%90%86) ，此時必有兩個元素相等。可是根據前面所證（在此劃分下，不會有集合有交集）的結論， $R$ 之中不會有兩個相同的元素，因此只能是存在某個 $i$ 使 $t_i=t_s$ ，所以：

$$
s=bq_s+t_s=bq_s+t_i=bq_s+r_i-bq_i\\
\Rightarrow s=r_i+b(q_s-q_i)\in R_{q_s-q_i}
$$

因此，任何整數 $s$ 都唯一地屬於某個 $R_k$ ，而 $(q_s-q_i)$ 或是前面定義的 $k$ 就是我們帶餘除法唯一的商

:::

### 輾轉相除法 a.k.a 歐幾里得演算法

輾轉相除法，是一個求兩數的最大公因數的演算法。

輾轉相除法是一種遞迴演算法，每一步計算的輸出都會是下一次計算的輸入。

設 $k$ 表示步驟數（從 0 開始），演算法流程如下：

輸入為前兩次的輸出 $r_{k-2}, r_{k-1}$ 。在第 $k$ 步中，演算法利用帶餘除法計算出滿足以下等式的商 $q_{k-1}$ 和餘數 $r_k$ ：

$$
r_{k-2}=r_{k-1}q_{k-1}+r_k
$$

其中 $0\le r_k<r_{k-1}$ ，所以每一步的餘數都會逐步變小，而且過程不含負數，所以必然存在第 $n$ 步使 $r_n=0$ ，因為 0 是任何數字的倍數，算法終止，最大公因數即為 $r_{n-1}$。因為 $r_{-2}$ 與 $0$ 之間只有有限的自然數，因此 $n$ 也會是有限的步驟。

> 可以注意到，其實它的原理就是讓大數變小數、再讓小數把另一個數變小，這樣來回運算。可是如果一開始的 $r_{-2}<r_{-1}$ 怎麼辦？
> 其實這是沒關係的，因為 $r_{-2}<r_{-1}$ 時，$r_{-2}=r_{-1}\cdot 0+r_0\Rightarrow r_0=r_{-1}$ ，你會發現第一次後兩個數就會自己交換，所以順序其實沒差

如果用遞迴式來表示演算法，即為：
（ $\gcd{(a, b)}$ 表示 $a, b$ 的最大公因數）

$$
\gcd{(a, b)}
\left\{
\begin{matrix}
& a, \text{if }b = 0\\
& \gcd{(b, a\!\!\!\mod b)}, \text{otherwise}
\end{matrix}
\right.
$$

以下是用表列的方式推算輾轉相除法，求 $7812$ 和 $6084$ 的最大公因數。

| $k$ | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
|-------|------|------|------|-----|-----|----|----|---|
| $r_k$ | 7812 | 6084 | 1728 | 900 | 828 | 72 | 36 | 0 |
| $q_k$ | | 1 | 3 | 1 | 1 | 11 | 2 | |

:::success
**證明**：輾轉相除法的正確性 --- 方法 1

由於輾轉相除法是基於 $\gcd{(a, b)}=\gcd{(b, a\!\!\!\mod b)}$ 這個事實才得以進行的，因此只要證明等式成立即可。

令 $x=\gcd{(a, b)}, y=\gcd{(b, a\!\!\!\mod b)}$ ，此時存在唯一的非負整數 $r, q$ ，滿足：

$$
a=bq+r, 0\le r<b
$$

其中 $r=a\!\!\!\mod b$ 為餘數。

（$a\mid b$ 代表 $a$ 是 $b$ 的因數）

1. 步驟一

因為 $x=\gcd{(a, b)}$ ，所以 $x\mid a,x\mid b$ ，因此可令 $k, l\in\mathbb{N}, a=kx, b=lx$ 。

因為 $r=a-bq=kx-lxq=x(k-lq)$ ，可得到 $x\mid r$

所以有
$$
y=\gcd{(b, r)}=\gcd{(lx, x(k-lq))}\\
\Rightarrow x\mid y
$$
2. 步驟二

因為 $y=\gcd{(b, r)}$ ，所以 $y\mid b, y\mid r$ ，因此可令 $m, n\in\mathbb{N}, b=my, r=ny$ 。

因為 $a=bq+r=myq+ny=y(mq+n)$ ，可得到 $y\mid a$

所以有

$$
x=\gcd{(a, b)}=\gcd{(y(mq+n), my)}\\
\Rightarrow y\mid x
$$
3. 步驟三
因為 $x\mid y, y\mid x(x, y\in\mathbb{N})\Rightarrow x=y$ ，得證

**證明**：輾轉相除法的正確性 --- 方法 2

（$a\mid b$ 代表 $a$ 是 $b$ 的因數）

證明分兩步，首先證明演算法的結果 $r_{n-1}$ 是初始值 $a, b$ 的公因數，表示 $r_{n-1}\mid \gcd{(a, b)}$；再證明 $\gcd{(a, b)}\mid r_{n-1}$ ，此時兩個不等式就只會在 $r_{n-1}=\gcd{(a, b)}$ 時成立

1. 步驟一

因為 $r_n=0$ ，所以 $r_{n-2}=r_{n-1}q_{n-1}+0\Rightarrow r_{n-1}\mid r_{n-2}$

因為 $r_{n-1}\mid r_{n-2}$ ，所以也可推出 $r_{n-3}=r_{n-2}q_{n-2}+r_{n-1}\Rightarrow r_{n-1}\mid r_{n-3}$

使用同樣的方法不斷進行，可以證明 $r_{n-1}$ 能夠整除其之前的所有餘數，包括初始值 $a, b$ ，即 $r_{n-1}$ 是 $a, b$ 的公因數，這表示 $r_{n-1}\mid \gcd{(a, b)}$

2. 步驟二

令 $g=\gcd{(a, b)}, m, n\in\mathbb{N}$ ，則 $a=mg, b=ng$ 。

按照演算法的描述 $r_{-2}=a, r_{-1}=b$ ，則可知道：
$$
r_{-2}=r_{-1}q_{-1}+r_0\Rightarrow r_0=r_{-2}-r_{-1}q_{-1}\\
\Rightarrow r_0=mg-ngq_{-1}\Rightarrow r_0=g(m-nq_{-1})
$$

這表示 $g\mid r_0$ ，這代表我們也可以推出：
$$
r_{-1}=r_{0}q_{0}+r_1\Rightarrow r_1=r_{-1}-r_0q_{0}\\
\Rightarrow r_{1}=ng-g(m-nq_{-1})q_0=g(n-(m-nq_{-1})q_0)
$$

這代表 $g\mid r_1$ ，使用同樣的方法不斷進行，可以證明 $g\mid r_{n-1}\Rightarrow \gcd{(a, b)}\mid r_{n-1}$

因為 $r_{n-1}\mid \gcd{(a, b)}$ 且 $\gcd{(a, b)}\mid r_{n-1}$ ，所以可以知道 $r_{n-1}=\gcd{(a, b)}$ ，得證。
:::

### 擴展歐幾里得算法

這是剛剛的輾轉相除法的擴展，對於自然數 $a, b\in\mathbb{N}$ 它除了 $\gcd{(a, b)}$ 以外，還能找到兩整數 $x, y\in\mathbb{Z}$ ，使得：

$$
ax+by=\gcd{(a, b)}
$$

它的流程是利用剛剛輾轉相除法沒有用到的商 $q$，來直接構造出一組 $x, y$ 滿足上面的方程式的。

這邊先直接舉例，求整數 $x, y$ 使得 $7812x+6084y=\gcd{(7812, 6084)}$ ：

| $k$ | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
|-------|------|------|------|-----|-----|----|------|------|
| $r_k$ | 7812 | 6084 | 1728 | 900 | 828 | 72 | 36 | 0 |
| $q_k$ | | 1 | 3 | 1 | 1 | 11 | 2 | |
| $x_k$ | 1 | 0 | 1 | -3 | 4 | -7 | 81 | -169 |
| $y_k$ | 0 | 1 | -1 | 4 | -5 | 9 | -104 | 217 |

其中

$$
\left\{
\begin{matrix}
x_{k}=x_{k-2}-q_{k-1}x_{k-1}\\
y_{k}=y_{k-2}-q_{k-1}y_{k-1}
\end{matrix}
\right.
$$

而初始狀態

$$
\left\{
\begin{matrix}
x_{-2}=1, x_{-1}=0\\
y_{-2}=0, y_{-1}=1
\end{matrix}
\right.
$$

其中

$$
r_k=x_ka+y_kb
$$

因此本例子中 $x=81, y=-104$ ，得到一組特殊解：

$$
7812\times 81 + 6084\times (-104)=36
$$

一般解為：

$$
x=81-169t, y=-104+217t, t\in\mathbb{Z}
$$

我知道上面範例可能會讓人一頭霧水，以下將開始證明和解釋：

:::success
**證明**： $r_k=x_ka+y_kb, (k=-2, -1, 0, 1\cdots)$

> 個人認為其實與其說是「證明」，更像是從零開始「構造」出我們要的數字，所以就算我們就算忘記了 $x_k, y_k$ 的公式要怎麼算，如下推導也可以重新導出那兩條公式。

注意到：

$$
r_{-2}=a=1\cdot a+0\cdot b\\
r_{-1}=b=0\cdot a+1\cdot b
$$

$$
\left\{
\begin{matrix}
x_{k}=x_{k-2}-q_{k-1}x_{k-1}\\
y_{k}=y_{k-2}-q_{k-1}y_{k-1}
\end{matrix}
\right.
$$

在初始情況已經成立了，接著根據[第二數學歸納法](https://zh.wikipedia.org/zh-tw/%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95#%E5%AE%8C%E6%95%B4%E5%BD%92%E7%BA%B3%E6%B3%95)，假設等式在 $k'\le k$ 皆成立，則：

$$
r_{k+1}=r_{k-1}-r_k\cdot q_k\\
=(x_{k-1}a+y_{k-1}b)-(x_ka+y_kb)q_k\\
=(x_{k-1}a-x_ka\cdot q_k)+(y_{k-1}b-y_kb\cdot q_k)\\
=(x_{k-1}-x_kq_k)a+(y_{k-1}-y_kq_k)b\\
=x_{k+1}a+y_{k+1}b
$$

得證

:::

以這種方式計算，用 C++ 來實作該演算法就會像以下那樣：

pair<int, pair<int, int>> exgcd(int a, int b) {
    int px = 1, x = 0;
    int py = 0, y = 1;
    while (b) {
        int q = a / b, r = a % b;
        a = b;
        b = r;
        int tmp_x = x, tmp_y = y;
        x = px - x * q;
        y = py - y * q;
        px = tmp_x, py = tmp_y;
    }
    return {a, {x, y}};
}

不過其實該演算法還能用遞迴式的方式、由下而上來計算：

假設 $x\cdot r_{i-2}+y\cdot r_{i-1}=\gcd{(r_{i-2}, r_{i-1})}$
且 $\gcd{(r_{i-1}, r_{i-2}\!\!\!\mod\!r_{i-1})}=x'\cdot r_{i-1}+y'\cdot r_{i-2}\!\!\!\mod\!r_{i-1}$
則

$$
\left\{
\begin{matrix}
x=y'\\
y=x'-\lfloor\frac{a}{b}\rfloor\cdot y'
\end{matrix}
\right.
$$

這種做法的證明如下：

:::success
**證明**：
$$
\left\{
\begin{matrix}
x=y'\\
y=x'-\lfloor\frac{a}{b}\rfloor\cdot y'
\end{matrix}
\right.
$$

> 這部分的證明，感覺就像從輾轉相除法的遞迴式中，直接推出一個合法的解

令 $x, x', y, y'\in\mathbb{Z}$ ，且 $ax+by=\gcd{(a, b)}$ 和 $(b)x'+(a\!\!\!\mod\! b)y'=\gcd{(b, a\!\!\!\mod\! b)}$

則有：

$$
ax+by=\gcd{(a, b)}=\gcd{(b, a\!\!\!\!\!\mod\! b)}\\
\Rightarrow (b)x'+(a\!\!\!\mod\! b)y'=\gcd{(b, a\!\!\!\!\!\mod\! b)}\\
\Rightarrow b\cdot x'+(a-\lfloor\frac{a}{b}\rfloor\cdot b)\cdot y'=\gcd{(b, a\!\!\!\!\!\mod\! b)}\\
\Rightarrow b\cdot x'+a\cdot y'-\lfloor\frac{a}{b}\rfloor\cdot b\cdot y'=\gcd{(b, a\!\!\!\!\!\mod\! b)}\\
\Rightarrow a\cdot y'+b(x'-\lfloor\frac{a}{b}\rfloor\cdot y')
$$

因此 $x=y', y=x'-\lfloor\frac{a}{b}\rfloor\cdot y'$
:::