# 一次同余式

## **一次同余式有解**

&#x20;$$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)$$
>
>     &#x20;广义欧几里得除法得到特解$$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)$$
>
>     &#x20;得到特解$$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: 写出全部解**
>
>     &#x20; $$x\equiv d+t\cdot\frac{m}{\left(a,m\right)}\left(\mod m\right),t=0,1,\cdots,\left(a,m\right)-1$$
