2次合同方程式(2)

[ 例題 ] 次の合同方程式を解け。 \[ x^2 + 5x + 2 \equiv 0 \pmod{13} \] [ 解法① ]
合同式の法を $13$ とする。 両辺を $4$ 倍すると \[ \begin{aligned} 4x^2 + 20x + 8 &\equiv 0 \\ (2x+5)^2 - 25 + 8 &\equiv 0 \\ (2x+5)^2 &\equiv 17 \\ &\equiv 4 \end{aligned} \] そこで、$y = 2x+5$ とおくと与えられた合同方程式は \[ y^2 \equiv 4 \] となり、「2次合同方程式(1)」と同様の問題になる。 これを解くと $y \equiv 2, 11$ である。 $y$ を戻すと $2x+5 \equiv 2, 11$ であり、これは「1次合同方程式(1)」と同様の問題である。 解は $x \equiv 3, 5 \pmod{13}$ である。
[ 解法② ]
合同式の法を $13$ とする。1次の係数を調整して \[ \begin{aligned} x^2 + 5x + 2 &\equiv 0 \\ x^2 - 8x + 2 &\equiv 0 \\ (x-4)^2 - 16 + 2 &\equiv 0 \\ (x-4)^2 &\equiv 14 \\ &\equiv 1 \end{aligned} \] 以下 [解法①] と同様だが、$x$ の係数が $1$ なのでこちらの方が簡単だろう。
[ 解法③ ]
合同式の法を $13$ とする。 解の候補は $x \equiv 0,1,2, \dots, 12$ である。 これらの候補のうち $x^2 + 5x + 2 \equiv 0$ を満たすものをしらみ潰しに探すと $x \equiv 3, 5$ のみが解であることが分かる。 以上より、解は $x \equiv 3, 5 \pmod{13}$ である。