= Square root of minus one modulo a prime
{title2=$x^2\equiv-1\pmod p$}
The <quadratic congruence> $x^2\equiv-1\pmod p$ is soluble exactly when $p=2$ or $p\equiv1\pmod4$. At $p=2$, take $x=1$.
For an <odd prime> $p$, any solution is nonzero modulo $p$. <Fermat's little theorem> gives
$$
1\equiv x^{p-1}\equiv(-1)^{(p-1)/2}\pmod p,
$$
so $(p-1)/2$ is even and $p\equiv1\pmod4$. Conversely, put $m=(p-1)/2$ when $p\equiv1\pmod4$. Pairing opposite factors in the factorial gives
$$
(p-1)!\equiv(-1)^m(m!)^2=(m!)^2\pmod p.
$$
<Wilson's theorem> therefore gives $(m!)^2\equiv-1\pmod p$, constructing a solution. For example, at $p=13$ the construction gives $6!\equiv5\pmod{13}$ and $5^2\equiv-1\pmod{13}$. The criterion is the <first supplementary law for quadratic reciprocity> expressed as existence of a square root.
Back to article page