欧几里得算法

算法

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

整除的一些引理

\(a \mid b\)，表示 \(b\) 能被 \(a\) 整除。

• 当 \(a\mid b\) 且 \(b\mid a\) 时，\(a=\pm b\)。

• 当 \(k \mid a, k\mid b\) 时，\(d\mid (ax+by)(x,y\in \mathbb Z)\)。

证明：
令 \(k=\gcd(a,b)\)，则有 \(k \mid a,k \mid b\)。

而且我们知道 \(a \mod b = a-b\lfloor{\dfrac{a}{b}}\rfloor\)。

由引理二得知，\(k\mid(a\mod b)\),又因为 $k\mid b $

所以 \(k\mid \gcd(b,a\mod b)\)。

最后得到 \(\gcd(a,b)\mid\gcd(b,a\mod b)\)。

又令 \(d = \gcd(b,a\mod b)\)。

则有 \(d\mid b,d\mid(a\mod b)\)。

得到 \(d\mid(a-b\lfloor{a-\dfrac{a}{b}}\rfloor)\)。

所以 \(\gcd(b,a\mod b)\mid\gcd(a,b)\)，又因为 \(\gcd(a,b)\mid\gcd(b,a\mod b)\)。

由引理一得知\(gcd(a,b)\pm\gcd(b,a\mod b)\)。

所以 \(gcd(a,b)=\gcd(b,a\mod b)\)。