欧几里得算法

欧几里得算法

描述

\[\gcd(a, b) = \gcd(b, a \bmod b) \]

证明

求证:

\[\gcd(a, b) = \gcd(b, a \bmod b) \]

假设 \(a > b\) 且 \(b \nmid a\),可描述:

\[a = bk + c \]

其中 \(k\) 为商,\(c\) 为余数。

假设 \(\gcd(a, b) = u\)
\(a = xu, b = yu\),显然 \(x\) 与 \(y\) 互素。

\[c = a - bk = xu - yuk = (x - yk)u \]

由于 \(x, y, k\) 都是整数,可得 \(c \mid u\) 即 \(b\),\(c\) 存在公因子 \(u\)。

由于 \(\gcd(a, b) = u\) 且现在已知 \(b = yu, c = (x - yk)u\);
所以若 \(y \bot (x - yk)\),则存在 \(\gcd(b, a \bmod b) = \gcd(a, b)\)。

先假设 \(y\) 与 \(x - yk\) 有一个公因子 \(q\),且 \(q \neq 1\);
可描述

\[y = qm, x - yk = qn \]

\[x = qn + yk = qn + qmk = (n + mk)q \]

与已知条件 \(y \bot (x - yk)\) 矛盾。

故 \(y\) 与 \(x - yk\) 互素。
所以

\[\gcd(a, b) = \gcd(b, a \bmod b) \]

由于 \(a, b, a \bmod b\) 是非增的,所以我们也就得到了最大公约数的一个递归求法。

int gcd(int a, int b)
{
    return (b == 0) ? a : gcd(b, a % b);
}

参考文献

上一篇:Springboot 整合 Mybatis 的完整 Web 案例


下一篇:LG 题解 CF710E Generate a String