免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖
$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}$

TOP

返回列表 回复 发帖