最大公约数

两个整数的最大公约数（greatest common divisor）是同时整除两数的正整数中最大的一个，记作 $gcd(a,b)$。若 $a,b$ 不同时为零，它总存在；例如 84 与 30 的公约数有 1、2、3、6，故 $gcd(84,30)=6$。负号不改变约数，所以 $gcd(-84,30)=6$。

余数为什么不改变公约数

若 $a=qb+r$，那么一个整数 $d$ 同时整除 $a,b$，当且仅当它同时整除 $b,r$：从 $a,b$ 可得 $r=a-qb$；从 $b,r$ 可得 $a=qb+r$。两对数的公约数集合相同，于是 $$gcd(a,b)=gcd(b,r).$$ 这正是欧几里得算法的关键一步，而不只是计算口诀。

对 84 与 30，连续相除得到 $84=2\cdot 30+24$，$30=1\cdot 24+6$，$24=4\cdot 6+0$。最后一个非零余数 6 就是最大公约数。每一步的正余数都严格小于前一个除数，故算法不会无限循环。

互素与零的边界

当 $gcd(a,b)=1$ 时称两数互素，并不要求各自都是素数：8 与 15 都合数，却互素。约定 $gcd(a,0)=|a|$（$a\ne 0$），因为 0 可被每个非零整数整除；$gcd(0,0)$ 没有最大正公约数，通常不定义。贝祖等式把算法所得的最大公约数进一步表示为原两数的整数线性组合。

参考资料

• MIT，Mathematics for Computer Science，Number Theory 章节。
• MIT 18.781，初等数论讲义。
• 继续阅读：整数整除、贝祖等式、最小公倍数。