# 二次同余式化简

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

$$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)$$的形式