黄博士网: 在线数学手册软件,电化学虚拟实验室,虚拟电化学工作站,电化学软件 关于 | 科学 | 数学 | 手册 | 软件 | 计算器 | 电化学 | 虚拟实验室 | 帮助 | 论坛 | 联系 | English

一次同余方程

一次同余方程可解条件

同余方程 \[ a_1 x_1 + \cdots + a_n x_n \equiv b\left( {\bmod m} \right) \] 有解的充分必要条件是: \[ \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不同余.




参阅