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

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

数字 A

数字 B

示例

GCD = 6，LCM = 144

最大公约数

最小公倍数

144

欧几里得算法步骤

48 = 2 \times 18 + 12, 18 = 1 \times 12 + 6, 12 = 2 \times 6 + 0

关系：A x B = GCD x LCM

48 \times 18 = 864 = 6 \times 144

GCD 为 6，LCM 为 144。

有帮助吗？

示例

公式

\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。

01什么是最大公约数？

最大公约数是能同时整除两个整数的最大正整数，也常写作 GCD。

02什么是最小公倍数？

最小公倍数是同时为两个整数倍数的最小正整数，也常写作 LCM。

03欧几里得算法怎样工作？

不断用较大的数除以较小的数，并把余数带入下一步。余数变为 0 时，最后一个非零余数就是最大公约数。

04GCD 和 LCM 有什么关系？

对正整数 a 和 b，有 a x b = GCD(a,b) x LCM(a,b)，所以 LCM 可以由两数乘积除以 GCD 得到。

05互质是什么意思？

如果两个数的最大公约数为 1，它们就是互质数，表示除了 1 以外没有共同因数。