最大公因數與最小公倍數計算器

輸入兩個正整數，計算最大公因數和最小公倍數，並查看歐幾里得演算法的逐步過程。

計算方式

公式

\text{GCD}(a,b) = \text{GCD}(b,\; a \bmod b)

\text{LCM}(a,b) = \frac{a \times b}{\text{GCD}(a,b)}

變數、符號與單位

計算方法說明

計算器先用歐幾里得演算法求最大公因數：反覆計算餘數，直到餘數為 0。然後利用兩數乘積、最大公因數和最小公倍數之間的恆等關係求 LCM。

按歐幾里得遞推，把 $(a,b)$ 替換為 $(b,\; a \bmod b)$ ，直到 $b = 0$ 。剩下的 $a$ 就是 GCD。再由 $a \times b = \text{GCD}(a,b) \times \text{LCM}(a,b)$ 得到 LCM。

什麼是最大公因數？

最大公因數是能同時整除兩個整數的最大正整數，也常寫作 GCD。

什麼是最小公倍數？

最小公倍數是同時為兩個整數倍數的最小正整數，也常寫作 LCM。

歐幾里得演算法怎樣運作？

不斷用較大的數除以較小的數，並把餘數帶入下一步。餘數變成 0 時，最後一個非零餘數就是最大公因數。

GCD 和 LCM 有什麼關係？

對正整數 a 和 b，有 a x b = GCD(a,b) x LCM(a,b)，所以 LCM 可以由兩數乘積除以 GCD 得到。

互質是什麼意思？

如果兩個數的最大公因數為 1，它們就是互質數，表示除了 1 以外沒有共同因數。