<s>[INST] 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.
 [/INST] 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$
</s>