数论-最大公约数和最小公倍数

声明

部分代码源于《数学一本通》by东南大学出版社

定义

就是最大的那个公约数呗
我们来个稍微学术点的定义:
一般地,设$a_1,a_2,…,a_k$是k个非零的整数,如果存在一个非零整数$d$,使得$d|a_1,d|a_2,…,d|a_k$,那么我们就说$d$是$a_1,a_2,…,a_k$的公约数。在公约数的集合里最大的,就是最大公约数
最小公倍数就是一般地,设$a_1,a_2,…,a_k$是k个非零的整数,如果存在一个非零整数$d$,使得$a_1|d,a_2|d,…,a_k|d$,那么我们就说$d$是$a_1,a_2,…,a_k$的公倍数。在公约数的集合里最小的,就是最小公倍数

最大公约数

最大公约数,一般表示为$gcd(…)$,数学上一般表示为$(…)$。这是显然肯定有的,至少是1。当$gcd=1$的时候,就说明这几个数是互质的。(区别于两两互质)。
下面介绍几种计算两个数的$gcd$方法。

欧几里得算法

欧几里得算法就是我们熟悉的辗转相除法(辗转相减法的 改进)。

原理

$gcd(x,y)=gcd(y-x)$

证明可以用同余定理来完成。

代码实现 (一行$gcd$)

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

二进制算法

这是对欧几里得的改进。
原理就是不断除去因子2来降低常数。
若$x=y$则$gcd(x,y)=x$,否则:

  1. 若$x,y$均为偶数,则$gcd(x,y)=2*gcd(x/2,y/2)$;
  2. 若$x$为奇数,$y$为偶数,则$gcd(x,y)=gcd(x,y/2)$;
  3. 若$y$为奇数,$x$为偶数,则$gcd(x,y)=gcd(x/2,y)$;
  4. 若$x,y$均为奇数,则$gcd(x,y)=gcd(x-y,y)$;

二进制算法代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline int gcd(int x,int y)
{
int i,j;
if(x==0)return y;
if(y==0)return x;
for(i=0;0==(x&1);++i)x>>=1;
for(j=0;0==(y&1);++j)y>>=1;
if(j<i)i=j;
while(1)
{
if(x<y)x^=y,y^=x,x^=y;
if(0==(x-=y))return y<<i;
while(0==(x&1))x>>=1;
}
}

最小公倍数

这个没什么好说的,一般表示为$lcm(…)$数学上表示为$[…]$
有一个定理需要说一下$$gcd(a,b) \times lcm(a,b)=a\times b$$

gcd的一些性质

基本变化规律

  1. $gcd(\pm a,\pm b)=gcd(a,b)$;
  2. $gcd(a,b)=gcd(b,a)$;
  3. 对于任意整数$x$有$gcd(a,b+ax)=gcd(a,b)$;

裴蜀等式

设$a$,$b$是不全为0的整数,则存在整数$x$,$y$使得$$ax+by=gcd(a,b)$$特别地,若$x=x_0,y=y_0$是满足上面的裴蜀等式的一对整数,则等式$$a(x_0+bu)+b(y_0-au)=gcd(a,b) (u是任意整数)$$
表明,满足上式的$x$,$y$有无数多组;并且,$ab>0$时,可选择$x$为正(负)数,此时$y$则相应的负(正)数。
我们称为等式(1)

裴蜀等式的推论

推论1

由等式(1)可以推出:
证明两个整数$a,b$互质的充分必要条件是存在整数$x,y$使得$$ax+by=1$$
证明
事实上,条件的必要性是等式(1)的特例。反过来,若有$x,y$使得等式成立,设$gcd(a,b)=d$,则$d|a$且$d|b$,所以$d|ax$及$d|by$,于是$d|(ax+by)$,所以$d|1$,所以$gcd(a,b)=1$。互质。

推论2

若$m|a,m|b$则$m|gcd(a,b)$,也就是说,$a$和$b$的公约数,是它们最大公约数的约数。

推论3

若$m>0$,则$gcd(ma,mb)=m\times gcd(a,b)$

推论4

若$gcd(a,b)=d$,则$gcd(\frac ad,\frac bd)=1$。因此,由两个不互质的整数,可以自然地产生一对互质的整数。

推论5

若$gcd(a,m)=1,gcd(b,m)=1$,则有$gcd(ab,m)=1$.这表示,与一个固定整数互质的整数之集关于乘法封闭。
由此可以推出:
若$a,b$互质,则对任意的$k>0$都有$gcd(a^k,b)=1$进而对任意的$l>0$都有$gcd(a^k,b^l)=1$。

推论6

设$b|ac$若$gcd(b,c)=1$,则$b|a$。

推论7

设正整数$a,b$之积是一个整数的$k$次幂$(2\leq k)$。若$a,b$互质,则$a,b$都是整数的$k$次幂。
这里两元的定理还可以扩展到多元。

lcm的一些性质

性质1

$a,b$的任何一个公倍数都是$lcm(a,b)$的倍数。

性质2

上面已经提到过了$$gcd(a,b)\times lcm(a,b)=|a\times b|$$但是对于多元的情况下,这个等式并不一定成立。但是我们有性质3:

性质3

若$a,b,c,…,d$两两互质,则有$$lcm(a,b,c,…,d)=|abc…d|$$

文章目录
  1. 1. 声明
  2. 2. 定义
  3. 3. 最大公约数
  4. 4. 欧几里得算法
    1. 4.1. 原理
    2. 4.2. 代码实现 (一行$gcd$)
    3. 4.3. 二进制算法
    4. 4.4. 二进制算法代码实现
  5. 5. 最小公倍数
  6. 6. gcd的一些性质
    1. 6.1. 基本变化规律
    2. 6.2. 裴蜀等式
    3. 6.3. 裴蜀等式的推论
      1. 6.3.1. 推论1
      2. 6.3.2. 推论2
      3. 6.3.3. 推论3
      4. 6.3.4. 推论4
      5. 6.3.5. 推论5
      6. 6.3.6. 推论6
      7. 6.3.7. 推论7
  7. 7. lcm的一些性质
    1. 7.1. 性质1
    2. 7.2. 性质2
    3. 7.3. 性质3