Defintion
\(a\) is a quadratic residue modulo \(m\) if $$ \begin{align} x^2 \equiv a \pmod{m} \end{align} $$

Examples

Note that when \(m = 5\), \(0, 1\) and \(4\) are quadratic residues modulo \(5\) since

$$ \begin{align} 0 &\equiv 0^2 \pmod{5} \\ 1 &\equiv 1^2 \pmod{5} \\ 4 &\equiv 2^2 \pmod{5} \end{align} $$

When \(m = 8\), \(0, 1\) and \(4\) are the only quadratic residues modulo \(8\).

If we continue to do more examples, we will notice that when \(p\) is prime, we will get special properties. Assuming that \(\gcd(p,a) = 1\) and \(p \nmid a\), then we will have the following theorem:

Theorem
The number \(a\) is a quadratic residue modulo \(p\) if and only if $$ \begin{align} a^{\frac{p-1}{2}} \equiv 1 \pmod{p} \end{align} $$

Note here that although \(a = 0\) is a quadratic residue modulo \(p\) by definition, this theorem fails for \(a = 0\). Hence, we must assume that \(\gcd(a,p) = 1\) or \(p \nmid a\).

Proof

\(\Rightarrow\): Let \(p\) be an odd prime such that \(p \nmid a\). Suppose \(a\) is a quadratic residue modulo \(p\). Let \(x\) be any integer such that

$$ \begin{align} x^2 \equiv a \pmod{p} \quad \quad \quad (1) \end{align} $$

By assumption, we know that \(p \nmid a\). We claim that \(p \nmid x\). To see this, suppose for the sake of contradiction that \(p \mid x\). Then \(x \equiv 0 \pmod{p}\) which implies that

$$ \begin{align} x^2 \equiv 0 \pmod{p} \end{align} $$

But we know that \(x^2 \equiv a \pmod{p}\). This would mean that

$$ \begin{align} a \equiv 0 \pmod{p} \end{align} $$

i.e. \(p \mid a\). This is a contradiction since we assumed that \(p \nmid a\). Hence, we must have that \(p \nmid x\) and so \(\gcd(p,x) = 1\). Thus, by Fermat’s Little Theorem

$$ \begin{align} x^{p-1} \equiv 1 \pmod{p} \quad \quad \quad (2) \end{align} $$

Now, raise \((1)\) to the power \((p-1)/2\) to see that

$$ \begin{align} (x^2)^{\frac{p-1}{2}} &\equiv a^{\frac{p-1}{2}} \pmod{p} \\ x^{p-1} &\equiv a^{\frac{p-1}{2}} \pmod{p} \quad \quad \quad (3) \end{align} $$

Finally, combine (2) and (3) to get

$$ \begin{align} a^{\frac{p-1}{2}} &\equiv 1 \pmod{p} \end{align} $$

\(\Leftarrow\): Now suppose that

$$ \begin{align} a^{\frac{p-1}{2}} &\equiv 1 \pmod{p} \end{align} $$

TODO …

\(\ \blacksquare\).

References

  • Number Theory by Georege Andrews