C最大公因式

在數學中，最大公因數（Greatest Common Divisor，GCD）也稱為最大公約數或最大公因子，是指兩個或多個整數共有最大的正因子。在許多情況下，最大公因數可以通過輾轉相除法來計算。

例如，對於整數24和36，它們的最大公因數是12，因為12是24和36都除得盡的最大的正整數。

最大公因數的性質：

1. 對於任何整數a和b，有GCD(a, b) = GCD(b, a)，即最大公因數是成對整數的一個對稱概念。
2. 如果a和b互質，即它們除了1以外沒有其他的公共因子，那麼GCD(a, b) = 1。
3. 對於任何整數a和b，有GCD(a, b) = GCD(a, b - a)，這表明在尋找兩個數的最大公因數時，可以從b中減去a的倍數，直到b小於a或a為0為止。

在某些情況下，最大公因數可能不直觀，但可以使用輾轉相除法來計算。例如，要找到整數18和54的最大公因數，我們可以用54除以18，得到商3和餘數0。這意味著54可以被18整除，所以最大公因數是18。

在實際套用中，最大公因數在數論、幾何學、組合數學和計算機科學等領域都有重要作用。