线性同余方程

$quad $ 给定整数a,b,m，求一个整数x满足(a*x equiv b (mod m)),或者给出无解。因为未知数的指数为1，所以我们称之为一次同余方程，也称线性同余方程。
$quad $ (a*x equiv b (mod m))等价于 (a*x-b)是m的倍数，不妨设为-y倍，于是该方程可改写为(a*x+m*y=b)
$quad $ 根据裴蜀定理及扩展欧几里得的知识，线性同余方程有解当且仅当满足gcd(a,m)|b。
$quad $ 当有解时，可以先用扩展欧几里得算法求出一组整数(x_0,y_0)，满足(a*x_0+m*y_0=gcd(a,m))然后(x=x_0*frac{b}{gcd(a,m)})就是原线性方程的一个解，通解就是所有模(frac{m}{gcd(a,m)})与x同余的整数.