最大公约数・最小公倍数计算器
输入两个正整数后，用辗转相除法（欧几里得算法）求出最大公约数（GCD），并逐步显示计算过程。同时计算出最小公倍数（LCM）。
| 最大公约数（GCD） | |
|---|---|
| 最小公倍数（LCM） |
辗转相除法的计算过程
| 计算式 |
|---|
| = × + |
什么是辗转相除法（欧几里得算法）
辗转相除法是求两个整数最大公约数的经典算法。其步骤是："关注较大数除以较小数所得的余数，用除数和余数这一组数重复相同的操作，当余数变为0时，此时的除数即为最大公约数"。即使是很大的数，也能通过较少的步骤准确求出最大公约数。这一方法记载于公元前300年左右欧几里得所著的《几何原本》中，被认为是现存最古老的算法之一。
最大公因数・最小公倍数计算是什么
最大公因数（GCD）是能共同整除两个整数的最大整数，最小公倍数（LCM）则是两个整数的公倍数中最小的整数。本工具只需输入两个正整数，便会以辗转相除法即时算出这两个值，并逐步显示计算过程（被除数、除数、商、余数）。
以手算而言，一般是从质因数分解中寻找共同因数，但数字愈大，质因数分解本身便愈费工夫。本工具采用的辗转相除法只需重复除法即可求得最大公因数，因此位数很大的整数之间也能以相同步骤计算。输入仅限1以上的整数，若输入0、负数或小数则不会显示计算结果。
最大公因数・最小公倍数计算的使用方式
- 输入数值A 输入欲求最大公因数、最小公倍数的第一个正整数。
- 输入数值B 输入另一个正整数。A与B孰大孰小、何者在先皆不影响结果。
- 确认结果 最大公因数（GCD）与最小公倍数（LCM）会自动显示。
- 确认计算过程 辗转相除法的各步骤（被除数＝除数×商＋余数）会以表格显示，可循序追踪至余数为0为止。
用好本工具的小技巧
- 最小公倍数（LCM）可以用"A×B÷最大公约数（GCD）"这一公式求出。常用于分数通分，或求多个周期不同的日程何时会重合。
- 如果两个数互质（最大公约数为1），那么最小公倍数就直接等于A×B。
- 辗转相除法的一个实用优点是：即使是求较大数字之间的最大公约数，它也比先做质因数分解再求解要快。
- 输入的两个数字的大小顺序不影响结果，程序内部会自动从较大的数开始计算。
最大公因数・最小公倍数计算的活用场景
分数约分的事前准备
求出分子与分母的最大公因数后，以该数同除两者即可约分。若想连约分后的结果一并确认，附约分功能的分数计算机相当便利。
计算多个周期重叠的时点
例如每3日与每5日发生的行程，下次落在同一天是3与5的最小公倍数、即15日后。可应用于班表与活动的周期调整。
数学作业・考试准备的验算
可连同计算过程立即验算手算所得的最大公因数、最小公倍数是否正确。
求通分分母的准备
将分母互异的多个分数通分时，各分母的最小公倍数即为新的共同分母。
确认密码技术的基础知识
RSA 加密的金钥产生等，最大公因数的计算也用于现代密码技术的根基，作为理解其原理的第一步，确认计算过程颇有助益。
用语集
- 最大公因数（GCD）
- 指能同时整除两个以上整数的整数（公因数）之中最大者。英文称 Greatest Common Divisor，缩写为 GCD。
- 最小公倍数（LCM）
- 指两个以上整数的共同倍数（公倍数）之中最小者。英文称 Least Common Multiple，缩写为 LCM。
- 辗转相除法
- 指着眼于大数除以小数所得的余数，再以除数与余数之组重复相同操作以求最大公因数的演算法。源自古希腊数学家欧几里得的著作。
- 互质
- 指两个整数的最大公因数为1。互质的两数的最小公倍数，即单纯为该两数相乘之值。
- 质因数分解
- 指将整数分解为质数乘积的形式。最大公因数、最小公倍数也可由共同质因数的组合求得，但数字较大时以辗转相除法较快。
- 公因数・公倍数
- 公因数指多个整数共通的因数，公倍数指多个整数共通的倍数。最大公因数、最小公倍数则分别指其中最大者与最小者。
常见问题
闲话 ― 为什么一个2000多年前的算法至今仍在使用
辗转相除法记载于公元前300年左右古希腊数学家欧几里得所著的数学著作《几何原本》（Elements）第七卷中。它被认为是现存记录中最古老的算法之一，即便过去了2000多年，如今依然是计算机科学教材中最先介绍的代表性算法之一。
这一算法之所以能沿用至今，关键在于其计算效率之高。数学上已证明，辗转相除法所需的步数大致与输入数字的位数成正比（最坏情况出现在与斐波那契数列相关的数字组合中），因此无论数字多大，都能在现实可行的时间内求出最大公约数。
现代密码技术（如RSA加密）在密钥生成过程中，仍然会用到最大公约数的计算（或其扩展版本——扩展欧几里得算法）。古代的数学发现如今支撑着互联网安全的基础技术之一，这一事实生动地展示了数学的普适性。