扩展欧几里得与扩展中国剩余定理
扩展欧几里得（exgcd）
对于两个整数a与b，一定会有且仅有一组整数x与y使得：
那么通过这一个性质，我们可以求出x与y的一组特解。
由欧几里得可以得到，gcd(a,b)=gcd(b,a mod b)。这是我们常用的辗转相除法的原理。我们在用欧几里得做辗转相除求gcd时有一个函数——gcd(a,b)。之后我们会递归gcd(b,a mod b)。我们设当前这一层程序的x与y为x1与y1，设接下来递归下去的程序x与y为x2与y2。
那么按照这一个式子写下来，我们便可以得到：
（注意：a与b应该是当前的a与b而不是全局的a与b）
由于我们不断递归，最后a mod b=0时弹出，也就是当一个子程序的b=0时即可退出。这个时候a=gcd(a,b)（第一个a是当前子程序的a，第二个a与b是全局变量的a与b）。此时x=1,y=0，即gcd(a,b)*1+0*0=gcd(a,b)。所以我们可以用一个全局变量x与y记录我们递归得到的x2与y2。之后我们用更新x与y，在父程序中继续使用。
最后弹出的x与y就是一组特解。
同余方程
那么，也就是说，我们用欧几里得拓展解出了a*x+b*y=gcd(a,b)的一组解。由于a*x mod b=gcd(a,b)可以写作a*x+b*y=gcd(a,b)（由于y只是一个满足要求的常数，所以我们可以任意取，只需满足要求即可），因此我们便解出了同余方程a*x mod b=gcd(a,b)的一组解。
那么我们自然不想只得到一个解，而且，我们也不想只能求a*x mod b=gcd(a,b)的解，而是希望可以拓展到a*x mod b=c上去。所以我们便用a*x+b*y=gcd(a,b)来做奠基，拓展同余方程的解法。
我们需要解决的是a*x mod b=c的通解。
其实按理来说，如果b是一个质数，我们直接乘上a(mod b)的逆元就好了。但是b不一定是质数，所以我们还是需要扩展欧几里得（条件限制更宽松）的算法来计算。
同余方程解存在性问题
首先我们需要知道：
（遗憾的是百度百科上也并没有任何有关的说明）。
后来搜了很久发现有一个题：“小珂的苦恼”正好是这一点的运用。看了一些题解之后算是明白了一些。然而各种题解相互盗取——连话都是一模一样……自己想了一个无奈的证明办法，供各位参考。
由欧几里得拓展我们可以得到，存在一组x与y使得a*x+b*y=gcd(a,b)。将等式两边同时乘以整数k，即a*x*k+b*y*k=gcd(a,b)*k。如果c mod gcd(a,b)=f，则0<=f<gcd(a,b)。
那么可以令c=gcd(a,b)*k+f。这样一来，就有a*x*k+b*y*k+f=c。
若f<>0，由于f<gcd(a,b)<=a<=b（假设a<=b），所以不存在f=a*m（m为整数），也就不存在a*(x*k+m)+b*y*k=c。也就是说，不存在a*x+b*y=c的整数解x与y。
所以f=0，即只有当c mod gcd(a,b)=0时，a*x+b*y=c有正整数解。得证。
（插一句，本人已经把如上方法贴至百度百科，望各位大神修改）
接下来我们便可以开始进行不定方程求正整数解了。
同余方程的通解
我们可以很容易得出a*x+b*y=gcd(a,b)的解。
同余方程的合并
为了方便，取x前的系数为1。
如果不取x前的系数为1，那么就需要先用exgcd求出x的表达式，之后做同样的推导。
扩展中国剩余定理（excrt）
给出n个同余方程组，求同余方程组的通解。
其实只需要把所有的同余方程合并成同一个方程，最后一趟exgcd就好了。
中国剩余定理与扩展中国剩余定理的主要用途在于拆分模数。在(modp)意义下，如果p不是一个质数，可以把p质因数分解，对于每一组p[i]^k[i]，他们两两互质（可以直接中国剩余定理），所以最后再用crt或者excrt求解即可。