关于欧几里得算法与裴蜀定理的证明
前言：
因为某次考试订正 T4，用到了 exCRT，然后发现我和 lws 不会 exgcd……
所以来把 gcd 到 exgcd 重新学一下，就写了这篇 trick。
欧几里得算法：
求证：
记：
\(a=qb+r\)，其中 \(q=\lfloor \frac a b \rfloor\)，\(r=a \bmod b\)。
\(d=\gcd(b,r)\)，且 \(b=dx\)，\(r=dy\)，\(x\perp y\)。
证明：
当 \(b=0\) 时，由定义 \(\gcd(a,b)=a\)，之后我们考虑 \(b\ne 0\) 的情况。
显然 \(\gcd(a,b)=\gcd(qb+r,b)=d\gcd(qx+y,x)\)。
设 \(\gcd(qx+y,x)=g\)，此时 \(g\mid x\)，且 \(g\mid qx+y\)，即 \(q\mid y\)。
然而 \(x\perp y\)，所以 \(g=1\)。
故 \(\gcd(a,b)=d\gcd(qx+y,x)=d\)。
裴蜀定理：
用于求解形如 \(ax+by=\gcd(a,b)\) 的方程的特解。
过程：
记 \(bx_0+(a\bmod b)y_0=\gcd(b,a\bmod b)\)，\(ax_1+by_1=\gcd(a,b)\)。
由欧几里得算法，我们可以联立两方程：\(bx_0+(a\bmod b)y_0=ax_1+by_1\)。
同样记 \(a=qb+r\)，则 \(bx_0+(a-qb)y_0=ax_1+by_1\)。
拆下系数：\(ay_0+b(x_0-qy_0)=ax_1+by_1\)。
那么可得 \(x_1=y_0,y_1=x_0-\lfloor\frac a b\rfloor y_0\)。
边界即为 \(ax+0y=a\)，此时取 \(x=1,y=0\) 即可（当然 \(y\) 其实可以为任意整数）。
求解通解：
在 \(ax+by=1\) 中，我们的通解为 \(x=x_0+db,y=y_0-da\)。
而对于 \(ax+by=\gcd(a,b)\) ，此时的通解应表示为 \(x=x_0+d\frac b {\gcd(a,b)},y=y_0-d\frac a{\gcd(a,b)}\)，此处 \(x_0,y_0\) 为一组特解。
证明：
带入 \(x,y\) 到原方程，可得：\(a(x_0+d\frac b{\gcd(a,b)})+b(y_0-d\frac a{\gcd(a,b)})=ax_0+by_0+\frac{adb}{\gcd(a,b)}-\frac{adb}{\gcd(a,b)}=\gcd(a,b)\)。
故该形式确实表示了 \(ax+by=\gcd(a,b)\) 的一组解。
然后考虑任意两组解 \(x_1,y_1\) 和 \(x_2,y_2\)。
作差可以得到 \(a(x_1-x_2)+b(y_1-y_2)=0\)，即 \(a(x_1-x_2)=-b(y_1,y_2)\)。
提出 \(\gcd(a,b)\)，得到 \(\frac a{\gcd(a,b)}(x1-x2)=-\frac b{\gcd(a,b)}(y_1-y_2)\)。
由于 \(\frac a{\gcd(a,b)}\perp\frac b{\gcd(a,b)}\)，所以 \(\frac a{\gcd(a,b)}\mid(y_1-y_2)\)，\(\frac b{\gcd(a,b)}\mid(x_1-x_2)\)。
故该形式可以表示出 \(ax+by=\gcd(a,b)\) 的所有解。
进一步扩展
\(ax+by=c\) 在 \(\gcd(a,b)\mid c\) 时同样被确定有解。
考虑在 \(ax+by=\gcd(a,b)\) 两边同时乘上一个 \(\frac c{\gcd(a,b)}\)。
得到 \(\frac {ac}{\gcd(a,b)}x+\frac{bc}{\gcd(a,b)}y=c\)。
这个方程的通解形式与上面的方程相同，这里由于 \(\frac a{\gcd(a,b)}\perp\frac b{\gcd(a,b)}\)，所以 \(\gcd(\frac{ac}{\gcd(a,b)},\frac{bc}{\gcd(a,b)})=c\)。
这个通解就写为 \(x+d\frac{\frac{bc}{\gcd(a,b)}}{c},y-d\frac{\frac{ac}{\gcd(a,b)}}{c}\)，，带入化简可得到 \(x+d\frac b{\gcd(a,b)},y-d\frac a{\gcd(a,b)}\)。
注意上面的 \(x\) 是在 \(ax+by=\gcd(a,b)\) 的解乘上 \(\frac c{\gcd(a,b)}\) 后得到的。