最大公因數

最大公因數（英語：highest common factor，hcf）也稱最大公約數（英語：greatest common divisor，gcd）是數學詞彙，指能夠整除多個非零整數的最大正整數。例如8和12的最大公因數為4。

整數序列${\displaystyle a}$的最大公因數可以記為${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$或${\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})}$。

最大公因數的值至少為1，例如${\displaystyle \gcd(3,7)=1}$；最大則為該組整數中絕對值最小的絕對值，例如${\displaystyle \gcd(3,9)=3}$和${\displaystyle \gcd(-3,9)=3}$。

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

• 列舉法：分別列出兩整數的所有因數，並找出最大的公因數。
• 質因數分解：分別列出兩數的質因數分解式，並計算共同項的乘積。
• 短除法：兩數除以其共同質因數，直到兩數互質時，所有除數的乘積即為最大公因數。
• 歐幾里得算法：${\displaystyle \gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)}$

兩個整數${\displaystyle a,b}$的最大公因數和最小公倍數（lcm）的關係為：

${\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=|ab|}$

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

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

${\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c))}$

${\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c))}$

在直角坐標中，兩頂點為${\displaystyle (0,0),(a,b)}$的線段會通過${\displaystyle \gcd(a,b)+1}$個格子點。

概述

例子

54和24的最大公因數是多少？

數字54可以表示為幾組不同正整數的乘積：

${\displaystyle 54=1\times 54=2\times 27=3\times 18=6\times 9}$

故54的正因數為${\displaystyle 1,2,3,6,9,18,27,54}$。

同樣地，24可以表示為：

${\displaystyle 24=1\times 24=2\times 12=3\times 8=4\times 6}$

故24的正因數為${\displaystyle 1,2,3,4,6,8,12,24}$。

這兩組數列中的共同元素即為54和24的公因數：

${\displaystyle 1,2,3,6}$

其中的最大數6即為54和24的最大公因數，記為：

${\displaystyle \gcd(54,24)=6}$

互質數

如果兩數的最大公因數為1，那麼這兩個數互質。例如，9和28就是互質數。

幾何角度的說明

24乘60的矩形被十個12乘12的正方形格子完全覆蓋，即12為24和60的最大公因數。推而廣之，如果c是a和b的最大公因數，那麼a乘b的矩形就可以被若干個邊長為c的正方形格子完全覆蓋。

假設有一個大小為24乘60的矩形區域，這個區域可以按照不同的大小劃分正方形網格：1乘1、2乘2、3乘3、4乘4、6乘6、12乘12。因此，12是24和60的最大公因數。大小為24乘60的矩形區域，可以按照12乘12的大小劃分正方形網格，一邊有兩格（${\displaystyle {\frac {24}{12}}=2}$）、另一邊有五格（${\displaystyle {\frac {60}{12}}=5}$）。

計算

質因數分解法

可以通過質因數分解來計算最大公因數。例如計算${\displaystyle \gcd(18,84)}$，可以先進行質因數分解 ${\displaystyle 18=2\times 3^{2}}$ 和 ${\displaystyle 84=2^{2}\times 3\times 7}$，因為其中表達式${\displaystyle 2\times 3}$的「重合」，所以${\displaystyle \gcd(18,84)=6}$。實踐中，這種方法只在數字比較小時才可行，因為對較大數進行質因數分解通常會耗費大量的時間。

再舉一個用文氏圖表示的例子，計算48和180的最大公因數。首先對這兩個數進行質因數分解：

${\displaystyle 48=2\times 2\times 2\times 2\times 3}$

${\displaystyle 180=2\times 2\times 3\times 3\times 5}$

它們之中的共同元素是兩個2和一個3：

^[1]

最小公倍數${\displaystyle =2\times 2\times (2\times 2\times 3)\times 3\times 5=720}$

最大公因數${\displaystyle =2\times 2\times 3=12}$

輾轉相除法

相比質因數分解法，輾轉相除法的效率更高。

計算${\displaystyle \gcd(18,48)}$時，先將48除以18得到商2、餘數12，然後再將18除以12得到商1、餘數6，再將12除以6得到商2、餘數0，即得到最大公因數6。我們只關心每次除法的餘數是否為0，為0即表示得到答案。這一算法更正式的描述是這樣的：

${\displaystyle \gcd(a,0)=a}$

${\displaystyle \gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)}$

其中

${\displaystyle a\,\mathrm {mod} \,b=a-b\left\lfloor {a \over b}\right\rfloor }$

如果參數都大於0，那麼該算法可以寫成更簡單的形式：

${\displaystyle \gcd(a,a)=a}$,

${\displaystyle \gcd(a,b)=\gcd(a-b,b)\quad }$ 如果 a > b

${\displaystyle \gcd(a,b)=\gcd(a,b-a)\quad }$ 如果 b > a

使用輾轉相除法計算62和36的最大公因數2的演示動畫。

性質

• 任意a和b的公因數都是${\displaystyle \gcd(a,b)}$的因數。
• ${\displaystyle \gcd }$函數滿足交換律：${\displaystyle \gcd(a,b)=\gcd(b,a)}$。
• ${\displaystyle \gcd }$函數滿足結合律：${\displaystyle \gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)}$

程式代碼

以下使用輾轉相除法實現。

C#

private int GCD(int a, int b) {
	if(0 != b) while(0 != (a %= b) && 0 != (b %= a));
	return a + b;
}

C++

運行時計算實現：

template<typename T>
T GCD(T a, T b) {
	if(b) while((a %= b) && (b %= a));
	return a + b;
}

編譯時計算實現：

#include <iostream>
#include <type_traits>

template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a, std::enable_if_t<std::is_integral<T>::value, T> b>
struct HCF{
public:
    static const T value=HCF<T, (a>b? b: a), (a>b? a%b: b%a)>::value;
};
template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a>
struct HCF<T, a, 0>{
public:
    static const T value=a;
};
int main(){
    std::wcout<<HCF<int, 12, 64>::value<<std::endl;//Output: 4
}

C

int GCD(int a, int b) {
	if (b) while((a %= b) && (b %= a));
	return a + b;
}

Java

private int GCD(int a, int b) {
    if (b==0) return a; 
	return GCD(b, a % b);
}

JavaScript

const GCD = (a, b) => b ? GCD(b, a % b) : a;

Python

GCD = lambda a, b: (a if b == 0 else GCD(b, a % b))

# or

def GCD(a, b):
    if b == 0:
        return a
    return GCD(b, a % b)

政治用法

參見：共識決策法和香港核心價值

最大公約數又指一社會中不同陣營勉強所達之共同利益。

參考文獻

1. Gustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", [[Wolfram Demonstrations Project]], Published: February 1, 2013.. [2018-06-11]. （原始內容存檔於2020-09-22）.

外部連結

• 圖解最大公因數求法 （頁面存檔備份，存於互聯網檔案館）
• 包含GCD動態規劃 （頁面存檔備份，存於互聯網檔案館）

參見

• 公倍數
• 公因數
• 最小公倍數