欧几里得推扩展欧几里得

我会带着你远行 2022-06-13 09:22 253阅读 0赞

## 欧几里得 ##

求整数a,b的最小公约数gcd(a,b)的算法。即欧几里得算法(俗称最小公倍数算法)。  
有一个重要的公式如下,这个公式的证明略,百度上有.  
 (1) g c d ( a , b ) = g c d ( b , a   m o d   b ) gcd(a,b)=gcd(b,a\\ mod\\ b)\\tag\{1\} gcd(a,b)=gcd(b,a mod b)(1)  
我们不妨考虑a，b为正整数的情况。令gcd(a,b)=g，则  
 a = k 1 g b = k 2 g a=k\_1g\\\\ b=k\_2g a=k1gb=k2g  
首先k1和k2肯定互质,即gcd(k1,k2)=1,否则说明a,b存在一个更大的约数，这与gcd(a,b)=g矛盾。  
那么由(1)式我们知道k1,k2辗转相减一定会定于1。我们就会得到下面的一个结论.

> **若a,b互质(gcd(a,b)=1),则 ax+by=1 一定存在整数解(x,y)**  
> 扩展的,  
> **若gcd(a,b)<>1,则 ax+by=gcd(a,b) 一定存在整数解(x,y)**  
> 因为同除gcd(a,b)有解.

由此我们引出扩展欧几里得

## 扩展欧几里得 ##

通过上面的结论,我们可以推出扩展欧几里得.下面我们来看一下如何求这样的整数解(x,y)之一.  
根据公式

(1) g c d ( a , b ) = g c d ( b , a   m o d   b ) gcd(a,b)=gcd(b,a\\ mod\\ b) \\tag\{1\} gcd(a,b)=gcd(b,a mod b)(1)  
 (2) a x + b y = g c d ( a , b ) ax+by=gcd(a,b)\\tag\{2\} ax\+by=gcd(a,b)(2)  
● 对于(2)式,当b=0时,ax+by=gcd(a,b)=a,显然(x=1,y=0)是方程的一个解.  
● 当b不为0时,根据欧几里得定理(1式)gcd(a,b)=gcd(b,a mod b)可得  
 g c d ( a , b ) = g c d ( b , a   m o d   b ) ⇒ a x + b y = g c d ( a , b ) = g c d ( b , a   m o d   b ) = b x ′ + ( a   m o d   b ) y ′ ⇒ a x + b y = b x ′ + ( a   m o d   b ) y ′ = b x ′ + ( a − b ∗ ⌊ a / b ⌋ ) y ′ 移项得 a x + b y = a y ′ + b ( x ′ − ⌊ a / b ⌋ y ′ ) \\begin\{aligned\} gcd(a,b) & =gcd(b,a\\ mod\\ b)\\\\ \\Rightarrow \\qquad ax+by=gcd(a,b) & =gcd(b,a\\ mod\\ b)=bx′+(a\\ mod\\ b)y′\\\\ \\Rightarrow \\qquad \\qquad\\qquad\\quad ax+by &=bx′+(a\\ mod\\ b)y′=bx′+(a−b∗⌊a/b⌋)y′\\\\ \\text\{移项得\}\\qquad \\qquad ax+by &=ay′+b(x′−⌊a/b⌋y′) \\end\{aligned\} gcd(a,b)⇒ax\+by=gcd(a,b)⇒ax\+by移项得ax\+by=gcd(b,a mod b)=gcd(b,a mod b)=bx′\+(a mod b)y′=bx′\+(a mod b)y′=bx′\+(a−b∗⌊a/b⌋)y′=ay′\+b(x′−⌊a/b⌋y′)

根据恒等定理,有 \{ x = y ′ y = x ′ − ⌊ a / b ⌋ y ′ \\text\{根据恒等定理,有\}\\qquad \\begin\{cases\} x=y&\#x27;\\\\ y=x′−⌊a/b⌋y′ \\end\{cases\}\\qquad\\qquad\\qquad\\qquad\\qquad\\quad 根据恒等定理,有\{ x=y′y=x′−⌊a/b⌋y′

这有什么用呢?x′和y′还是不知道呀.  
重新来看看我们得到的两个等式.x和y是 g c d ( a , b ) = a x + b y gcd(a,b)=ax+by gcd(a,b)=ax\+by的解,而 x ′ x&\#x27; x′和 y ′ y&\#x27; y′是在对gcd(a,b)按欧几里德算法进行一步后的结果对应的贝祖等式 g c d ( b , a   m o d   b ) = b x ′ + ( a   m o d   b ) y ′ gcd(b,a\\ mod\\ b)=bx′+(a\\ mod\\ b)y′ gcd(b,a mod b)=bx′\+(a mod b)y′的解.也就是说,**gcd(a,b)对应的贝祖等式的解x,y可以由gcd(b,a mod b)对应等式的解 x ′ , y ′ x&\#x27;,y&\#x27; x′,y′计算得出.**

> **说的通俗点,由于欧几里德算法最后一步为gcd(a,0)=a**  
> **此时对应的等式的解为 x=1,y=0,因此只需从最后一层1a+0b=gcd(a,0)=a 向上一层推倒求解.**  
> **即在进行欧几里德算法的递归的时候根据相邻两次调用间x,y和x’,y’的关系计算即可求出ax+by=gcd(a,b)的解.**  
> **请结合文末9行代码理解**

更进一步,对于任意不定式ax′+by′=c,只需要在等式ax+by=gcd(a,b)=d两边乘上c/d即可得到解为x′=x∗c/d,y′=y∗c/d

### 解的范围 ###

递归算到最后y其实可以取任意整数。但是取的太大容易导致使得最后算出来的解爆int之类的事情  
下面我们来看一下最终算出来的解x,y的绝对值大小情况  
由x y的计算方法 x -= (a / b) \* y 可以知道，x y始终是在  max ⁡ ( ∣ a ∣ , ∣ b ∣ ) \\max(|a|, |b|) max(∣a∣,∣b∣) 的绝对值范围内的，因此  a ∗ x + b ∗ y = g c d ( a , b ) a\*x + b\*y = gcd(a, b) a∗x\+b∗y=gcd(a,b) 最后算出的x y的绝对值大小跟a b是同一个级别的。

### 如何得到所有解? ###

实际上在之前的计算和证明中我们得到的只是不定方程的一组解,那么怎样得到所有解呢?对于一般形式  a x + b y = g ax+by=g ax\+by=g 有通解  ( x , y ) (x,y) (x,y) ,则  x ′ = x + b / g , y ′ = y − a / g x&\#x27;=x+b/g,y&\#x27;=y−a/g x′=x\+b/g,y′=y−a/g .(证明略,只要代入一下就知道为什么通解是这个了)

### exgcd代码 ###

int exGcd(int a,int b,int &x,int &y) { 
        if(b==0) { 
            x=1;y=0;      //边界解,1a+0b=gcd(a,0)=a 
            return a;
        }
        int r=exGcd(b,a%b,x,y);   //求下一层的解(x',y')
        int t=x;x=y;y=t-a/b*y;    //根据下一层的解(x',y'),求出本层的解(x,y)
        return r;
    }

友情回顾  
 \{ x = y ′ y = x ′ − ⌊ a / b ⌋ y ′ \\begin\{cases\} x=y&\#x27;\\\\ y=x′−⌊a/b⌋y′ \\end\{cases\}\\qquad\\qquad\\qquad\\qquad\\qquad\\quad \{ x=y′y=x′−⌊a/b⌋y′