Let \(p\) be an odd prime and \(p\nmid a\) (which implies \(\gcd(a,p)=1\) ). Now we study those special values of \(a\)
for which \(x^2 \equiv a \:\left(\mathrm{mod}\: p \right)\) has a solution, i.e., \(a\) is a square mod \(p\).
If \(x^2 \equiv a \:\left(\mathrm{mod}\: p \right)\) has a solution, \(a\) is called a quadratic residue of \(p\) .
Otherwise \(a\) is called a quadratic nonresidue of \(p\).
Example.
Let us find quadratic residues of the odd prime \(p=7\).
\[\begin{array}{llll}
1^2 &\equiv 6^2 &\equiv 1 &\:\left(\mathrm{mod}\: 7 \right)\\
2^2 &\equiv 5^2 &\equiv 4 &\:\left(\mathrm{mod}\:7 \right)\\
3^2 &\equiv 4^2 &\equiv 2 &\:\left(\mathrm{mod}\:7 \right)
\end{array}\]
So \(x^2 \equiv a \:\left(\mathrm{mod}\: 7 \right)\) has a solution when \(a=1,2,4\) and no solution when \(a=3,5,6\).
Thus quadratic residues of \(p=7\) are \(1,2,4\) and quadratic nonresidues of \(p=7\) are \(3,5,6\).
Observation.
Let \(p\) be an odd prime and \(p\nmid a\). Then \(p\) has exactly \((p-1)/2\) residues and \((p-1)/2\) nonresidues among
\(1,2,\ldots,p-1\). The reason is \(x^2 \equiv a \:\left(\mathrm{mod}\: p\right)\) has either no or two solutions.
Theorem.(Euler's criterion, 1748)
Let \(p\) be an odd prime and \(p\nmid a\). Then \(a\) is a quadratic residue of \(p\) if and only if
\[ a^{\frac{p-1}{2}} \equiv 1 \:\left(\mathrm{mod}\: p \right).\]
Proof.
Suppose \(a\) is a quadratic residue of \(p\). Then \(x_0^2 \equiv a \:\left(\mathrm{mod}\: p \right)\) for some integer
\(x_0\). Since \(p\nmid a\), \(p\nmid x_0\). By FLT \(x_0^{p-1}\equiv 1 \:\left(\mathrm{mod}\: p \right)\). Then
\[ a^{\frac{p-1}{2}}\equiv (x_0^2)^{\frac{p-1}{2}}\equiv x_0^{p-1} \equiv 1 \:\left(\mathrm{mod}\: p \right).\]
Conversely suppose \(a^{\frac{p-1}{2}} \equiv 1 \:\left(\mathrm{mod}\:p \right)\). Since \(p\) is prime, \(p\) has
a primitive root, say \(r\) (why?). Then \(r^{p-1}\equiv 1 \:\left(\mathrm{mod}\: p \right)\) and \(\overline{r}\) is
a generator of \(\mathbb Z_p^*\). Then \(a \equiv r^k \:\left(\mathrm{mod}\: p \right)\) for some positive integer
\(k\leq p-1\). Note that
\[ r^{k\cdot\frac{p-1}{2}}\equiv a^{\frac{p-1}{2}} \equiv 1 \:\left(\mathrm{mod}\: p \right).\]
Since the order of \(r\) is \(p-1\), by a previous proposition, \((p-1)\vert \frac{k(p-1)}{2}\) which implies
\(k=2t\) is an even integer. Then \((r^t)^2 \equiv r^k \equiv a \:\left(\mathrm{mod}\: p \right)\) giving \(r^t\)
as a solution of \(x^2 \equiv a \:\left(\mathrm{mod}\: p \right)\). Thus \(a\) is a quadratic residue of \(p\).
◼
Note that for an odd prime \(p\nmid a\),
\[\left(a^{\frac{p-1}{2}}-1\right) \left(a^{\frac{p-1}{2}}+1\right)\equiv a^{p-1}-1\equiv 0 \:\left(\mathrm{mod}\: p \right).\]
Then either \(p\vert \left(a^{\frac{p-1}{2}}-1\right)\) or \(p\vert \left(a^{\frac{p-1}{2}}+1\right)\). Because if \(p\)
divides both, then \(p\vert 2=(a^{\frac{p-1}{2}}+1)-(a^{\frac{p-1}{2}}-1)\), a contradiction. Thus either
\(a^{\frac{p-1}{2}} \equiv 1 \:\left(\mathrm{mod}\: p \right)\) or \(a^{\frac{p-1}{2}} \equiv -1 \:\left(\mathrm{mod}\:p \right)\).
Corollary.
Let \(p\) be an odd prime and \(p\nmid a\). Then \(a\) is a quadratic nonresidue of \(p\) if and only if
\[ a^{\frac{p-1}{2}} \equiv -1 \:\left(\mathrm{mod}\: p \right).\]
Example.
Let us see whether \(a=4\) is a quadratic residue of \(p=7\). Since
\(4^{\frac{7-1}{2}}\equiv 64 \equiv 1 \:\left(\mathrm{mod}\: 7 \right)\), So \(4\) is a quadratic residue of \(7\).
Similarly for \(a=5\), \(5^{\frac{7-1}{2}}\equiv 125 \equiv 6\equiv -1 \:\left(\mathrm{mod}\: 7 \right)\). So \(5\)
is a quadratic nonresidue of \(7\).