欧几里得算法

本文主要是介绍欧几里得算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

欧几里得算法

描述

\[\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);
}

参考文献

• OI WIiki
• CSDN：欧几里得算法原理

这篇关于欧几里得算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！