欧几里得算法与扩展欧几里得算法

欧几里得算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。

基本算法:设a=qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。

证明

第一种证明:
a可以表示成a = kb + r,则r = a mod b

  假设d是a,b的一个公约数,则有

  d|a, d|b,而r = a - kb,因此d|r

  因此d是(b,a mod b)的公约数

  假设d 是(b,a mod b)的公约数,则

  d | b , d |r ,但是a = kb +r

  因此d也是(a,b)的公约数

  因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

第二种证明:

要证欧几里德算法成立,即证: gcd(a,b)=gcd(b,r),其中 gcd是取最大公约数的意思,r=a mod b

下面证 gcd(a,b)=gcd(b,r)
设 c是a,b的最大公约数,即c=gcd(a,b),则有 a=mc,b=nc,其中m,n为正整数,且m,n互为质数
由 r= a mod b可知,r= a- qb 其中,q是正整数,
则 r=a-qb=mc-qnc=(m-qn)c
b=nc,r=(m-qn)c,且n,(m-qn)互质(假设n,m-qn不互质,则n=xd, m-qn=yd 其中x,y,d都是正整数,且d>1
则a=mc=(qx+y)dc, b=xdc,这时a,b 的最大公约数变成dc,与前提矛盾,
所以n ,m-qn一定互质)
则gcd(b,r)=c=gcd(a,b)
得证。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
int gcd(int i,int j){//定义求最大公因数的函数,有两个参数i,j是要求最大公因数的两个数
while(j!=0)
{
int r=j; //定义r为中间变量,用于交换i,j的值
j=i%j; //求i,j的余数
i=r;
} //根据欧几里得算法,gcd(i,j)=gcd(j,i%j),在j!=0的条件下循环计算
return i;
}
int main(){
int i,j;
printf("input i,j:");
scanf("%d %d",&i,&j);
printf("gcd of i,j is:%d",gcd(i,j));
return 0;
}

递归:

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

扩展欧几里得算法

基本算法:对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。

证明

证明:设 a>b。

  1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;

  2,ab!=0 时

  设 ax1+by1=gcd(a,b);

  bx2+(a mod b)y2=gcd(b,a mod b);

  根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);

  则:ax1+by1=bx2+(a mod b)y2;

  即:ax1+by1=bx2+(a-(a/b)b)y2=ay2+bx2-(a/b)by2;

  根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;

这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.

  上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。

当 b=0 时存在 x , y 为最后一组解
,而每一组的解可根据后一组得到。所以第一组的解 x , y 必然存在

算法实现

根据上面的证明,在实现的时候采用递归做法

  先递归进入下一层,等到到达最后一层即 b=0 时就返回x=1 , y=0

  再根据 x=y’ , y=x’-a/b/y’ ( x’ 与 y’ 为下一层的 x 与 y ) 得到当层的解

  不断算出当层的解并返回,最终返回至第一层,得到原解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int exgcd(int m,int n,int &x,int &y)//扩展欧几里得算法

{
int x1,y1,x0,y0;
x0=1; y0=0;
x1=0; y1=1;
x=0; y=1; //初始化x0,y0,x1,y1
int r=m%n; //令r=i mod j
int q=(m-r)/n;
while(r)
{
x=x0-q*x1; y=y0-q*y1;
x0=x1; y0=y1;
x1=x; y1=y; //x0=y1,y0=x1-(m/n)y1
m=n; n=r; r=m%n;
q=(m-r)/n;
}
return n;
}

递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}

应用:

(1)求解不定方程;

(2)求解模线性方程(线性同余方程);

(3)求解模的逆元;

求解逆元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
int exgcd(int m,int n,int &x,int &y)//扩展欧几里得算法
{
int x1,y1,x0,y0;
x0=1; y0=0;
x1=0; y1=1;
x=0; y=1; //初始化x0,y0,x1,y1
int r=m%n; //令r=i mod j
int q=(m-r)/n;
while(r)
{
x=x0-q*x1; y=y0-q*y1;
x0=x1; y0=y1;
x1=x; y1=y; //x0=y1,y0=x1-(m/n)y1
m=n; n=r; r=m%n;
q=(m-r)/n;
} //可以求出x,y的值
return n;
}

int mod_reverse(int a,int n)//ax=1(mod n) 求a的逆元x
{
int d,x,y;
d=exgcd(a,n,x,y); //调用扩展欧几里得算法求最大公因数
if(d==1) //如果做大公因数是1,gcd(a,n)=1则存在逆元
return (x%n+n)%n; //求a的逆相当于求解ax=1(mod n),这个方程可以转化为ax-my=1,
//然后套用二元一次方程的方法,用扩展欧几里得算法求得一组x0,y0和gcd
else
return -1;
}

int main(){
int i,j;
printf("input a,n(ax=1(mod n)):") ;
scanf("%d%d",&i,&j);
printf("mod_reverse a is:%d",mod_reverse(i,j));
return 0;
}
求解不定方程

exgcd 解不定方程(使用不将a与b转为互质的方法)

  对于 ax+by=c 的不定方程,设 r=gcd(a,b)

  当 c%r!=0 时无整数解

  当 c%r=0 时,将方程右边 *r/c 后转换为 ax+by=r 的形式

  可以根据扩展欧几里得算法求得一组整数解 x0 , y0

  而这只是转换后的方程的解,原方程的一组解应再 *c/r 转变回去

  (如 2x+4y=4 转换为 2x+4y=2 后应再将解得的 x , y 乘上2)

  则原方程解为 x1=x0c/r , y1=x0c/r

  通解 x=x1+b/rt , y=y1-a/rt ,其中 t 为整数

  证明:

    将 x , y 带入方程得

    ax+ab/rt+by-ab/rt=c

    ax+by=c

    此等式恒成立

    得证

  这里 b/r 与 a/r 为最小的系数,所以求得的解是最多最全面的

  证明:

    为了推出证明中的 ax+by=c ,且想达到更小的系数,只能将 b/r 与 a/r 同除以一个数 s

    而 b/r 与 a/r 互质,且 s 为整数,则 s=1 ,不影响通解

    那么 b/r 与 a/r 就为最小的系数

    得证

1
2
3
4
5
6
7
8
9
bool linear_equation(int a,int b,int c,int &x,int &y)
{
int d=exgcd(a,b,x,y);
if(c%d)
return false;
int k=c/d;
x*=k; y*=k; //求得的只是其中一组解
return true;
}
-------------本文结束感谢您的阅读-------------
/*
*/