同余方程 a1x1+⋯+anxn≡b(mod 有解的充分必要条件是: \left( {a_1 , \cdots ,a_n ,m} \right)|b 当满足此条件时,其解数(对模m的不同余者)为 m^{n - 1} \left( {a_1 , \cdots ,m} \right)
一元一次同余方程 ax + b \equiv 0\left( {\bmod m} \right) 有解的充分必要条件是: \left( {a,m} \right)|b ,若有解则共有 \left( {a,m} \right) 个互不同余的解 \left( {\bmod m} \right) 解法如下:
设 \left( {a,m} \right) = d , d|b ,则原方程化为 \frac{a}{d}x + \frac{b}{d} \equiv 0\left( {\bmod \frac{m}{d}} \right),\left( {\frac{a}{d},\frac{m}{d}} \right) = 1 记作 a'x' + b' \equiv \left( {\bmod m'} \right),\left( {a',m'} \right) = 1 首先由辗转相除法 x_0 ,y_0 ,使得 a'x_0 + m'y_0 = 1 则 x' = - b'x_0 是同余方程的解,最后得到 x = x' + m't,t = 0,1, \cdots ,d - 1 为原方程的解 \left( {\bmod m} \right) .即有d个解 x',x' + \frac{m}{d},x' + \frac{{2m}}{d}, \cdots ,x' + \frac{{\left( {d - 1} \right)m}}{d} 对模m不同余.