最大公约数是什么，能解释一下吗？

本文共计415个文字，预计阅读时间需要2分钟。

最大公约数（gcd）在许多题目中都需要用到，非常实用，但理论很难，请耐心阅读。更相减损术（九章算术）+ 对于所有a，b ∈ N，(a ≥ b) 有 gcd(a, b)=gcd(b, a-b)，即 gcd(a, b)=gcd(a-b, a)

最大公约数\((\gcd)\)

很多题目中都要用到,非常的好用,但是理论很难,请仔细耐心阅读

更相减损术(九章算术）

\(\forall a,b \in \mathbb{N}\),\(a \geqslant b\) 有 $ \gcd(a,b) $= \(\gcd(b,a-b)\) = \(\gcd(a,a-b)\)
\(\forall a,b \in \mathbb{N}\),有 \(\gcd(2a,2b)\) = \(\gcd(a,b)*2\)

证明如下：(a|b表示b可以被a整除)
第一个: 对于\(a\),\(b\)的最大公约数\(d\),因为\(d|a\),\(d|b\),所以\(d|(a-b)\).因此\(d\)也是\(b\),\(b-a\)的公约数.
所以\(a\),\(b\),\(a-b\)的公约数集合相同,于是它们的最大公约数也亦然相等

第二个: 显然,略

得证

欧几里得算法

\(\forall a,b \in \mathbb{N}\),\(b \not = 0\) , \(\gcd(a,b)\) = \(\gcd\) (\(b\),\(a\) \(mod\) \(b\))

证明如下：

若\(a<b\),则\(\gcd(b,a\bmod b)\) = \(\gcd(b,a)\) = \(\gcd(a,b)\), 成立
若\(a \geqslant b\),不妨设\(a\) = \(q*b+r\)其中 $0\leqslant r < b $,显然 \(r=a\bmod b\)对于\(a\),\(b\)的任意公约数\(d\),因为\(d|a\),\(d|(q*b)\),故\(d(a-qb)\),即\(d|r\)因此\(d\)也是\(b\),\(r\)的公约数.所以\(a\),\(b\),\(a\bmod b\)的公约数集合相同,最大公约数也相等

得证

代码实现如下:

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