为什么从较大的正整数中减去较小的正整数能保持它们的公约数不变？

欧几里得算法将旧的除数移到左边（新的被除数），将旧的余数移到较小数的位置（新的除数），以递归地简化问题。这种移位确保随后的每个除法步骤都在更小的数字上进行，同时保持原始数对的最大公约数，直到达到余数为零为止。

适用条件：算法应用于两个正整数。；前一个余数不为零。；过程持续直到获得余数 0。

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

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

要形成下一个除法行，你取前一行的除数，并将其作为新行的被除数。然后，你取前一行的余数，并将其作为新行的除数。

适用条件：你刚刚完成了欧几里得算法中的一个除法步骤。；前一个余数不为 0。

要开始求 $\gcd(10,45)$ 的欧几里得算法，需将较大的数写成较小的数乘以一个未知的商加上一个未知的余数。具体来说，建立除法方程 $45 = 10 \cdot q + r$。

适用条件：输入是正整数。；较大的数放在方程的左边。；商是整数，且余数满足 $0 \le r < 10$。

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

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