gcd
$gcd(n,m)=gcd(m,n \%m)$
一个常识
如果$a\leq b$ 并且$b\leq a$那么$a=b$
一个引理
假设$k|a,k|b$ 则对于任意的$x,y属于z，k|(xa+yb)$ 均成立
证明：
$k|a \to a=pk$ $k|b \to b=qk$
于是有$xa+yb=xpk+yqk=(xp+yq)k$
因为$k|(xp+yq)k$所以$k|(xa+yb)$
gcd的Euclid证明
证明：
令$k=gcd(n,m)$ 则$k|n$并且$k|m$
令$j=gcd(m,n\%m)$ 则$j|m$并且$j|(n \%m) $
对于$n$ 可以用$m$表示为$n=p\times m +n\%m$
由引理可知$j|n$(其中$x=p,y=1$),又$j|m$ 于是$j是n和m的公因数(但补一定最大)$
因为$k$是$m和n的最大公因数$ 所以$j\leq k$
通过另一种方式得到$n\%m=n-p\times m$
所以$k$是$n\%m$的因子,又$k|m$。于是$k是n\%m和m的公因子$ (但不是最大)
又$j>=k$ 所以$j==k$
所以$gcd(n,m)=gcd(m,n\%m)$
exgcd
求方程$ax+by=gcd(a,b)$的一个解
如果$b=0$ 那么$gcd(a,b)=a,取x=1,y=0$即可
否则：根据$gcd(a,b)=gcd(b,a\%b)$
那么递归求解$ bx+a\%by=gcd(a,b)$的解
然后推当前$x,y$
设$bx+a\%by=gcd(a,b)$的解为$x0,y0$
$ax+by=gcd(a,b)=bx0+a\%by$
$=bx0+(a-a/b\times b)y0$
$=bx0+ay0-a/b\times b y0$
$=ay0+b(x0-a/b \times y0)$
所以$x=y0,y=x0-a/b\times y0$