最大公约数｜Michael Penn

逆命题陈述道，如果整数 a 和 b 互质（即它们的最大公约数是 1），那么存在整数系数 x 和 y 使得 ax+by=1。这是由贝祖恒等式提供的。

适用条件：a 和 b 是互质的整数。；gcd(a,b) = 1。

证明通过展示 d 是 a 和 b 的线性组合来展示这一点。由于任何公约数都能整除 a 和 b，它也必然能整除它们的任何整数线性组合，包括 d。

适用条件：d 是 a 和 b 的最小正线性组合。；c 是 a 和 b 的公约数。

它可以作为证书，因为如果整数系数 x 和 y 满足 ax+by=1，那么 a 和 b 的任何公约数都必须整除 1。唯一能整除 1 的正整数是 1 本身，这证明了最大公约数是 1。

适用条件：a 和 b 是整数。；存在整数 x 和 y 使得 ax+by=1。

它与最小性矛盾，因为余数可以表示为 a 和 b 的线性组合。如果余数是正的且小于 d，它就属于正线性组合的集合，这违反了 d 是该集合中最小值的定义。

适用条件：d 被定义为 a 和 b 的最小正整数线性组合。；余数 r 是通过将 a 或 b 除以 d 得到的。；r 是正的且 $r < d$。

良序原理通过确保任何非空的正整数集都有一个最小元素来保证这一点。由于正线性组合的集合是非空的，它必然包含一个最小值。

适用条件：整数 a 和 b 不全为零。；集合由形式为 au+bv 的正值组成，其中 u 和 v 是整数。