目录
- 扩欧用途
- 扩欧推导过程
本文为oiwiki内容整理，主要是过一遍思路，也权当LaTex数学公式练习，侵权紫衫
LaTex公式表
oiwiki上的扩欧
扩欧用途
扩欧(exgcd)，常用来解决形如$$ax+by=gcd(a,b),其中\ a,b,x,y\in\Z$$的方程可行解。
扩欧推导过程
设
\[\begin{cases}
ax_1+by_1=\gcd(a,b)\\
bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)
\end{cases}\\
\]
\[\begin{align*}
\because \gcd (a,b)&=\gcd (b,a\bmod b)\\
\therefore ax_1+by_1&=bx_2+(a\bmod b)y_2\\
\text{and that}\,\,\,a\bmod b&=a-(\lfloor{\dfrac{a}{b}}\rfloor\times b)\\
\therefore ax_1+by_1&=ay_2+b(x_2-\lfloor{\dfrac{a}{b}}\rfloor)\\
\because a=&a,b=b\\
\therefore\begin{cases}
x_1=y_2\\y_1=x_2-\lfloor{\dfrac{a}{b}}\rfloor\end{cases}
&\text{ is a legit solution for recursing}
\end{align*}
\]
Therefore, we just ahve to keep recursing until \(b=0\) ,and we have \(\begin{cases}x_0=1\\y_0=0\end{cases}\) as the end of recursion.