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

gcd

Let $\gcd(a,b)=\left( a, b\right)=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$
$r\mid b, r\mid (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 $d\in A$, $a=pd, b=qd, a\% b=pd-kqd$
   so $d\mid (a\% b), d\in B$

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

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

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

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

exgcd

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

def exgcd(a, b):
#    if(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

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;
}