最大公约数・最小公倍数计算器
输入两个正整数后，用辗转相除法（欧几里得算法）求出最大公约数（GCD），并逐步显示计算过程。同时计算出最小公倍数（LCM）。
| 最大公约数（GCD） | |
|---|---|
| 最小公倍数（LCM） |
辗转相除法的计算过程
| 计算式 |
|---|
| = × + |
什么是辗转相除法（欧几里得算法）
辗转相除法是求两个整数最大公约数的经典算法。其步骤是："关注较大数除以较小数所得的余数，用除数和余数这一组数重复相同的操作，当余数变为0时，此时的除数即为最大公约数"。即使是很大的数，也能通过较少的步骤准确求出最大公约数。这一方法记载于公元前300年左右欧几里得所著的《几何原本》中，被认为是现存最古老的算法之一。
使用提示
- 最小公倍数（LCM）可以用"A×B÷最大公约数（GCD）"这一公式求出。常用于分数通分，或求多个周期不同的日程何时会重合。
- 如果两个数互质（最大公约数为1），那么最小公倍数就直接等于A×B。
- 辗转相除法的一个实用优点是：即使是求较大数字之间的最大公约数，它也比先做质因数分解再求解要快。
- 输入的两个数字的大小顺序不影响结果，程序内部会自动从较大的数开始计算。
常见问题
最大公约数是"能同时整除两个数的整数中最大的一个"，最小公倍数是"两个数的倍数中最小的一个"。例如12和18，最大公约数是6，最小公倍数是36。
通过质因数分解求最大公约数的方法，数字越大质因数分解本身就越耗时；而辗转相除法只需反复进行除法和求余运算，因此即使是位数很大的整数，也能快速求出最大公约数。
本工具仅支持正整数。如果输入0、负数或小数，将不会显示计算结果。
本工具支持两个数字的计算。如果是3个及以上，可以两两依次计算（例如先求A和B的最大公约数，再求该结果与C的最大公约数）来得到同样的结果。
闲话 ― 为什么一个2000多年前的算法至今仍在使用
辗转相除法记载于公元前300年左右古希腊数学家欧几里得所著的数学著作《几何原本》（Elements）第七卷中。它被认为是现存记录中最古老的算法之一，即便过去了2000多年，如今依然是计算机科学教材中最先介绍的代表性算法之一。
这一算法之所以能沿用至今，关键在于其计算效率之高。数学上已证明，辗转相除法所需的步数大致与输入数字的位数成正比（最坏情况出现在与斐波那契数列相关的数字组合中），因此无论数字多大，都能在现实可行的时间内求出最大公约数。
现代密码技术（如RSA加密）在密钥生成过程中，仍然会用到最大公约数的计算（或其扩展版本——扩展欧几里得算法）。古代的数学发现如今支撑着互联网安全的基础技术之一，这一事实生动地展示了数学的普适性。