最大公因數公式

最大公因數（Greatest Common Divisor, GCD），也稱為最大公約數，是指兩個或更多整數共有因數中最大的那一個。在數學中，求最大公因數有幾種方法，其中一種是質因數分解法，另一種是較為基礎的輾轉相除法。

輾轉相除法（Euclidean algorithm）是求兩個整數的最大公因數的一種算法，其基本思想是：gcd(a, b) = gcd(b, a mod b)，其中 a mod b 表示 a 除以 b 的餘數。用數學公式表示就是：

[ \gcd(a, b) = \begin{cases} a & \text{if } b = 0 \ \gcd(b, a \bmod b) & \text{if } b \ne 0 \end{cases} ]

這個公式可以通過遞歸的方式實現，也可以通過疊代的方式實現。以下是遞歸的實現方式：

[ \gcd(a, b) = \gcd(b, a \bmod b) ]

其中，( a \bmod b ) 表示 ( a ) 除以 ( b ) 的餘數。

以下是疊代的方式：

[ \gcd(a, b) = \begin{cases} a & \text{if } b = 0 \ \gcd(b, a \bmod b) & \text{if } b \ne 0 \end{cases} ]

這個公式可以通過不斷用較小數除以較大數，得到餘數，然後交換被除數和除數的位置，直到其中一個數為0為止。

除了輾轉相除法，還有其他求最大公因數的方法，例如質因數分解法。質因數分解法是將兩個數分別分解為質數的乘積，然後找出共同的質因數，最後將這些質因數相乘得到最大公因數。不過，這種方法通常比較慢，因為質因數分解可能需要較多的計算。