欧几里得推扩展欧几里得-蒲公英云

欧几里得推扩展欧几里得

欧几里得

求整数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'\\ 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' x′和 y ′ y' 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',y' 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'=x+b/g,y'=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;
}