最大公约数(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;
}