最大公因數

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

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

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

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

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

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

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

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

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

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

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

## 概述

### 例子

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

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

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

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

同樣地，24可以表示為：

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

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

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

$$1, 2, 3, 6$$

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

$$\gcd(54,24) = 6$$

### 互質數

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

### 幾何角度的說明

<image>

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

## 計算

### 質因數分解法

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

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

$$48 = 2 \times 2 \times 2 \times 2 \times 3$$

$$180= 2 \times 2 \times 3 \times 3 \times 5$$

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

<image>

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

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

### 輾轉相除法

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

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

$$\gcd(a, 0) = a$$

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

其中

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

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

$\gcd(a,a) = a$,

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

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

<image>

## 性質

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

## 程式代碼

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

### C#

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

### C++

運行時計算實現：

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

編譯時計算實現：

```cpp
#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

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

### Java

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

### JavaScript

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

### Python

```py
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)
```

## 政治用法

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