扩展欧几里得算法（Exgcd） 裴蜀定理 对于任意一组整数\(a,b\)，存在一组整数\(x,y\)，满足\(ax+by=\gcd(a,b)\)。 Proof： 考虑数学归纳法。 当\(b=0\)时，由于\(\gcd(a,0)=a\)，则对于\(ax+0y=a\)这个不定方程，\(x=1\)，\(y\)取任意整数。 假设存在一组整数\(x,y\)，满足$bx+(a\bmodb)y=\gcd(b,a\bmodb)=\gcd(a,b)$。 那么接下来证明也存在一组整数\(x',y'\)满足\(ax'+by'=\gcd(a,b)\)。 \[\begin{aligned}bx+(a\bmodb)y...