一次同余式

一次同余式有解

$a\cdot x\equiv b\left(\mod m\right)$有解$\Longleftrightarrow\left(a,m\right)\mid b$ $x\equiv \frac{b}{\left(a,m\right)}\cdot\left({\left(\frac{a}{\left(a,m\right)}\right)}^{-1}\left(\mod \frac{m}{\left(a,m\right)}\right)\right)+t\cdot\frac{m}{\left(a,m\right)}\left(\mod m\right)$ $t=0,1,\cdots,\left(a,m\right)-1$

一次同余式求解

• STEP1: 验证有解

• STEP2: 求解$\frac{a}{\left(a,m\right)}\cdot x\equiv 1\left(\mod \frac{m}{\left(a,m\right)}\right)$

  广义欧几里得除法得到特解$x_{0}^{\prime}\equiv c\left(\mod \frac{m}{\left(a,m\right)}\right)$

• STEP3: 求同余式$\frac{a}{\left(a,m\right)}\cdot x\equiv \frac{b}{\left(a,m\right)}\left(\mod \frac{m}{\left(a,m\right)}\right)$

  得到特解$x_0\equiv \frac{b}{\left(a,m\right)}\cdot x_{0}^{\prime}\equiv \frac{b}{\left(a,m\right)}\cdot c\equiv d\left(\mod \frac{m}{\left(a,m\right)}\right)$

• STEP4: 写出全部解

  $x\equiv d+t\cdot\frac{m}{\left(a,m\right)}\left(\mod m\right),t=0,1,\cdots,\left(a,m\right)-1$