最大公约数与最小公倍数计算器

输入两个正整数，计算最大公约数和最小公倍数，并查看欧几里得算法的分步过程。

计算方式

公式

\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 以外没有共同因数。