輾轉相除法最大公因數計算機

輸入計算

數值 1

數值 2

結果

https://example.com

最大公因數

4

最大公因數（GCF，又稱 GCD）

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

什麼是輾轉相除法？

最大公因數（GCF，英文也稱 greatest common divisor，簡寫為 GCD）指的是能同時整除兩個整數的最大正整數。輾轉相除法（又稱歐幾里得演算法）是一種歷史悠久卻極為高效的求法，透過反覆「帶餘數除法」逐步逼近答案。本計算機可求出任意兩個整數的最大公因數，並完整列出每一步除法，讓你清楚看懂整個運算過程。

歐幾里得演算法用盡可能大的相等正方形鋪滿矩形——該正方形的邊長就是最大公因數。

使用方法

在數值 1 和 數值 2 中各輸入一個整數。計算機會以較大的數當作被除數、較小的數當作除數，反覆相除直到餘數為 0。最後一個不為 0 的除數，就是兩數的最大公因數。輸入順序不影響結果，正負號也會被忽略，因為最大公因數只與數值大小有關。

公式解析

每一步都會算出商和餘數：\(a = c \times b + R\)，其中 \(c = \lfloor a / b \rfloor\)（商取整數部分），\(R = a \bmod b\)（餘數）。接著把 \(a\) 換成 \(b\)、把 \(b\) 換成 \(R\)，再重複同樣的步驟。由於每次的餘數一定比前一個除數小，這個過程必然會結束。當 \(R = 0\) 時，當下的除數就是答案。寫成遞迴形式即為：

$$\gcd\!\left(a,\ b\right) = \gcd\!\left(b,\ a \bmod b\right),\quad \gcd(a, 0) = a$$

Advertisement

實際範例

求 GCF(816, 2260)。設 a = 2260、b = 816。

$$2260 = 2 \times 816 + 628$$$$816 = 1 \times 628 + 188$$$$628 = 3 \times 188 + 64$$$$188 = 2 \times 64 + 60$$$$64 = 1 \times 60 + 4$$$$60 = 15 \times 4 + 0$$

當除數為 4 時餘數歸零，因此 GCF(816, 2260) = 4。

每一步用 (b, a mod b) 取代 (a, b)，直到餘數為 0；最後一個非零除數即為最大公因數。

常見問題

GCF 和 GCD 是同一回事嗎？是的。「最大公因數（greatest common factor）」與「最大公約數（greatest common divisor）」是同義詞，本工具兩者通用。

如果有一個輸入是 0 怎麼辦？\(\gcd(a, 0) = a\)，因為任何數都能整除 0。但若兩個數都是 0，則最大公因數沒有定義。

可以求三個數的最大公因數嗎？可以，兩兩配對計算即可：\(\gcd(x, y, z) = \gcd(\gcd(x, y), z)\)。