最大公因數（GCD）

假設現在有兩個數 A、B，他們都可以被一個數字 d 整除，那這個 d 是 A 的因數，同時也是 B 的因數，那我們就可以說 d 是 A、B 的公因數；但公因數可能不會只有一個，那其中最大的那個公因數我們就稱為 最大公因數 (Greatest Common Diviser)。

• 例：16、24 的公因數有 {1,2,4,8}，8 就是最大公因數，gcd(16,24)=8
• 另外，如果 gcd(A,B)=1，我們就可以說 A、B 互質。

那 GCD 我們可以用在哪裡呢？

像是分數約分、密碼學（RSA 裡常用 mod 要用到 GCD）、資料分割或排程(Scheduling)時的最小單位。

尋找最大公因數

可能有些人在找兩個數 A、B 的第一個想法是直接找出兩數所有的因數，在找到其中相同且最大的部分。

舉個例子，我們有兩個數 40、24

1. 找出 40 的因數 {1,2,4,5,8,10,20,40}
2. 找出 24 的因數 {1,2,3,4,6,8,12,24}
3. 再透過比對後找出數字 8 為 GCD

但如果數字越來越大的話，這樣求解可能會花上許多時間

而這只是其中一個例子，但還有很多其他不同的方法

其中有一個很厲害的演算法就叫做歐幾里得演算法，也就叫做輾轉相除法，可能有些人國中小就已經學過了。

輾轉相除法的原理

一樣拿上面的例子 40、24 算法如下：

1. 40 ÷ 24 = 1 餘 16
2. 24 ÷ 16 = 1 餘 8
3. 16 ÷ 8 = 2 (整除)

當我們算到 最後可以整除別人的的那個數就是最大公因數

想比起前面慢慢找的快了許多

那為什麼這樣可以解出 GCD 呢?

首先我們需要先知道一些事，現在我們有兩個數字 A、B，且他們不互質 (gcd(A,B)≠1)

1. 這兩個數字的關係可以寫成 A = q × B + r，其中 q 就是商數，r 是餘數

2. 假設 A、B 的公因數是 d，那 A=q×B+r 的 r 也可以被 d 整除

   • A = q × B + r ⇒ (d × a) = q × (d × b) + r ⇒ r = d × (a - q × b)

現在我們拿前面的例子 40、24，透過輾轉相除法後可以得到 GCD 為 8，如下圖所示。

假設我們現在 8 不是 GCD 而是一個比 8 大的數 k，那這個 k

• 可以整除 40，因為是他的因數
• 可以整除 24，因為是他的因數
• 可以整除 16，根據剛剛的餘數也可以被整除
• 可以整除 8，根據剛剛的餘數也可以被整除

那奇怪的地方就來了，既然 k 是 GCD 且比 8 大，那又怎麼能整除 8 呢？

所以輾轉相除法最後所得出的數就是最大公因數 (GCD)。

最後分享一句

We might call Euclid's method the granddaddy of all algorithms, because it
is the oldest nontrivial algorithm that has survived to the present day.
-- Donald Knuth

參考資料
Euclid’s elements of geometry (Book 7)
維基百科《輾轉相除法》