ACM数论基础之扩展欧几里德详细证明

扩展的欧几里得算法原理扩展的欧几里得算法（Extended Euclidean algorithm）也称为扩展欧几里得求最大公因数算法，是一种计算两个整数的最大公因数（GCD）以及解决线性不定方程组的方法。

扩展的欧几里得算法的原理是基于欧几里得算法（Euclidean algorithm），欧几里得算法的基本思想是通过逐步取两个数的除数和余数的过程中不断缩小问题的规模，最终将问题的规模缩小到可以直接得出最终的结果。

欧几里得算法利用的是gcd(a, b) = gcd(b, a mod b)的性质。

而扩展的欧几里得算法的原理在于扩展欧几里得定理：对于任意整数a、b，存在整数x、y，使得ax+by=gcd(a,b)。

具体实现过程中，我们可以设a、b为两个需要求GCD的整数，上述定理可以表示为：ax1 + by1 = gcd(a,b)就是说，我们要找到x1、y1与a、b，同时满足上述等式。

接下来就是具体的计算步骤：首先，利用欧几里得算法，求出a、b的最大公因数gcd(a, b)，并记录下每次得到的余数和除数：b = r1q2 + r2...最终，得到一个余数为0的方程，即gcd(a,b) = r(m-1)。

这时，我们就可以根据上述定理来求得x1、y1。

我们可以将上述的余数和除数代入定理中，得到：r(m - 2) = r(m - 4) - r(m - 3)q(m - 2)其中，a1 = (-1)^(m-1)q1这样，我们就可以根据扩展欧几里得定理求得x1、y1了。

例如，我们要求两个数3528和378，它们的最大公因数gcd(3528，378) = 126，那么我们可以利用欧几里得算法求解：3528 = 9 * 378 + 126378 = 3 * 126 + 0可以看到，最终的余数为0，因此gcd(3528，378) = 126。

因此，x1 = -10，y1 = 93。

这样，我们就得到了3528和378的最大公因数为126，同时满足3528 * (-10) + 378 * 93 = 126。

欧几里得&扩展欧几里得算法#朴素的欧几里得算法大家应该知道gcd(a,b)gcd(a,b)gcd(a,b)表示a,b的最大公约数朴素的欧几里得算法其实就是所谓的辗转相除法辗转相除法gcd(a,b)=gcd(b,agcd(a,b)=gcd(b,agcd(a,b)=gcd(b,a modmodmod b)b)b)证明如下：设r=a设r=a设r=a modmodmod bbb =a?ab?b=a-lfloorfrac{a}{b}rfloor*b=a?ba?b,p=gcd(a,b)p=gcd(a ,b)p=gcd(a,b);则a=xp,b=ypa=xp,b=ypa=xp,b=yp代入可得r=xp?xpyp?ypr=xp-lfloorfrac{xp}{yp}rfloor*ypr=xp?ypxp?yp 提公因式得r=p(x?xpyp?y)r=p(x-lfloorfrac{xp}{yp}rfloor*y)r=p(x?ypxp?y) 所以p∣rp|rp∣r即a,b的最大公约数也是r的约数a,b的最大公约数也是r的约数a,b的最大公约数也是r的约数设p‘=gcd(b,r)p`=gcd(b,r)p‘=gcd(b,r)则b=x‘p‘,r=y‘p‘b=x`p`,r=y`p`b=x‘p‘,r=y‘p‘a=r+?ab?ba=r+lfloorfrac{a}{b}rfloor*ba=r+?ba?b代入得a=y‘p‘+?ab?x‘p‘a=y`p`+lfloorfrac{a}{b}rfloor*x`p`a=y‘p ‘+?ba?x‘p‘提公因式a=p‘(y‘+?ab?x‘)a=p`(y`+lfloorfrac{a}{b}rfloor*x`)a=p‘(y ‘+?ba?x‘)所以p‘∣ap`|ap‘∣a得出结论：a,b与b,a mod b的公约数相同，所以最大公约数也相同int gcd(int a,int b)if(!b) return a;else return gcd(b,a%b);扩展欧几里得算法扩展欧几里得算法就是在朴素的欧几里得算法上求一组未知数(x,y)的解，满足贝祖定理:ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b)公式的推导当且仅当ababab①b=0b=0b=0 则x=1,y=0x=1,y=0x=1,y=0②ab0ab0ab0设ax1+by1=gcd(a,b);bx2+(aax1+by1=gcd(a,b);bx2+(aax1+by1=gcd(a ,b);bx2+(a modmodmod b)y2=gcd(b,ab)y2=gcd(b,ab)y2=gcd(b,a modmodmod b)b)b)由朴素欧几里得算法得：gcd(a,b)=gcd(b,agcd(a,b)=gcd(b,agcd(a,b)=gcd(b,a modmodmod b)b)b)所以ax1+by1=bx2+(aax1+by1=bx2+(aax1+by1=bx2+(a modmodmod b)y2b)y2b)y2即ax1+by1=bx2+(a?ab?b)y2ax1+by1=bx2+(a-lfloorfrac{a}{b}rfloor *b)y2ax1+by1=bx2+(a?ba?b)y2化简得：ax1+by1=bx2+ay2?ab?b?y2ax1+by1=bx2+ay2-lfloorfrac{a}{b}rflo or*b*y2ax1+by1=bx2+ay2?ba?b?y2由贝祖等式得x1=y2y1=x2?ab?b.x1=y2 {y1=x2-lfloorfrac{a}{b}rfloor*b} .x1=y2y1=x2?ba?b.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);x=y;y=z-a-b*y;return r;扩展欧几里得应用①解不定方程②解线性同余方程③求模的逆元1.解形如ax+by=c的不定方程用扩展欧几里得算法求出解ax‘+by‘=gcd(a,b)ax`+by`=gcd(a,b)ax‘+by‘=gcd(a,b)再分别乘上cgcd(a,b)frac{c}{gcd(a,b)}gcd(a,b)c?当时无解2.解形如ax≡b(modaxequiv b(modax≡b(mod m)m)m)的线性同余方程即ax?my=bax-my=bax?my=bax+m(?y)=bax+m(-y)=bax+m(?y)=bax+my=bax+my=bax+my=b同上解除即可。

