最大公約數公式

最大公約數（Greatest Common Divisor, GCD），也稱為最大公因數，是指兩個或更多個整數共有因數中最大的那一個。在數學中，最大公約數可以用來解決許多問題，例如將一個數字分解成其因數的和，或者找出兩個數字的最低公倍數。

最大公約數可以用許多不同的方法來計算，其中一個基本的方法是質因數分解法，另一個則是更為常用的歐幾里得算法（Euclidean algorithm）。歐幾里得算法是一個非常有效的方法，可以用來找出兩個整數的最大公約數。

歐幾里得算法的公式可以表示如下：

如果 a 和 b 是非負整數，並且 a > b，則 a 和 b 的最大公約數 GCD(a, b) 可以通過以下步驟計算：

1. 如果 b == 0，則 GCD(a, b) = a
2. 如果 b != 0，則 GCD(a, b) = GCD(b, a % b)

這裡，a % b 表示 a 除以 b 的餘數。

這個算法的基礎是，如果 a 和 b 都有因數 c，則 a % b 也應該有因數 c。因此，我們可以通過不斷地將較小的數字代入較大的數字中，直到兩個數字相等為止，來找到最大公約數。

例如，我們想要找出 120 和 60 的最大公約數。我們可以這樣做：

GCD(120, 60) = GCD(60, 120 % 60) = GCD(60, 60) = 60

因為 60 已經是 120 和 60 的最低公倍數，所以它們的最大公約數就是 60。