前言
本文通过尽量短，通俗易懂的形式帮助大家理解最简单的 exgcd。
前置知识：
欧几里得算法（辗转相除法）
\[gcd(a,b)=gcd(b,a\bmod b)\ \ \ (b\neq 0) \]模运算的本质:
\[a\bmod b = a - \left\lfloor \frac{a}{b}\right\rfloor b \]其中 \(\left\lfloor \frac{a}{b}\right\rfloor\) 指的是 \(\frac{a}{b}\) 下取整。
正片：
exgcd，扩展欧几里得，扩欧，是求下面这个不定方程解的方法:
\[ax+by=gcd(a,b) \]把后面的 \(gcd(a,b)\) 辗转相除一下再写成类似的形式（这里的 \(x',y'\) 是对应 \(gcd(b,a\bmod b)\) 的 \(x,y\)，和上面的 \(x,y\) 没有关系）：
\[bx'+(a\bmod b)y'=gcd(b,a\bmod b) \] \[ax+by=gcd(a,b)=gcd(b,a\bmod b)=bx'+(a-\left\lfloor\frac{a}{b}\right\rfloor b)y' \] \[ax+by=bx'+(a-\left\lfloor\frac{a}{b}\right\rfloor b)y' \]因为要求解 \(x,y\)，所以假设我们已经求解了 \(x',y'\)，则要按 \(a,b\) 把两个方程分开，然后就可以递归求解了。（貌似没有为什么，就是这么处理然后是可以递归求解的）
\[ax+by=ay'+b(x'-\left\lfloor \frac{a}{b}\right\rfloor y') \]解出 \(x,y\) 就要求解 \(x'y'\)，注意求解 \(x'y'\) 的时候，他们对应的 \(a,b\) 实际上是原先 \(x,y\) 的 \(a,b\) 的 \(b,a\bmod b\)。
递归就能求出 \(ax+by=gcd(a,b)\) 一组特解了，最后当 \(b=0\) 的时候递归终止，此时 \(ax+by=gcd(a,b)\) 的解显然是 \(x=1,y=0\) （ \(0\) 和非零数的 \(gcd\) 仍为那个数本身）。
后记
这样最基础的 exgcd 就到这里了，如果想进一步理解更深层的 exgcd，推荐阅读:
洛谷日报#288 [_Leaving]同余方程-5天从入门到入土