最大公倍數

最大公倍數（Greatest Common Divisor，GCD），也稱為最大公因子或最大公約數，是指兩個或更多個整數共有最大的約數。例如，對於整數24和36，它們的最大公約數是12，因為12是24和36都可被整除的最大數。

在數學中，有許多方法可以計算最大公約數，其中一種常見的方法是質因數分解法。將每個數字分解為其質因數的乘積，然後從這些質因數中找出同時出現在所有數字中的那些，這些質因數的乘積就是最大公約數。

例如，要找出數字24和36的最大公約數：

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

從質因數分解中可以看出，2^2和3^1同時出現在兩個數字中，因此它們的最大公約數是2^2 3^1 = 4 3 = 12。

另一種常見的方法是使用歐幾里得算法（Euclidean algorithm），這是一種更高效的方法，可以用來找出任意兩個整數的最大公約數。歐幾里得算法的基本思想是，要找出a和b的最大公約數，可以先找出b對於a的余數r，然後用a和r重新計算最大公約數，直到r為0為止。此時，a對於b的余數就是a和b的最大公約數。

例如，要找出數字24和36的最大公約數：

36 ÷ 24 = 1 R 12 24 ÷ 12 = 2 R 0

因為余數r為0，所以最大公約數就是最後的除數，即12。