> 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/er-ci-tong-yu-shi-he-ping-fang-sheng-yu/er-ci-tong-yu-shi-hua-jian.md).

# 二次同余式化简

## **一般二次同余式化简**

$$ax^2+bx+c\equiv 0\left(\mod m\right),a\not\equiv0\left(\mod m\right)$$

> $$m=p\_{1}^{\alpha\_1}\cdots p\_{k}^{\alpha\_k}$$ $$\left{ \begin{array}{**lr**} ax^2+bx+c\equiv 0\left(\mod p\_{1}^{\alpha\_!}\right) &\ \vdots &\ ax^2+bx+c\equiv 0\left(\mod p\_{k}^{\alpha\_k}\right) \end{array} \right.$$

## **素数幂的同余式化简**

$$ax^2+bx+c\equiv 0\left(\mod m\right),a\not\equiv0\left(\mod m\right)$$

$$p$$为奇素数，$$\left(2a,p\right)=1$$

> * **STEP1:** 两端同时乘以$$4a$$
> * **STEP2:** $${\left(2ax+b\right)}^2\equiv b^2-4ac\left(\mod p^{\alpha}\right)$$
> * **STEP3:** 令$$y=2ax+b$$，有$$y^2\equiv b^2-4ac\left(\mod p^{\alpha}\right)$$

即简化为$$x^2\equiv a\left(\mod m\right)$$的形式