欧几里得算法｜Proof of Concept

对于非负整数 $n$，$n$ 和 $0$ 的最大公约数是 $n$ 本身。这作为欧几里得算法的基本情况，当第二个参数变为零时终止递归。

适用条件：$n$ 是非负整数。；数字对是 $(n, 0)$。

使用除法的欧几里得算法在当前数字对 $(a,b)$ 中的一个条目变为零时终止。具体来说，当步骤 $b=aq+r$ 中的余数 $r$ 变为零时，下一对是 $(0,a)$ 或 $(a,0)$，算法停止，返回非零条目作为最大公约数。

适用条件：算法使用步骤 $\gcd(a,b) = \gcd(b, a \bmod b)$。；$a$ 和 $b$ 是非负整数。；当第二个参数为 0 时终止。

重复减法操作在保持公约数不变的同时减小了所涉及数字的大小。由于数字是正整数，它们不能无限减小。

适用条件：初始数字是正整数。；操作是从较大的数字中减去较小的数字。；目标是在减小数字的同时保持最大公约数不变。

从较大的正整数中减去较小的正整数能保持它们的公约数不变，因为一个整数整除 $a$ 和 $b$ 当且仅当它整除 $a$ 和 $b-a$。因此，公约数的集合，进而最大公约数（gcd），保持不变。

适用条件：$a$ 和 $b$ 是正整数。；$b > a$（所以我们从 $b$ 中减去 $a$）。

欧几里得算法通过将较大的数字替换为两个数字相除的余数来减小问题规模。由于余数 $r$ 满足 $0 \le r < a$（其中 $a$ 是除数），新数字严格小于之前的较大数字，从而确保向基本情况推进。

适用条件：当前数字对是 $(a,b)$，其中 $b \ge a > 0$。；步骤计算 $b = aq + r$，其中 $0 \le r < a$。；新的数字对是 $(r,a)$ 或 $(a,r)$，取决于实现，但有效地最大值减小了。

不变性质是两个数 $a$ 和 $b$ 的公约数集合与 $a$ 和 $b-a$（或 $b$ 和 $a \bmod b$）的公约数集合完全相同。这确保了最大公约数（gcd）在算法的步骤中保持不变。

适用条件：$a$ 和 $b$ 是整数。；操作是减法（$b-a$）或取模（$a \bmod b$）。

根据带余除法的定义，对于任意整数 $a$ 和 $b$（$b>0$），存在唯一的整数 $q$ 和 $r$，使得 $a = bq + r$ 且 $0 \le r < b$。这个对 $r$ 的约束确保余数始终严格小于除数 $b$，这对于算法的终止至关重要。

适用条件：$b$ 是正整数。；$a$ 是非负整数。；运算是 $a \bmod b$。

用除法代替多次减法通过直接使用余数来简化算法。对于 $b=aq+r$ 且 $0 \le r < a$，数字对 $(a,b)$ 被替换为 $(r,a)$。

适用条件：$a$ 和 $b$ 是非负整数。；$b = aq + r$，其中 $0 \le r < a$。；算法通过将数字对 $(a,b)$ 替换为 $(r,a)$ 继续进行。