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.


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.


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\}$

  • $\begingroup$ how to derive this? $\endgroup$ – lab bhattacharjee Dec 10 '13 at 15:00
  • $\begingroup$ thanks, can you tell me what was the reasoning behind that? $\endgroup$ – FranckN Dec 10 '13 at 15:00
  • $\begingroup$ I didn't find a reasoning, so I did it by computer. Still manageable by hand, but not very nice. But have a look at OEIS A224770. It seems to give the possible values of $m$ (not considering the number of prime factors), though I don't know why. $\endgroup$ – Jean-Claude Arbaut Dec 10 '13 at 15:05
  • $\begingroup$ it's supposed to be solvable by hand, so I think it must have certain trick to make it easier $\endgroup$ – FranckN Dec 10 '13 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.