何謂最大公因數

最大公因數（Greatest Common Divisor，GCD），也稱為最大公約數或最大公因子，是指兩個或更多個整數中最大的那個共同因子。一個數的因子是能夠整除該數的數字，例如，5是25的因子，但不是10的因子。

在數論中，兩個數的GCD可以用質因數分解來找到。例如，要找到12和18的GCD，我們可以將它們分解為質因數：

12 = 2 × 2 × 3 18 = 2 × 3 × 3

現在，我們可以看到12和18都包含因子2和3，但最大的共同因子是6（2 × 3），因為它是12和18都包含的最大的因子。

在許多情況下，最大公因數可以用以下方法來找到：

試除法：將較小的數字除以較大的數字，直到找到一個除不盡的餘數，這個餘數就是較小的數字對應的GCD。
質因數分解法：將兩個數分解為質因數，然後找出它們共有的質因數，將這些質因數相乘得到GCD。
歐幾里得算法（Euclidean algorithm）：這是一個高效的算法，可以用來找到兩個數的GCD。這個算法的基本思想是，如果a > b，那麼GCD(a, b) = GCD(b, a mod b)，其中a mod b表示a除以b的餘數。

最大公因數在數學和實際問題中都有很多應用，例如在計算機科學中的編碼和解碼、機械製造中的材料切割、數學競賽和遊戲等。