0%

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

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

1
2
3
4
def gcd(a, b):
if(b==0):
return a
return gcd(b, a%b)
1
2
3
int gcd(int a, int  b) {
return b?gcd(b, a%b):a;
}

exgcd

1
2
3
4
5
6
7
8
9
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
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;
}
Have fun.