合同方程式x^2≡-nの解の個数

$m = p_1^{e_1} p_2^{e_2} \dotsm p_r^{e_r}$を$m$の素因数分解とする．この時，中国剰余定理により，合同方程式
$$ y \equiv -n \pmod{p_i^{e_i}}, \quad i = 1, 2, \dotsc, r $$
は$m$を法として唯一つの解をもつ．よって，もしある$i$に対し$(-n / p_i) = -1$となるならば，合同方程式 (1) は解を持たない．すなわち，解の個数は$0 = \prod(1 + (-n / p))$である．各$i = 1, \dotsc, r$に対して$(-n / p) = 1$であるとする．このとき，もしも合同方程式$x^2 \equiv -n \pmod{p_i^{e_i}}$がそれぞれ2つの解しか持たないならば，中国剰余定理により合同方程式 (1) の解の個数が (2) によって与えらえることが従う．ゆえに，$m$が素数冪のときに定理が成り立つことを示せば十分である．
$m = p^e$ ($p$は素数，$e \ge 1$) とする．$e$に関する帰納法．$e = 1$のときは，合同方程式$x^2 \equiv -n \pmod{p}$は解を2つしか持たない．$e > 1$とし，合同方程式$x^2 \equiv -n \pmod{p^{e - 1}}$は解をちょうど2つ持つと仮定する．この時，$y^2 \equiv -n \pmod{p^e}$となるような$y$は全て$y = x + \ell p^{e - 1}$の形である．もし$(x + \ell p^{e - 1}) \equiv x^2 \equiv -n \pmod{p^e}$ ($0 \le \ell < p$) となるならば，$\ell p^{e - 1} (2x + \ell p^{e - 1})$が$p^e$で割り切れ，したがって$2x + \ell p^{e - 1}$が$p$で割り切れる．ゆえに$x$が$p$で割り切れることが従うが，これは$\gcd(p, n) = 1$に矛盾である．ゆえに合同方程式$x^2 \equiv -n \pmod{p^e}$はちょうど2つの解をもつ．