Find m $\in \mathbb N$ that as condition is product of $3$ primes and the equation $x^2 +1 \equiv 0 \pmod{m}$ has $8$ solutions modulo $m$

Question

What I thought was that if

$$x^2 +1 \equiv 0 \pmod{m}$$

has to be met, then $$x^4 \equiv 1 \pmod{m}$$

it's also a condition.

Then I looked for primes that hold to this condition, and using brute force, find 3 primes with 2 solutions each.

After an extensive trial an error, I found that $5,13$ and $29$ so by the Chinese remainder theorem, there has to be 8 solutions modulo $m= 5.13.29$

Now my question is, there is a better, and elegant way to justify this?

Answer 1

Hint: The congruence $x^2+1\equiv 0\pmod{p}$ has $2$ distinct solutions if and only if $p$ is of the shape $4k+1$.

Remark: Your example is fine. The cheapest example uses $(5)(13)(17)$.