「Note」欧几里得算法全家桶

一，欧几里得算法

1. 内容

\(\gcd (a, b) = \gcd (b, a \mod b)\)

2. 证明

先假设 \(a > b\)，\(a = bx+y\)，其中 \(x = \lfloor\frac{a}{b}\rfloor, 0 \le y \lt b\)。
也就是 \(b\) 除以 \(a\) 等于 \(x\) 余 \(y\)。
原命题就是 \(\gcd (a, b) = \gcd (y, b)\)。

由 \(a = bx + y\) 可以得到 \(y = bx - a\)，由于 \(\gcd (a, b)\) 必定是 \(a, b\) 的因数，所以 \(\gcd (a, b)\) 也是 \(y\) 的因数。

按照上面的方法，我们发现 \(\gcd (y, b)\) 是 \(y\) 和 \(b\) 的因数，由 \(a = bx+y\) 得知它也是 \(a\) 的因数。

整理所有信息。

• \(\gcd (a, b)\) 是 \(a, b\) 的最大公因数。
• \(\gcd (y, b)\) 是 \(a, b\) 的公因数。
• \(\gcd (y, b)\) 是 \(y, b\) 的最大公因数。
• \(\gcd (a, b)\) 是 \(y, b\) 的公因数。

因为最大公因数大于等于所有因数，我们知道 \(\gcd (y, b) \le \gcd (a, b)\) 且 \(\gcd (a, b) \le \gcd (y, b)\)。所以两数相等，命题得证。