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

Question

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.

Answer 1

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$

Answer 2

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$

Answer 3

Hint $\ $ By CRT the square roots mod $5$ and $13$ lift to $4$ square roots mod $65$. There is an obvious 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