如果要求多個數的 GCD，可以先求前兩個數的 GCD，然后用這個結果與下一個數求 GCD，依次類推。 為什么可以用前兩個數的 GCD 與下一個數繼續求 GCD，從而得到所有數的 GCD 呢？（之前我不知道，自己也沒推過了。是的，我很笨）

了解到之后，知道這是GCD的結合性和傳遞性

---

1.GCD的結合性

GCD 運算滿足結合性，即：

也就是說，多個數的 GCD 可以通過逐步計算兩兩數的 GCD 來得到。

---

2.GCD的傳遞性

如果 d 是 a 和 b 的公約數，并且 d 也是 b 和 c 的公約數，那么 d 一定也是 a 和 c 的公約數，所以 d 一定是 a ，b? ，c 的公約數。因此，逐步計算GCD 不會丟失任何可能的公約數。

---

3.為什么可以逐步計算？

假設我們有三個數?a、b、c，我們需要計算?GCD(a,b,c)。

• 首先計算?GCD(a,b)，得到結果?d。

• 然后計算?GCD(d,c)，得到最終結果。

為什么可以這樣做？（體現的是結合性）

---

?4.拓展到多個數

對于多個數?a1,a2,a3,…,an，我們可以逐步計算：

每一步都保證當前的 GCD 是前面所有數的公約數，同時繼續與下一個數求 GCD，確保最終結果是所有數的最大公約數。

---

5.數學證明

假設?d=GCD(a,b,c)，我們需要證明：

d=GCD(GCD(a,b),c)

• 因為?d?是?a、b、c?的公約數，所以?d?能整除?a?和?b，因此?d?是 GCD(a,b)?的約數。

• 同時，d?能整除?c，所以?d?是?GCD(GCD(a,b),c) 的約數。

• 反過來，GCD(GCD(a,b),c) 也能整除?a、b、c，因此它一定是?d?的約數。

• 綜上，d=GCD(GCD(a,b),c)。