最大公约数｜Chirag Lecture Tutorials

10 和 15 的最大公约数是 5。这是通过列出这两个数的所有公共正约数（即 1 和 5），并选择其中最大的一个来确定的。

适用条件：输入是正整数 10 和 15。；使用的方法是列出所有公共正约数。

欧几里得算法通过反复应用步骤 $\gcd(a,b)=\gcd(b,a\bmod b)$ 来保持最大公约数不变，其中 $a$ 为非负整数，$b$ 为正整数。它将数字对替换为除数和余数，从而保留了最大公约数。

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

欧几里得算法会终止，因为在每一步中，余数都严格小于前一个除数。由于第二个参数是一个非负整数，并且在每一步中都在减小，它最终必须达到零。

适用条件：算法在非负整数上运行。；每一步将数字对 $(a,b)$ 替换为 $(b, a\bmod b)$。；当 $b > 0$ 时，余数 $a\bmod b$ 严格小于 $b$。

欧几里得算法的基本情况是当数字对的第二个参数为零时。此时，算法停止，并返回第一个参数作为最大公约数。

适用条件：算法正在使用 $\gcd(a,b)=\gcd(b,a\bmod b)$ 替换数字对。；第二个参数 $b$ 已经达到零。

在欧几里得步骤 $\gcd(a,b)=\gcd(b,a\bmod b)$ 中，余数 $a\bmod b$ 成为数字对的新第二个参数。它在下一次迭代中替换了原始的被除数 $a$。

适用条件：$a$ 是非负整数。；$b$ 是正整数。；运算是欧几里得步骤 $\gcd(a,b)=\gcd(b,a\bmod b)$。

当数字对的第二个参数变为零时，你应该停止欧几里得算法。此时，第一个参数就是最大公约数。

适用条件：算法正在追踪欧几里得算法的步骤。；数字对表示为 $(a,b)$。；运算是 $\gcd(a,b)=\gcd(b,a\bmod b)$。

要追踪 $\gcd(10,15)$ 的欧几里得算法，需反复应用步骤 $\gcd(a,b)=\gcd(b,a\bmod b)$，直到第二个参数为零。序列为 $\gcd(10,15)=\gcd(15,10)=\gcd(10,5)=\gcd(5,0)=5$。

适用条件：初始数字对是 (10, 15)。；算法使用欧几里得步骤 $\gcd(a,b)=\gcd(b,a\bmod b)$。；当第二个参数为零时，过程停止。