# 扩展欧几里得算法

# 欧几里得算法 Euclidean Algorithm

# 定理

对于$\forall 非负整数x,y$，均有$gcd(x, y) = gcd(y, x \% y)$

# 证明

不防设 $x > y$. 令$q=x/y, r=x\%y$. (k 为正整数)
$\Rightarrow x=qy + r, r=x-qy$.
不妨设$gcd(x, y)=d_{1}, gcd(y, r) = d_{2}$，即需证明d_{1}=d_

1. 由于$gcd(x,y)=d_{1}$，则$\Rightarrow d_{1}|x,d_{1}|y$（x 可以整除 d，y 可以整除 d）
   $\Rightarrow d_{1}|(x-qy) \Leftrightarrow d_{1}|r$.
   $\because d_{1}|y, d_{1}|r$
   \therefore d_{2}|d_

2. 由于$gcd(y,r)=d_{2}$，则$\Rightarrow d_{2}|y,d_{2}|r$

   $\Rightarrow d_{2}|(qy+r) \Leftrightarrow d_{2}|x$.
   $\because d_{2}|x, d_{2}|y$
   $\therefore d_{1}|d_{2}$
   固$d_{1}$=d_

# 实现

int gcd(int a, int b){

    return b == 0 ? a : gcd(b, a % b);

}

#

# 裴蜀定理

# 定理

对于任意整数$a、b$ 和$m$，如
$ax+by=m$
有整数解时，当且仅当$m$ 为$gcd(x，y)$ 的倍数
$\Leftrightarrow a、b$ 能凑出的最小正整数为$gcd(a,b)$

# 证明

如果$a$ 和$b$ 中有一个是 0，比如$a=0$，那么它们两个的最大公约数是$𝑏$。这时裴蜀等式变成$𝑏𝑦=𝑚$，它有整数解$(𝑥,𝑦)$ 当且仅当$m$ 是$b$ 的倍数，而且有解时必然有无穷多个解，因为$x$ 可以是任何整数。定理成立.
以下设$a、b$ 均不为 0.

# 扩展欧几里得算法 Extended Euclidean Algorithm

# 定理

# 证明