欧⼏⾥得（扩展）算法欧⼏⾥得算法欧⼏⾥得算法⼜称辗转相除法，是指⽤于计算两个⾮负整数a，b的最⼤公约数。

应⽤领域有数学和计算机两个⽅⾯。

计算公式gcd(a,b) = gcd(b,a modb)。

证明记a|d表⽰a可以整除d(d为a的倍数)设d为a和b的公约数，即d|a，d|b。

a modb = a-kb，显然d也为a mod b 的和b的公约数。

设d为a mod b和b的公约数，即d|b，d|(a mod b)则有d|(a-kb)，因为ad−kbd和bd为整数，所以ad必为整数，即d也为a和b的公约数。

综上，(a,b)与(b,a mod b)有相同的公约数，故其最⼤公约数也相等。

C++实现int gcd(int a,int b){return b==0?a:gcd(b,a%b);//其实b⽐a⼤时也是对的}扩展欧⼏⾥得算法扩展欧⼏⾥得算法是欧⼏⾥得算法（⼜叫辗转相除法）的扩展。

除了计算a、b两个整数的最⼤公约数，此算法还能找到整数x、y（其中⼀个很可能是负数）。

通常谈到最⼤公因⼦时, 我们都会提到⼀个⾮常基本的事实: 给予⼆整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。

有两个数a,b，对它们进⾏辗转相除法，可得它们的最⼤公约数——这是众所周知的。

然后，收集辗转相除法中产⽣的式⼦，倒回去，可以得到ax+by=gcd(a,b)的整数解。

证明我们先假设ax+by=gcd(a,b)①存在整数解，令r=a%b，根据假设我们⼜可以得到个式⼦：bx′+ry′=gcd(b,r)=gcd(a,b)存在整数解，将r=a−⌊ab⌋b带⼊并整理得：b(x′−⌊ab⌋y′)+ay′=gcd(a,b)②我们发现①②具有相同的形式，即①式的解可以从②式中获得：x=y′,y=x′−⌊ab⌋y′这就是说只要我们找到②式的解，就能得到①式(上⼀层)的解。

根据相同的形式，从②式的原式我们⼜可以得到rx′′+r′y′′=gcd(r,r′)=gcd(a,b),r′=b%r...根据欧⼏⾥得，这个过程会有⼀个尽头：dx+0y=gcd(a,b)，其中d=gcd(a,b)，为使等式成⽴，我们可以令x=1,y=0(当然也可以为其他值)这就找到了⼀组可⾏解，在⼀层层倒退回去，就能得到原始⽅程的⼀组整数解。

扩展的欧几里得算法扩展的欧几里得算法是一种求解最大公约数的算法，也被称为扩展欧几里得算法或扩展辗转相除法。

它不仅可以求出最大公约数，还可以求出一组使得两个数的线性组合等于最大公约数的系数。

本文将介绍扩展的欧几里得算法的原理、应用及其优化。

一、原理扩展的欧几里得算法是基于欧几里得算法（辗转相除法）的扩展。

欧几里得算法是一种求解最大公约数的方法，其基本思想是：用较小的数除较大的数，再用余数去除除数，如此反复，直到余数为零为止。

最后的除数就是最大公约数。

例如，求出48和18的最大公约数，过程如下：48 ÷ 18 = 2 (12)18 ÷ 12 = 1 (6)12 ÷ 6 = 2 0因此，最大公约数是6。

扩展的欧几里得算法的主要思想是在欧几里得算法的基础上，求出一组使得两个数的线性组合等于最大公约数的系数。

设a、b为两个正整数，d为它们的最大公约数，那么必定存在整数x和y，使得ax + by = d。

扩展的欧几里得算法就是通过辗转相除的过程，递归求解x和y的值。

具体来说，假设a、b为两个正整数，d为它们的最大公约数，且a > b。

则有：1. 如果b = 0，那么d = a，此时x = 1，y = 0。

2. 如果b ≠ 0，那么可以将a除以b，得到a = bq + r（其中q为a÷b的商，r为余数）。

因为d是a和b的公约数，所以d也是b和r的公约数。

因此，可以递归地求解b和r的系数x1和y1，即有：bx1 + ry1 = d由于a = bq + r，可以将其代入上式，得到：bx1 + (a - bq)y1 = d展开后得到：ay1 + b(x1 - qy1) = d因此，x = y1，y = x1 - qy1。

通过递归求解，最终可以得到x和y的值，从而求出a和b的最大公约数d以及一组使得两个数的线性组合等于最大公约数的系数。

二、应用扩展的欧几里得算法在密码学、数论、计算机图形学等领域都有广泛的应用。

欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数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)的公约数，贝Ud | b , d |r ,但是a = kb +r因此d也是(a,b)的公约数因此(a,b)和(b,a modb)的公约数是一样的，其最大公约数也必然相等，得证第二种证明：要证欧几里德算法成立,即证: gcd(a,b)=gcd(b,r), 其中gcd 是取最大公约数的意思, r=a mod b下面证gcd (a, b)=gcd(b, r)设 c 是a, b的最大公约数，即c=gcd (a, b),贝U有a=mc, b=nc,其中m, n 为正整数，且m，n 互为质数由r= a mod b 可知，r= a- qb 其中，q 是正整数，则r=a-qb=mc-qnc= ( m-qn) cb=nc,r=(m-qn)c ,且n, (m-qn)互质(假设n, m-qn不互质，贝U 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 )4 {5 int r = b; 得证。

算法的实现：最简单的方法就是应用递归算法，代码如下：1 int gcd( int a, int b)2 {3if (b==0) 4return a; 5return 6gcd(b,a%b);7 } 代码可优化如下：1 int gcd( int a, int b)2 {3return b ? gcd(b,a%b) : a;4 }当然你也可以用迭代形式： 1 int Gcd( int a, int b)2 {3while (b != 0) 6b = a % b; 7a = r;8 }a;9 return10 }扩展欧几里德算法基本算法：对于不完全为0的非负整数a , b, gcd (a, b)表示a , b的最大公约数，必然存在整数对x ，y ，使得gcd ( a，b) =ax+by。

