Solving Congruency Using Quadratic Reciprocity

Question

Use quadratic reciprocity to show that if p is an odd prime different from 5, then 5 is a quadratic residue (mod p) if and only if p $\equiv\pm$ 1 (mod 5).

Answer 1

Applying the Quadratic Reciprocity law in your example we know that for $5$ to be a quadratic residue $\mod p$ and $p\ne 5$ the following conditions must satisfy:

The legendre symbol $(\frac{p}{5})$ and $(\frac{5}{p})$ are both equal, which means that 5 is a quadratic residue modulo every odd prime which is a residue modulo 5.

Example, let $p=31$ and $q=5$

$(\frac{p}{q}) = p^{\frac{q-1}{2}} \pmod q$ then $1\equiv 31^{2} \pmod 5$

$(\frac{q}{p}) = q^{\frac{p-1}{2}} \pmod p$ then $1\equiv 5^{15} \pmod{31}$

Also notice that $(\frac{p}{q})$ and $(\frac{r}{q})$ will be equal with $r$ being $p = kq+r$ such that $r= 0 \leq r < p$

Answer 2

By the Law of Quadratic Reciprocity, $(5/p) = (p/5)$ since $5$ is a prime of the form $4k + 1$. Use the division algorithm to write $p = 5q + r$, so $p \equiv r \pmod{5}$. Then, $(p/5) = (r/5)$. By trying each of $1 \leq r \leq 4$ (since $r$ must be a residue modulo $5$, and $r \neq 0$ since $p$ is not a multiple of $5$ by the assumption that $p \neq 5$), we find that only $r = 1,4$ are quadratic residues. Thus, $(p/5) = 1$ if and only if $r = 1,4$ if and only if $p \equiv 1,4 \equiv \pm 1 \pmod{5}$.