最大公因數定義

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

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

12 = 2^2 3^1 18 = 2^1 3^2

現在，我們可以看到兩個數字都包含因子2和3。為了找到GCD，我們取兩個數字中最低的次方，即2^1和3^1，然後將它們相乘：

GCD(12, 18) = 2^1 3^1 = 2 3 = 6

因此，12和18的最大公因數是6。

有時候，最大公因數也用於計算兩個數字的最低公倍數（Least Common Multiple, LCM）。最低公倍數是兩個或更多個整數中能夠被它們每個都整除的最小數字。最低公倍數和最大公因數之間存在一個簡單的關係：

LCM(a, b) GCD(a, b) = a b

其中，a和b是任意兩個整數。