数论初步:GCD和LCM

GCD

GCD，也就是最大公约数，即两个数拥有的相同的因数集中最大的一个。

求法

如果求任意两个数的GCD呢，相信小学的时候都学过辗转相除法，也就是欧几里得算法，当然还有以前学过的更相减损术，这里只讨论欧几里得算法（据说更相减损术是欧几里得算法的特殊情况）。

欧几里得算法

描述

欧几里得算法的内容是：

两个数的最大公约数是指能同时整除它们的最大正整数。

设两数为$a,b(a\geq b)$，求a和b最大公约数gcd(a,b)的步骤如下：

Ⅰ.用a除以b，$a\geq b$，得$a \div b=q…r_1(0\leq r_1)$。

Ⅱ.若$r_1=0$，则$gcd(a,b)=b$；

Ⅲ.若$r_1\neq 0$，则再用$b\div r_1=q…r1(0\leq r_1)$。

如此往复，直到余数为0，那么gcd(a,b)为除数。

证明

证明欧几里得算法，也就是证明：

Ⅰ.$gcd(a,b)==gcd(b,a\mod b)$.

Ⅱ.所求为最优.

Ⅰ

首先设c为a,b的公因数，则设$a=m\times c,b=n\times c$。

设$a=k\times b+r$，则得到$r=a-k\times b=m\times c-k\times n\times c=(m-k\times n)\times c$。

则c也为b和r的公因数。

再者，设b和r的公因数为v，则设

$b=i\times v$

$r=j\times v$

于是有$a=k\times b+r=k\times i\times v+j\times v=(k\times i+j)\times v$。

则a和b的公约数也为v.

综上我们可以使用这个递推。

Ⅱ

下面我们来推一下:

$a\mod b=r$

$b\mod r=r_1$

$r\mod r_1=r_2$

……

$r_{n-3}\mod r_{n-2}=r_{n-1}$

$r_{n-2}\mod r_{n-1}=r_n$

由于$a\geq b\geq 0$那么$r_1….r_n$是递减的，最终将变为0.

则当$r_{n-1}\neq 0,r_n==0$时，可以得到$r_{n-1}|r_{n-2}$（’|’为整除符号，a|b代表b能被a整除），则$r_{n-2}和r_{n-1}$的公约数只有$r_{n-1}和r_{n-1}的约数$，其中最大的就是$r_{n-1}$。

代码实现

接下来给出代码实现

1
2
3

int gcd(int x, int y){
    return y?gcd(y, x%y):x;
}

LCM

聊完GCD，再来聊聊LCM，也就是最小公倍数,即两个数公共的倍数集合中最小的元素。

求法

对于两个数a,b,有公式:

$a\times b=lcm(a,b)\times gcd(a,b)$。

证明

设$x=gcd(a,b)$；

则$n=a/x,m=b/x$。显然a和m是互素的，所以$lcm(n,m)=n\times m$,又因为$lcm(a,b)=lcm(n\times x,m\times x)=x\times n\times m$。

所以$lcm(a,b)=gcd(a,b)\times a/gcd(a,b)\times b/gcd(a,b)$，即$lcm(a,b)\times gcd(a,b)=a\times b$

代码实现

1
2
3

int lcm(int a, int b){
    return a/gcd(a, b)*b;//先做除法避免溢出
}

参考链接

Ⅰ.欧几里得算法证明

Ⅱ.境外之主