扩展欧几里得算法：欧几里得算法中，计算x, y 的最大公约数的方法是辗转相除，例如：gcd (26, 15)26 % 15 = 1 (11)15 % 11 = 1 (4)11 % 4 = 2 (3)4 % 3 = 1 (1)3 % 1 = 3 0可知，gcd (26, 15) = 1如果gcd(x, y) = r，那么有ax + by = r，可以看出，上面的步骤实际上是可以直接得出a, b 的：null26 % 15 = 1 ... 11 => 11 = 26 - 15 1 1 -115 % 11 = 1 ... 4 => 4 = 15 - 11 = 15 - (26 - 15) = -26 + 2*15 1 -1 211 % 4 = 2 ... 3 => 3 = 11 - 4*2 = (26 - 15) - (-26 + 15) * 2 = 3*26 -5*15 2 3 -54 % 3 = 1 ... 1 => 1 = 4 - 3 = (-26 + 2*15) - (3*26 - 5*15) = -4*26 +7*15 1 -4 73 % 1 = 3 0在每一轮，我们都可以得到一个模的表达式为：ri = aix + biy如果不考虑第一轮和第二轮，那么ai 和bi 可以表示为(qi 为每一轮得到的商)：a i = a i-2 - q i * a i-1b i = b i-2 - q i * b i-1证明如下：输入：x,y,则有如下：x/y=q1…..r1 =>r1=x-q1*yy/r1=q2…r2 =>r2=y-q2*r1=y-q2*(x-q1*y)=-q2*x+(1+q2*q1)*y r1/r2=q3…r3 =>r3=r1-q3*r2=(x-q1*y)-q3*(-q2*x+(1+q2*q1)*y)=(1+q2*q3)x+(-q1-q3*(1+q2*q3))*y则可以看出有：a3=1+q3*q2=a1-q3*a2B3=b1-q3*b2由此可以推测出：a i = a i-2 - q i * a i-1b i = b i-2 - q i * b i-1但是a1,b1,a2,b2比较特别：a1=1=a-1 – q1*a0b1=-q1=b-1 – q1*b0由此我们可以知道a-1=1,a0=0,b-1=0,b0=1即可满足。

