GCD Calculator

求任意几个数的最大公约数

最大公约数(GCD),也叫最大公因数,是能同时整除所有给定数字、且不留余数的最大整数。输入两个或更多用逗号隔开的数字,计算器就会用辗转相除法立刻算出结果。

定义与例子

• GCD(12, 18) = 6——因为6是同时能整除12和18的最大数字。
• GCD(48, 36, 24) = 12——能同时整除这三个数的最大数字。
• GCD(7, 13) = 1——这两个数互质(除了1以外没有公因数)。

辗转相除法

计算最大公约数最著名的方法是辗转相除法,由欧几里得约在公元前300年的《几何原本》中记载。这个算法的原理是:GCD(a, b) = GCD(b, a mod b),不断重复直到b等于0。举例来说:GCD(48, 36) → GCD(36, 12) → GCD(12, 0) = 12。

化简分数

最大公约数在日常生活中最常见的用途就是把分数化简到最简形式。要化简48/72,先算出GCD(48, 72) = 24,再用24分别去除分子和分母:2/3。这个结果已经彻底化简,因为分子和分母现在互质了。

密码学

保护大部分互联网通信安全的RSA加密算法,其根基就是涉及最大公约数和互质数的数论。RSA密钥生成算法需要选取两个大质数,这两个质数彼此互质,和它们的乘积也互质。

把东西分成相等的组

最大公约数一个很实际的用途,是把不同数量的物品分成尽可能多的、完全相同的组,而且不留剩余。假设你有48个苹果和36个橙子,想用光所有水果、不留剩余地做出完全一样的果篮,能做出的最大篮数就是GCD(48, 36) = 12篮,每篮装4个苹果和3个橙子。同样的道理也适用于把布料或木材裁成等长的若干段、把不同大小房间里的椅子排成相等的行数,或者把一笔预算按最大的相等份额分给各个部门。

工程应用

在机械工程里,两个齿轮齿数的最大公约数决定了同一对齿相遇的频率。如果齿轮A有48个齿,齿轮B有36个齿,GCD(48, 36) = 12,意味着齿轮A每转过12个齿,就会和齿轮B的每12个齿重新啮合一次。

使用方法

在输入框里用逗号隔开输入你的数字——可以是两个,也可以是任意多个。点击计算,整组数字的最大公约数会立刻显示出来,同时给出辗转相除的每一步过程,让你清楚地看到答案是怎么得出来的,而不是一个黑箱结果。只输入一个数字,或者输入的数字除了1以外没有公因数,工具都能妥善处理:后一种情况会直接报告最大公约数为1,说明这些数字互质。

为什么辗转相除法如此高效

在欧几里得的方法出现之前,求最大公约数意味着要列出每个数的所有因数,再挑出它们共有的最大那个——数字小的时候还行得通,数字一大就慢得没法用。辗转相除法则是反复用较大数除以较小数所得的余数替换较大数,让问题的规模迅速缩小。对任何现实大小的两个数,通常不到五十步就能算完,这也是为什么它至今仍是标准教学方法,也是几乎每个计算器、表格函数和编程语言库里计算最大公约数时内置的算法。

推广到两个以上的数字

当你输入三个或更多数字时,计算器并不需要一个全新的算法——它只是反复应用两个数的情形。整个列表的最大公约数,等于前两个数的最大公约数再和第三个数求最大公约数,依此类推:GCD(a, b, c) = GCD(GCD(a, b), c)。这是成立的,因为任何能同时整除a、b、c的数,必然能整除其中任意两个数的最大公约数,所以两两化简的过程不会丢失任何信息。这很好地说明了一个简单的基础模块——两个数的最大公约数——是如何干净利落地扩展到处理任意长的列表的。

互质数,以及最大公约数为1说明了什么

当计算器报告最大公约数是1时,你输入的这些数字被称为互质数,或者说彼此互素,意思是它们没有大于1的公因数,即便每个数字自身可能有很多因数。比如8和15是互质的,尽管8 = 2×2×2,15 = 3×5——它们只是没有共享任何相同的质数因子。互质性在数论和密码学里随处可见,因为许多算法都依赖于选取那些保证不共享隐藏公共结构的数字。

一步步演示一个例子

看一看辗转相除法求GCD(48, 18)的过程。首先,48 = 2×18 + 12,问题变成GCD(18, 12);接着,18 = 1×12 + 6,变成GCD(12, 6);最后,12 = 2×6 + 0,余数归零,最后一个非零余数6就是最大公约数。算法的每一步都能快速缩小涉及的数字规模,这正是为什么即便面对非常大的数字,它也只需要寥寥几步就能算完,而列出所有因数的方法则会随着数字增大而急剧变慢。

私密且即时

所有计算都完全在你的浏览器中使用辗转相除法完成,输入即刻出结果,你输入的任何数字都不会被发送到服务器、记录或分享。页面加载完成后即可离线使用,每次计算在关闭或刷新标签页的瞬间就会被丢弃。