欧几里得算法与扩展欧几里得算法

Let $gcd(a,b)=left( a, bright)=r$
Then $a=pr, b=qr, a pmod b=a-kb=pr-kqr mid r$
$Rightarrow gcd(a,b) = gcd(b, a%b)$

Then we prove that the gcd is max gcd.(Oh, my poor English.)
There are two ways to prove it.
First Way:
Presume that $r$ is the maxium gcd(a,b), and $r$ is different from $r’$ which is the maxium $gcd(b, a% b)$.
It means $r > r’$.
$a=pr, b=qr, a% b=pr-kqr$
$rmid b, rmid (a% b), r>r’$
so $r$ is maxium $gcd(b, a% b)$, it’s against to the condition which we presumed.
so $r$ is the maxium $gcd(a, b)$ and $gcd(a, a% b)$.

Second Way:
Let set $A$ be all factor of $gcd(a, b)$, and let set $B$ be all factor of $gcd(b, a% b)$.

1. if $din A$, $a=pd, b=qd, a% b=pd-kqd$
   so $dmid (a% b), din B$

2. if $din B$, $b=pd, a% b=qd, a=kqd + pd$
   so $d mid a, din A$

It means $A=B$, so $gcd(a,b)_{max}=gcd(b, a% b)_{max}$

1
2
3
4

def (a, b):
    if(b==0):
        return a
    return gcd(b, a%b)

1
2
3

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

$$xa + by = r$$ $$x(left lfloor frac{a}{b} right rfloortimes b + a% b) + yb = r$$ $$(xleft lfloor frac{a}{b} right rfloor+y)b + xa% b=r$$ $$left{begin{matrix} x'=xleft lfloor frac{a}{b} right rfloor+y\ y'=xend{matrix}right.Rightarrow left{begin{matrix}x=y'\ y=x'-y'left lfloor frac{a}{b} right rfloorend{matrix}right.$$

1
2
3
4
5
6
7
8
9

def exgcd(a, b):

#        a, b = b, a
    if(b==0):
        return 1, 0, a
    x1, y1, r = exgcd(b, a%b)
    x = y1
    y = x1-(a//b)*y1
    return x, y, r

1
2
3
4
5
6
7
8
9

int exgcd(int a, int b, int &x, int &y) {
    if(!b) {
        x=1, y=0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y-=(a/b)*x;
    return d;
}