# Find the solutions of $x^2\equiv -1\pmod{5}$ and $x^2\equiv -1\pmod{13}$

Find the solutions of $x^2\equiv -1\pmod{5}$ and $x^2\equiv -1\pmod{13}$

I know that they are both soluble since $5\equiv 1\pmod{4}$ and $13\equiv 1\pmod{4}$

What is the method to solving this simultaneous equation.

Looking for a standard method to use with this type of problem.

• Solve the sub-problems, and combine with the Chinese remainder theorem. – Daniel Fischer Feb 23 '15 at 11:48
• And you can solve the subproblems by seeing whether $1$ is a solution, whether $2$ is a solution, whether $3$ is a solution, and so on. – Gerry Myerson Feb 23 '15 at 12:23
• The Chinese remainder theorem is crucial to this problem and many like it. – Robert Soupe Feb 23 '15 at 14:29

Hint: $x^2 \equiv -1$ mod $5$ $\iff$ $x^2 \equiv 4$ mod $5$ $\iff$ $(x-2)(x+2) \equiv 0$ mod $5$, whence $x \equiv 2$ or $x \equiv -2$ mod $5$.

$x^2 \equiv -1$ mod $13$ $\iff$ $x^2 \equiv 25$ mod $13$ $\iff$ $(x-5)(x+5) \equiv 0$ mod $13$, whence $x \equiv 5$ or $x \equiv -5$ mod $13$.

Now cross-solve these $4$ possibilities with the Chinese Remainder Theorem.

Example: if $x \equiv 2$ mod $5$ and $x \equiv 5$ mod $13$, this should give you $x \equiv 57$ mod $65$

• Why -i is not solution? – Poutrathor Feb 23 '15 at 13:15
• Because this is about integers and not complex numbers, see the tags. – Nicky Hekster Feb 23 '15 at 13:16
• Oooo but could we solve it in C? – Poutrathor Feb 23 '15 at 13:17
• Then one should clarify what you mean by mod $5$ or mod $13$. This can be done, but then we are talking algebraic number theory in $\mathbb{Z}[i]$ which is not elementary number theory as meant by the OP. – Nicky Hekster Feb 23 '15 at 13:20

by Wilson's theorem, for prime $p$: $$(p-1)! \equiv_p -1$$ if $p \equiv_4 1$ then $p-1 = 4n$ and $$(p-1)! = \prod_{k=1}^{2n} k \prod_{k=2n+1}^{4n} k =\prod_{k=1}^{2n} k\prod_{k=1}^{2n}(p- k) \equiv_p (-1)^{2n} \left( \prod_{k=1}^{2n} k \right)^2 = ((2n)!)^2$$ i.e. $$\left( \left(\frac{p-1}2 \right)! \right)^2 \equiv_p -1$$ so $(2!)^2 \equiv_5 -1$ and $(6!)^2 \equiv_{13} -1$, with $6! = 720 \equiv_{13} 720-650-65=5$

since, for any $m$ we have $j^2 \equiv_m (m-j)^2$ the square roots of $-1 \mod 5$ are $2,3$ and the square roots of $-1 \mod 13$ are $5,8$

Hint $\$ By CRT the square roots mod $5$ and $13$ lift to $4$ square roots mod $65$. There is an obvious square root $\,{\rm mod}\ 65\!:\ x^2\equiv -1\equiv 64\,$ if $\,x\equiv \pm8\equiv \pm (2,5)\pmod {5,13}$. The other pair $\pm (-2,5),\,$ arise by multiplying the first pair by $\,(-1,1)\equiv 14,\,$ i.e. $\,\pm 8\cdot 14\equiv \pm18\pmod{65}.\$ QED