最大公因式定理

最大公因數（Greatest Common Divisor, GCD）定理，也稱為歐幾里得算法（Euclidean Algorithm），是數論中的一個基本定理，用於找出兩個整數的最大公因數。這個定理表明，對於任何兩個整數a和b，總存在整數q和r，使得a = bq + r，其中0 ≤ r < |b|。然後，我們可以通過繼續套用這個算法來找到b和r的最大公因數，直到r為0。當r為0時，上一次的餘數即為a和b的最大公因數。

歐幾里得算法的步驟如下：

1. 設a > b，計算a除以b的餘數r，即a = bq + r，其中q為整數。
2. 若r = 0，則b是a和b的最大公因數，算法結束。
3. 若r ≠ 0，交換a和b的值，即設a = b，b = r，並返回步驟1繼續計算。

通過這個算法，我們可以找到兩個整數的最大公因數。例如，要找到12和18的最大公因數，我們可以按照以下步驟進行：

1. 18 ÷ 12 = 1，餘數 r = 6。
2. 因為r ≠ 0，交換a和b的值，即設a = 12，b = 6，並返回步驟1繼續計算。
3. 12 ÷ 6 = 2，餘數 r = 0。
4. 因為r = 0，所以6是12和18的最大公因數。

因此，最大公因數定理告訴我們，對於任何兩個整數a和b，總存在一個整數d，使得d是a和b的公因數，且對於任何其他的a和b的公因數d'，都有d' ≤ d。這個d就是a和b的最大公因數。