# 擴展歐幾里德算法

----

給定整數$a、b$，求一組滿足$ax+by=gcd(a,b)$的整數解$(x,y)$
假設$a>b$
$1.$當$gcd(a,b)=b$時，可得$x=0,y=1$

$2.$根據歐幾里德算法(輾轉相除法)可得$gcd(a,b)=gcd(b,a$ $mod$ $b)=gcd(b,a-k*b)$，$k=\lfloor \frac{a}{b} \rfloor$
故$ax_1+by_1=gcd(a,b)=gcd(b,a-k*b)=bx_2+(a-k*b)y_2$
展開後得到$ax_1+by_1=a*y_2+b*(x_2-k*y_2)$
故$x_1=y_2，y_1=x_2-k*y_2$
於是我們可以用遞迴的方式得出一組解$x_1，y_1$

程式碼:

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

----
# 求解不定方程
一不定方程式$ax+by=c$有解若且唯若$gcd(a,b)\mid c$

設$(x_1，y_1)$滿足$ax_1+by_1=gcd(a,b)$，另一組解為$(x_2，y_2)$
$ax_1+by_1=gcd(a,b)=ax_2+by_2$，移項後得$a(x_1-x_2)=b(y_2-y_1)$
同除以$gcd(a,b)$得$a'(x_1-x_2)=b'(y_2-y_1)$，其中$a'=\frac{a}{gcd(a,b)}，b'= \frac{b}{gcd(a,b)}$
因$a'、b'$互質，故$b' \mid (x_1-x_2)$
設$(x_1-x_2)=kb'$，則$a'(x_1-x_2)=a'b'k=b'(y_2-y_1)$，$a'k=(y_2-y_1)$
由上可得以下結論
設$(x,y)$為$ax+by=gcd(a,b)$的一組解，則其他整數解$(x',y')$滿足$x'=x-k*\frac{b}{gcd(a,b)}，y'=y+k*\frac{a}{gcd(a,b)}$，其中$k$為任意整數
而$ax+by=c$的解只要將$(x_1，y_1)$同乘以$\frac{c}{gcd(a,b)}$便能得到

----
# 求解線性同餘方程
$ax≡b$ $mod$ $n$可以寫成$ax=b+kn$
移項後得$ax-nk=b=ax+n(-k)=b$
由上述可知此線性同餘方程有解若且唯若$gcd(a,n)\mid b$
於是便可利用求解不定方程的方法求出$x$
但因為是在模運算下，所以只求$0\leq x<n$的解即可

----
# 求模逆元
相當於求$ax≡1$ $mod$ $n$ $(n!=1)$
可知$a$在模$n$下的模逆元存在若且唯若$gcd(a,n)=1$