最大公约数(GCD)
又称:GCD、最大公因数、辗转相除法
最大公约数(英文 Greatest Common Divisor,简称 GCD),是能同时整除几个整数的最大正整数。比如 24 和 36,能同时整除它们的数有 1、2、3、4、6、12,其中最大的是 12,所以 gcd(24, 36) = 12。如果两个数的最大公约数是 1,就说它们「互质」,比如 8 和 15。
手算最快的方法是辗转相除法(欧几里得算法)。它基于一个巧妙的性质:a 和 b 的公约数,等于 b 和「a 除以 b 的余数」的公约数。于是就用大数除以小数取余,反复替换,直到余数为 0,最后一个非零的除数就是答案。举例 gcd(24, 36):36 ÷ 24 余 12 → 24 ÷ 12 余 0,除数 12 即为最大公约数。这比「先把两个数都分解质因数再取公共部分」快得多,对很大的数也几步就出结果。
最大公约数在生活中最常见的用途是约分——把分数的分子分母同时除以它们的最大公约数,就得到最简分数,比如 4/8 除以 4 变成 1/2。它还和最小公倍数是一对搭档:两个数的乘积等于「最大公约数 × 最小公倍数」,所以求出 GCD 后,用 a × b ÷ GCD 就能得到最小公倍数。多个数时把结果两两往下滚就行。