Prove that a squared number is an equivalence relation of $-1\pmod{p}$ [duplicate]

Prove that a squared number is an equivalence relation of $-1\pmod{p}$.

Lets assume that $p$ is a prime number which satisfies:

$$p \,\equiv\, 1 \pmod{4}.$$

How can one find a natural number $n$, which yields:

$$n^2 \,\equiv\, -1 \pmod{p}\;?$$

Solution 1:

First find a small non-residue, call it $c.$ When $p \equiv 5 \pmod 8$ we may choose $c=2.$ When $p \equiv 2 \pmod 3$ we may choose $c=3.$ Otherwise, one may just check small numbers in order, checking $(c|p)$ by quadratic reciprocity until we find $(c|p) = -1.$ Tests have been done on this, the first non-residue $c$ is typically tiny.

Then find $$ n \equiv c^{\frac{p-1}{4} } \pmod p . $$ When $p$ is large, we use the powermod algorithm. The result is that $$ x^2 \equiv -1 \pmod p $$

first non-residue for small primes $1 \pmod 4$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

    5    2
   13    2
   17    3
   29    2
   37    2
   41    3
   53    2
   61    2
   73    5
   89    3
   97    5
  101    2
  109    2
  113    3
  137    3
  149    2
  157    2
  173    2
  181    2
  193    5
  197    2
  229    2
  233    3
  241    7

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=