扩展欧几里得学习笔记

最近写题的时候经常遇到一些数论题,似乎是扩欧又似乎不是,为了加深自己的印象并且整理一下以前模糊的思路,就写下这篇笔记。

感谢巨巨的博客:https://www.cnblogs.com/KatouKatou/p/9818175.html

同时其中部分证明参考了柯召 孙琦编著的《数论讲义》第二版。

欧几里得算法

在讨论扩展欧几里得算法前先厘清一下欧几里得算法,也就是我们常说的辗转相除法。熟练掌握的人可以跳过,不过如果不知道如何证明的话可以看一下证明过程,说不定会有某种程度上的启发。

用途

辗转相除法的应用范围很单一,就是用来求两个整数的最大公因数的。

过程

假设我们要求的是a和b的最大公因数,设a=b*q1+r1,如果r1!=0,那么我们使a=b,b=r1,那么新的a和b必然也有类似的关系a=b*q2+r2,重复这个操作直到这个算式中的r(a/b的余数)等于0时,那个式子中的b就是原始的a,b两数的最大公因数。配合代码理解一下。

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

 

证明

  在看过程中可能会有一个疑问:为什么我们可以这样子不断变换a,b的值?这就需要先证明一个先导定理:设a,b,c是三个不全为0的整数,且a=b*q+c ①,其中q是整数,则a与b的最大公因数等于b与c的最大公因数。

为了方便表述,我在这里引用一个符号(a,b)来表示a和b的最大公因数。

证:

    因为(a,b)整除与a,也整除于b,所以由①式我们可以得到(a,b)也整除于c(这里就不证明了),因而(a,b)<=(b,c)(因为(a,b)同时是b和c的约数,也就是说它是b和c的公约数,那么它必然小于等于b和c的最大公约数)。用同样的方法我们可以得到(a,b)>=(b,c),于是我们就可以得到(a,b)=(b,c)的结论,证毕。

 

  然后我们来证明辗转相除法,其实在证明之前还有一个我们常常默认为正确的定理需要证明(设a,b为两个整数且b>0,则存在两个唯一整数q,r使得 a=b*q+r,0<=r<b),不过一直在这种地方喋喋不休也很烦吧,我就略过不证了,有兴趣的朋友可以自己推导一下,并没有什么难度。

  其实这回的证明只要在原来的推导过程中加入一个范围就行。

  首先我们有a=b*q1+r1,0<r1<b。(r1如果等于0也就是a被b整除,那就没有证明的必要了,所以为了使证明更清晰我们假设前几式的余数均不为0)

  然后有b=r1*q2+r2,0<r2<r1,

             r1=r2*q3+r3,0<r3<r2

            ......

            rn-2 = rn-1 * qn + rn,0 < rn <rn-1

            rn-1 = rn * qn+1 + rn+1,rn+1= 0

 可以看到余数r的值是不断减少的,那么在有限次的交换后r必定会变成0,我们假设r n+1=0,那么我们就可以得到rn=(0, rn)=(rn,r n-1)=......=(r2,r1)=(r1,b)=(b,a)。证毕。

扩展欧几里得

 证明

  扩展算法的形式就是 对于任给的a>0,b>0,有a*x+b*y=(a,b)。这个结论其实我们用前面证明欧几里得算法的过程就可以得出。

  在前面证明欧几里得算法的时候我们列出了一连串的式子,然后我们把它们变换一下,从倒数第二式开始,我们可以得到rn-2 - rn-1 * qn = rn,

  同理 rn-1= rn-3 - rn-2 * qn-1,合并两式 可以得到 rn = rn-2 * (1+ qn * qn-1)-rn-3 * qn,我们再将rn-2 = rn-4 - rn-3 *qn代入,如此反复,最后就可以得到

  rn =a*x+b*y 即(a,b)=a*x+b*y,其中x,y是两个整数。

  解法

  对于a>0,b>0,有a*x1+b*y1=(a,b),

            同样可得b*x2+(a%b)*y2=(b,a%b)=(a,b)

     所以可以得到a*x1+b*y1=b*x2+(a-[a/b]*b)*y2

                       即a*x1+b*y1=a*y2+b*(x2-[a/b]*y2)

  那么由恒等定理可以得到x1=y2,y1=x2-[a/b]*y2。

 ([a/b]表示小于等于a/b的最大整数)

  至此我们就得到了一个递推式,而由前面欧几里得算法的推导过程我们知道,在推导到边界的时有b=0,return a,即gcd(a,0)=a,那么就有         a*xn+b*yn=a,显然此时xn=1,yn=0。

  到此为止,我们就求出了这个方程的一个特解。

  而在实际的应用过程中,等式的右边不一定为(a,b),而可能为一个任意的整数c,这时该如何求解?

  首先根据我们已经得出的结论,我们可以断言:如果c%(a,b)!=0,那么这个式子是肯定无解的。相对的,假如c%(a,b)=0并且c/(a,b)=t,那么我们只需要在求出的解上乘上一个t就行了。

 

  同时我们对x,y可能也有要求,该如何得到不同的使等式成立的x,y呢。可以想到的是对x,y进行加减操作,同时控制变化量保证等式恒等,显然假如x加上b,y减去a,那么等式是成立的,但这样我们无法保证变化量最小,也就是说我们不能保证这样加减可以得到所有可能的解。而通过观察之后,我们可以想到,x和y分别的最小的变化量应当分别是b/gcd(a,b)和a/gcd(a,b)。如此扩展欧几里得的求解就结束了。

最后附上代码

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

代码的返回值就是a,b的最大公因数

  

原文地址:https://www.cnblogs.com/forever3329/p/11322303.html