最小公因數

最小公因數（Greatest Common Divisor，GCD），也稱為最大公約數，是指兩個或更多個整數中最大的那個共同約數。例如，對於整數24和36，它們的最小公因數是12，因為12是24和36的約數，而且沒有比12更大的共同約數。

在數學中，最小公因數可以用質因數分解來找到。例如，要找到24和36的最小公因數，我們可以將它們分解為質因數：

24 = 2^3 3^1 36 = 2^2 3^2

觀察質因數，我們可以看到2^2和3^1是兩數都共有的質因數，因此它們的最小公因數是2^2 * 3^1 = 12。

另一種找到最小公因數的方法是使用歐幾里得算法（Euclidean algorithm），這是一個有效的算法，可以用來找出兩個整數的最小公因數。以下是使用歐幾里得算法的步驟：

1. 設兩個數為a和b，其中a >= b。
2. 計算a除以b的餘數，記作r。
3. 如果r = 0，則b就是a和b的最小公因數；如果r != 0，則以b替換a，以r替換b，並回到第二步。

例如，要找到24和36的最小公因數，我們可以這樣做：

a = 24, b = 36 r = 24 % 36 = 24 因為r != 0，所以我們用b（36）替換a（24），用r（24）替換b（36），並再次計算餘數：

a = 36, b = 24 r = 36 % 24 = 12 因為r != 0，所以我們用b（24）替換a（36），用r（12）替換b（24），並再次計算餘數：

a = 24, b = 12 r = 24 % 12 = 12 因為r != 0，所以我們用b（12）替換a（24），用r（12）替換b（12），並再次計算餘數：

a = 12, b = 12 r = 12 % 12 = 0 因為r = 0，所以12就是24和36的最小公因數。

最小公因數在數學和實際應用中都非常重要，例如在計算兩個線段的最低公倍數、解線性 Diophantine 方程、數論和工程學中都有應用。