最大公约数与扩展欧几里得算法[数论]

时间:2023-01-09 09:46:10

——!x^n+y^n=z^n  

  最大公约数(gcd)及其算法(欧几里得算法)

对于正整数 a,b 若存在c使得c|a且c|b,则称c为a,b的公约数,若c还满足a=pc,b=qc,且p,q互质,则称c为a,b的最大公约数,记为(a,b)。

当然我们可以用枚举的方法求gcd,但还有一种算法可以高效解决这一问题,叫做欧几里得算法...这里主要给出一种证明...

欧几里得算法:(a,b)=(a,b%a)[不妨设a<=b]

``````

证明:

设(a,b)=c;

则a=pc,b=qc,且(p,q)=1;

由带余除法可知,b=am+r,0=<r<a;

∵a=pc,b=qc

∴r=c(q-mp)

这表明c是r的约数,故c|(a,b%a);

若c≠(a,b%a) 记c'=(a,b%a),c'>c;

即r=c(q-mp)=b-am=c'r'

   a=c'a'

=>b=c'r'+c'a'm 这表明c'|a,c'|b,然而c'>c 这与c是(a,b)矛盾

固原命题得证。

``````

身为lowbee的我乱写一通代码:

int gcd(int a,int b){

if(b==0) return a;

return gcd(b,a%b);

}

  裴蜀定理与扩展欧几里得:

裴蜀定理:ax+by=c   <=>   (a,b)|c  <=>   ax+by=(a,b)有解

特别地,ax+by=1   <=>   (a,b)=1 (其实证明这个就能得到一般的裴蜀定理)

``````

简单说明一下,记住就好把,别太纠结:

若(a,b)=1,则b不整除 a,2a,L,(b-1)a;(这个操作比较显然...)···①

下证上面的式子除以b两两不同:

若存在ka≡ ma(mod b),那么b|a(k-m)[不妨设k>m,且k,m∈[1,(b-1)]∩N]

这与①产生矛盾,故命题成立。

故一定存在0<k<b使得 ka≡1(mod b),即存在 ax+by=1。

``````

那么问题来了,怎么求解x,y?

若x=x0,y=y0是方程的一组解,且(a,b)=1,我们容易得到她的所有解:

a(x0+tb)+b(y0-ta)=1 (t∈Z)。

所以我们只要求得一组解就行了。当然这个问题不好想,如果a|b,那就十分显然了

a*1+b*0=a(gcd(a,b))[特殊情况的话a=1],这时候能想到什么?

欧几里得算法!

我们先假设  ax0+by0=1(a>b),我们考虑b,a%b的情况,由裴蜀定理我们易知:

存在 bx1+(a%b)y1=1=ax0+by0成立,如果我们在运用编程的特性,我们可以知道:

a%b=a-[a/b]*b,这意味着我们可以对上式进行变形(这种操作就自己画画把…)

得到:

x0=y1;y0=x1-[a/b]y1;

这不就是很好的递归操作吗?其实这就是上面这个操作就是扩展欧几里得算法。

接下来是蒟蒻的渣代码:

int x,y;
void egcd(int a,int b){
if(b==0){
x
=1;
y
=0;
return ;
}
int p,q;
egcd(b,a
%b);
p
=y;
q
=x-(a/b)*y;
x
=p;
y
=q;
return ;
}

可以去做同余方程加深理解(luogu的...):https://www.luogu.org/problem/show?pid=1082#sub

2017-07-21