求证欧几里得算法可计算最大公约数：该证明是否充分？

好的，咱们直接切入核心：证明当$a, b, q, r \in \mathbb{Z}$且$a = bq + r$时，$(a, b)=(b, r)$，完全足以说明欧几里得算法可以用来计算最大公约数。下面我会把这个逻辑拆解清楚：

核心证明思路 #

先证$a,b$的任意公约数都是$b,r$的公约数，反之亦然；如果两个数对的公约数集合完全相同，那它们的最大公约数肯定相等——这是整个推导的关键。

第一步：$a,b$的公约数必是$b,r$的公约数 #

假设整数$n$是$a$和$b$的公约数，也就是 $n \mid a$ 且 $n \mid b$。根据整除的基本性质：若一个整数能整除另外两个整数，那它也能整除这两个整数的任意整数线性组合。

咱们看$r$的表达式：$r = a - bq$，这明显是$a$和$b$的线性组合（系数1和$-q$都是整数），所以：
$$n \mid (a - bq) \implies n \mid r$$
这就说明$n$同时整除$b$和$r$，也就是$n$是$b,r$的公约数。

第二步：$b,r$的公约数必是$a,b$的公约数 #

反过来，假设整数$m$是$b$和$r$的公约数，即 $m \mid b$ 且 $m \mid r$。同样用线性组合的性质，$a = bq + r$是$b$和$r$的线性组合（系数$q$和1都是整数），所以：
$$m \mid (bq + r) \implies m \mid a$$
这说明$m$同时整除$a$和$b$，也就是$m$是$a,b$的公约数。

为什么这能支撑欧几里得算法？ #

既然$(a,b)=(b,r)$，那求$(a,b)$的问题就可以转化为求$(b,r)$的问题。而根据带余除法的规则，余数$r$满足 $0 \leq r < |b|$——说白了，每次迭代我们处理的数对都会越来越小，直到余数$r=0$的时候：

• 当$r=0$时，$(b,0)=|b|$（因为任何整数都能整除0，所以$b$和0的最大公约数就是$b$的绝对值）。
• 这个迭代过程一定会终止，因为余数是严格递减的非负整数，不可能无限循环下去。

这样一步步把大问题拆成小问题，直到得到结果，这就是欧几里得算法的核心逻辑——而我们一开始证明的$(a,b)=(b,r)$，就是这个算法能正确运行的理论基础。

内容的提问来源于stack exchange，提问作者jitender