$ax^2+bx+c\equiv m\pmod{n}$
假射$a\neq 0$
$\exists p,s.t.p|n,(a,p)=(2,p)=1$
$x^2+a^{-1}bx+a^{-1}(c-m)
\equiv (x+\frac{a^{-1}b}{2})^2-(\frac{a^{-1}b}{2})^2+a^{-1}(c-m)\equiv 0\pmod{p}$
取$m=c-a(\frac{a^{-1}b}{2})^2+aq$
$(x+\frac{a^{-1}b}{2})^2\equiv q\pmod{p}$
若q不是p的二次剩餘,此式不可能成立,所以a=0。
$bx+c\equiv m\pmod{n}$
假射$b^2>1$,$n=b,m=c+1\Rightarrow 0\equiv 1\pmod{b}$矛盾
假射$b=0$,$n=2,m=c+1\Rightarrow 0\equiv 1\pmod{2}$矛盾
$\forall b^2=1$,$x=b(m-c)\Rightarrow bx+c\equiv m\pmod{n}$ |