二次同余式化简

一般二次同余式化简

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