为什么方程 ax+by=1 可以作为整数 a 和 b 互质的证书？

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

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

最大公约数 $\gcd(a,b)$ 是能同时整除 $a$ 和 $b$ 的最大正整数。等价地，正整数 $c$ 是最大公约数，如果它同时整除 $a$ 和 $b$，并且 $a$ 和 $b$ 的任何其他正公因数也都整除 $c$。

适用条件：整数 $a$ 和 $b$ 不同时为零。；$c$ 是同时整除 $a$ 和 $b$ 的正整数。

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

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

是的，在这种语境下，“最大公约数”（greatest common factor）被用来指代许多现代文本中更常称为“最大公因数”（greatest common divisor）的概念。所示的数学过程是相同的基于减法的欧几里得算法。

适用条件：在解释算法为何有效时非正式地使用。

要通过列出因数来求最大公约数，需列出第一个数字的所有正因数，列出第二个数字的所有正因数，识别出现在两个列表中的因数，并从公因数中选择最大的数字。

适用条件：输入是正整数。；列出因数对于小例子是实用的；并未断言这是最快的方法。