Home GCD及其证明
Post
Cancel

GCD及其证明

「欧几里得算法」应该是刚入门算法就要学会的·了·吧… 奈何我一直拖到现在还没有为它写过一篇博客. 今天顺手将它补上.

最大公约数即为 Greatest Common Divisor, 常缩写为 gcd.

$\pm 1$ 是任意一组整数的公约数.

代码模板

1
2
3
4
5
6
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

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

甚至还有这种高调的写法:

1
2
3
4
inline int gcd(int a,int b) {
    while(b^=a^=b^=a%=b);
    return a;
}

具体可以参考这篇博客, 归纳得很全.

欧几里得算法证明

我自己的证法嗷.

欧几里得算法就是一个著名的等式: gcd(a, b) = gcd(b, a mod b).

对于两个数 a 和 b, 我们假设 a > b, 那么 a 就可以表示成 a = kb + r. 其中, k = a / b, r = a mod b.

c = gcd(a, b), 那么 a = mc, b = nc, 且 (m, n) = 1.

于是 mc = knc + r, 即 r = (m - kn)c.

由于 c = gcd(a, b), 因此我们其实只需要证明 c = gcd(b, r), 即证 (n, m - kn) = 1.

这个很好证! 用裴蜀定理进行一番奇妙的变换:

因为 (m, n) = 1, 因此不定方程 mx + ny =1 一定有一组整数解.

于是, 1 = mx + ny = ny + (m - kn)x + knx = (kx + y)n + x(m - kn).

于是乎, 不定方程 (kx + y)n + x(m - kn) = 1 有一组整数解 u = kx+y, v = x.

因此 (n, m - kn) = 1.

证毕.

P.S. 回想起高中时的自己是一名很菜的数竞生的事实… (是数竞生啊 为什么不是艺术生呢) 但是如今已经转码的我仍然对数学怀有一种热爱… 泪目 T^T…

扩展 GCD

抽时间再更…

This post is licensed under CC BY 4.0 by the author.