$\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同余的整数.