> For the complete documentation index, see [llms.txt](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/tong-yu-shi/yi-ci-tong-yu-shi.md).

# 一次同余式

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

 $$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$$