最大公约数

最大公因數（Greatest Common Divisor，簡寫為G.C.D.；或Highest Common Factor，簡寫為H.C.F.），指某几個整數共有因數中最大的一個。

求兩個整數最大公因數主要的方法：

• 列舉法：各自列出因數，再找出最大的公因數。
• 質因數分解法：兩數各作質因數分解，然後取出同樣有的項乘起來。
• 短除法
• 輾轉相除法（擴展版）：常使用於直觀上不容易判別公因數的場合。

兩個整數的最大公因數和最小公倍數（L.C.M.）的關係： $G.C.D.(a, b) \times L.C.M.(a, b) = |ab|$

兩個整數的最大公因數可用於計算兩數的最小公倍數，或分數化簡成最簡分數。

兩個整數的最大公因數和最小公倍數中存在分配律：

• $G.C.D.(a,\;L.C.M.(b, c)) = L.C.M.(G.C.D.(a, b)),\;G.C.D.(a, c))$
• $L.C.M.(a,\;G.C.D.(b, c)) = G.C.D.(L.C.M.(a, b)),\;L.C.M.(a, c))$

在座標裏，將點（0, 0）和（a, b）連起來，通過整數座標的點的數目（除了（0, 0）一點之外）就是G.C.D.(a, b)。

粗體文字==其他== 數字之間的最大公因數之所有因數是該組數字所有的公因數。

c# 最大公因數遞迴 Code:

       /// <summary>
       /// GCD最大公因數遞迴演算法
       /// </summary>
       private int GCD(int a, int b)
       {
           int max = Math.Max(a, b);
           int min = Math.Min(a, b);
           if (max%min!=0)
               return GCD(min, (max%min));
           return min;
       }

参见

• 公倍数
• 公约数