Finding mod of X^2+1 = 0 to have exactly 4 solutions Find a natural number $m$ that is product of 3 prime numbers, and that the equation $x^2+1 \equiv 0 \text { (mod m)}$ has exactly 4 solutions mod m.
 A: We sketch, mostly without proof, some standard theory. Let $m$ have prime power factorization 
$$m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}.$$
The congruence $x^2\equiv -1\pmod{m}$ is solvable if and only if the congruence $x^2\equiv -1\pmod{p_i^{a_i}}$ is solvable for all $i$. 
Moreover, let $e_i$ be the number of solutions of the congruence $x^2\equiv -1\pmod{p_i^{a_i}}$. Then the number of solutions of $x^2\equiv -1\pmod{m}$ is $e_1e_2\cdots e_k$.
Briefly, this is because given solutions $c_i$ of $x^2\equiv -1\pmod{p_i^{a_i}}$, we can use the Chinese Remainder Theorem to find a solution $x$ of the system of congruences $x\equiv c_i \pmod{p_i^{a_i}}$, and this will satisfy $x^2\equiv -1\pmod{p_i^{a_i}}$.
So far we have not used any properties of $x^2+1$ other than it is a polynomial. 
But now we need to examine the solvability of $x^2 \equiv -1\pmod{p^a}$.
The prime $2$ is special. The congruence $x^2\equiv -1\pmod{2}$ has one solution, while for $a\gt 1$, the congruence $x^2\equiv -1 \pmod{2^a}$ has no solutions.
We turn to the odd primes $p$. It is a standard theorem that the congruence $x^2\equiv -1 \pmod{p^a}$ has no solutions if $p$ is of the form $4q+3$, and has exactly two solutions if $p$ is of the form $4q+1$.
This is enough information to solve any problem of the same general type as the problem in the OP.  
To be specific, if we have $3$ distinct primes $p_1,p_2,p_3$, and $m=p_1p_2p_3$, then the congruence $x^2\equiv -1\pmod{m}$ has $e_1e_2e_3$ solutions, where $e_i$ is the number of solutions of $x^2\equiv -1\pmod{p_i}$. Since $e_i=1$ if $p_i=2$, and $e_i=0$ or $2$ otherwise, if $e_1e_2e_3=4$ we must have one of the $p_i$ (say $p_1$) equal to $2$, and the other two must be of shape $4q+1$.
The first few possibilities are $m=(2)(5)(13)$, $m=(2)(5)(17)$, $(2)(5)(29)$, $(2)(5)(37)$, $(2)(5)(41)$, and $(20(13)(17)$.
For example, let us look at $m=(2)(5)(17)$. Solutions of $x^2\equiv -1$ modulo the primes $2, 5,17$ are respectively $1$, $\pm 2$, $\pm 4$. So we want to find $x$ which is odd and is congruent to $\pm 2\pmod{5}$, and to $\pm 4\pmod{17}$. 
That gives us $4$ systems of congruences to solve, using the machinery of the CRT, or by inspection. Let us solve for example $x$ odd, congruent to $2$ mod $5$, and to $-4$ modulo $17$. A quick search yields $x=47$.
This shows that $-47$ solves the problem for $x$ odd, congruent to $-2$ modulo $5$, and to $4$ modulo $17$. 
Only two more to go, really only one, since we can switch signs. 
A: The smallest solution is $m=130=2 \cdot 5\cdot 13$, with roots of $x^2+1 \equiv 0 \pmod m$  being $\{47, 57, 73, 83\}$