扩展的欧几里得&中国剩余定理扩展的欧几里得（EXTENDED-EUCLID）一、假设：对于给定的整数a和b，它们满足方程：ax+by=d=gcd(a,b)，求出整系数x，y二、推理：ax+by=gcd(a,b)=gcd(b,a%b)=bx+(a-(int)a/b*b)y=ay+b(x-(a-(int) a/b*y)三、扩展的欧几里得算法：1int extended_gcd(int a, int b, int &x, int &y)2 {3int ret, tmp；4if (!b) {5 x = 1; y = 0; return a;6 }7 ret = extended_gcd(b, a % b, x, y);8 tmp = x;9 x = y;10 y = tmp - a / b * y;11return ret;12 }复制代码四、应用：1、求解模线性方程：ax≡b (mod n)定理一：设d=gcd(a,n)，用扩展欧几里得算法解线性方程ax'+ny'=d.如果d|b,则方程axºb(mod n)有一个解的值x0=x'(b/d)mod n定理二：方程axºb(mod n)有解（即存在d|b,其中d=gcd(a,n)),x0是该方程的任意一个解，则该方程对模n恰有d个不同的解，分别为x(i)=x(0)+i(n/d)(i=1,2,...d-1)//用扩展欧几里得解模线性方程ax=b (mod n)bool modularLinearEquation(int a,int b,int n){int x,y,x0,i;int d=Extended_Euclid(a,n,x,y); //ax=b (mod n) 等价于ax+n y=bif(b%d)return false;x0=x*(b/d)%n;for(i=1;i<=d;i++)printf("%d\n",(x0+i*(n/d))%n);return true;}复制代码2、求乘法逆元：ax≡1（mod n）ax≡1（mod n）等价于ax+ny=1=gcd(a,n)，调用extended_gcd(a,n,&x,&y)，并当公约数ret=1时，x%n即为a的乘法逆元。

扩展欧几里得算法的证明扩展欧几里得算法是一种用于求解两个整数的最大公约数（GCD）以及一组满足贝祖等式的整数解的算法。

它是欧几里得算法的扩展，因此得名。

在本文中，我们将详细介绍扩展欧几里得算法的证明过程。

我们回顾一下欧几里得算法。

欧几里得算法是一种通过连续地应用辗转相除法来计算两个整数的最大公约数的方法。

给定两个整数a 和b，我们用r表示a除以b的余数，即r = a mod b。

如果r等于0，则b即为最大公约数。

如果r不等于0，则将b赋值给a，将r赋值给b，然后重复上述步骤，直到r为0。

扩展欧几里得算法的目标是求解贝祖等式的整数解。

贝祖等式的形式为ax + by = gcd(a, b)，其中x和y是整数。

扩展欧几里得算法通过迭代地计算出一系列的x和y，直到找到满足贝祖等式的解。

算法的基本思想是在欧几里得算法的每一步中，根据已知的x'和y'，通过一系列的变换得到新的x和y。

现在，我们开始证明扩展欧几里得算法的正确性。

我们使用数学归纳法来证明。

当b等于0时，根据欧几里得算法，最大公约数gcd(a, 0)等于a。

此时，贝祖等式变为ax + 0y = a，解为x = 1，y = 0。

因此，扩展欧几里得算法在这种情况下得到了正确的解。

接下来，假设扩展欧几里得算法在某一步中得到了一组解x'和y'，满足贝祖等式ax' + by' = gcd(a, b)。

我们需要证明，在下一步中，算法能够得到一组新的解x和y，满足贝祖等式。

根据欧几里得算法，我们有b = q * r + s，其中q是商，r是余数，s是一个辅助变量。

将这个等式代入贝祖等式，我们得到：ax' + (q * r + s)y' = gcd(a, b)。

进一步化简，我们有：ax' + q * rx' + sy' = gcd(a, b)。

根据归纳假设，我们知道ax' + by' = gcd(a, b)，因此我们可以将其代入上式，得到：gcd(a, b) + q * rx' + sy' = gcd(a, b)。

扩展欧⼏⾥得算法详解本篇将附上扩展欧⼏⾥得算法的思想与推导;对于⼀个⽅程a∗x+b∗y=gcd(a,b)来说,我们可以做如下的推导:设有a∗x1+b∗y1=gcd(a,b);同时我们有b∗x2+(a%b)∗y2=gcd(b,a%b);对于这个⽅程组,我们希望知道的是x1,x2,y1,y2之间的关系,这样我们才可以递归解决这个问题我们观察b∗x2+(a%b)∗y2这个式⼦,我们可以将(a%b)写作(a−⌊ab⌋∗b),将括号打开常数a,b合并,合并之后的结果为a∗y2+b∗(x2−⌊ab⌋∗y2))由于欧⼏⾥得算法的原理gcd(a,b)==gcd(b,a%b),我们将两式⼦联⽴,对⽐系数即可得到x1=y2,y1=x2−⌊ab⌋∗y2这个递归的边界是什么呢?我们知道,当朴素欧⼏⾥得到达边界时,return gcd(a,0)=a,那么边界条件就是对a∗x0+b∗y0=a求解,很显然,此时x0=1,y0=0当我们递归求出了⼀个⽅程的特解时,如何求出这个⽅程的通解呢?⽅程a∗x+b∗y=gcd(a,b)中,如果将x加上⼀个常数k1,y减去⼀个常数k2,仍然保持原⽅程成⽴,那么x+k1,y−k2就是⽅程的⼀个新解,这个k应该如何选择呢?实际上很简单,a∗(x+k1)+b∗(y+k2)=gcd(a,b),打开括号,a∗x+a∗k1+b∗y−b∗k2=gcd(a,b);我们保证原⽅程成⽴,就需要a∗k1==b∗k2,那么显然k1=b,k2=a是⼀种合理的情况,但是这样是⽆法包含所有整数解的,因为我们加上的这个值并⾮是最⼩值那我们应该加上什么值才⾏呢?我们发现当a∗k1==b∗k2=t∗lcm(a,b)可以保证得到所有解,于是每次寻找解就可以分别在x加上bgcd(a,b),在y减去agcd(a,b)就可以了对于⽅程a∗x+b∗y=c我们⼜该如何求解?我们发现如果(c%gcd(a,b)!=0)那么这个⽅程是⽆解的,⽽如果gcd(a,b)∗t==c,我们就可以按上⾯的⽅法求解之后对我们的解乘上⼀个t(t=c gcd(a,b))code:int exgcd(int a,int b,int &x1,int &y1) {if(!b){x1=1,y1=0;return a;}int x2,y2;int d=exgcd(b,a%b,x2,y2);x1=y2,y1=x2-(a/b)*y2;return d;}Processing math: 100%。