For an odd prime \(p\), the Legendre symbol \(\displaystyle\left(\frac{a}{p}\right)\)
(read as "\(a\) on \(p\)") is defined by
\[ \displaystyle\left(\frac{a}{p}\right)=
\left\lbrace
\begin{array}{rl} 0 & \text{ if } p \vert a \\
1 & \text{ if } a \text{ is a quadratic residue mod } p \\
-1 & \text{ if } a \text{ is a quadratic nonresidue mod } p. \end{array} \right.\]
Note that the number of solutions of \(x^2 \equiv a \:\left(\mathrm{mod}\: p \right)\) is \(1+\displaystyle\left(\frac{a}{p}\right)\).
Example.
Since quadratic residues of \(p=7\) are \(1,2,4\) and quadratic nonresidues of \(p=7\) are \(3,5,6\). We have
\[\displaystyle\left(\frac{0}{7}\right)=0,\; \displaystyle\left(\frac{1}{7}\right)=1,\; \displaystyle\left(\frac{2}{7}\right)=1,\;
\displaystyle\left(\frac{3}{7}\right)=-1,\;
\displaystyle\left(\frac{4}{7}\right)=1,\;\displaystyle\left(\frac{5}{7}\right)=-1,\;\displaystyle\left(\frac{6}{7}\right)=-1,\;
\displaystyle\left(\frac{7}{7}\right)=0.\]
Now we restate Euler's criterion using the Legendre symbol:
Theorem.(Euler's criterion)
Let \(p\) be an odd prime and \(a\) an integer not divisible by \(p\). Then
\[\displaystyle\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \:\left(\mathrm{mod}\:p \right).\]
Example.
By Euler's criterion, \(\displaystyle\left(\frac{-1}{p}\right) \equiv (-1)^{\frac{p-1}{2}} \:\left(\mathrm{mod}\:p\right)\).
Since both \(\displaystyle\left(\frac{-1}{p}\right)\) and \((-1)^{\frac{p-1}{2}}\) are \(1\) or \(-1\),
\(\displaystyle\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}\) for any odd prime \(p\).
Corollary.
Let \(p\) be an odd prime. The following hold for any given integers \(a\) and \(b\).
\(\displaystyle\left(\frac{a^2}{p}\right) =1\) if \(p\nmid a\) and \(0\) otherwise. In particular
\(\displaystyle\left(\frac{1}{p}\right) =1\).
If \(a\equiv b \:\left(\mathrm{mod}\:p\right)\), then \(\displaystyle\left(\frac{a}{p}\right)=\displaystyle\left(\frac{b}{p}\right)\).
\(\displaystyle\left(\frac{ab}{p}\right)=\displaystyle\left(\frac{a}{p}\right)\displaystyle\left(\frac{b}{p}\right)\), i.e.,
the Legendre symbol is a completely multiplicative function on the numerator.
Proof.
If \(p\nmid a\), then \(x^2 \equiv a^2 \:\left(\mathrm{mod}\:p\right)\) has solutions \(\pm a\). Thus
\(\displaystyle\left(\frac{a^2}{p}\right) =1\).
If \(a\equiv b \:\left(\mathrm{mod}\:p\right)\), then \(x^2 \equiv a \:\left(\mathrm{mod}\:p\right)\) has a solution
if and only if \(x^2 \equiv b \:\left(\mathrm{mod}\:p\right)\) has a solution. Thus \(\displaystyle\left(\frac{a}{p}\right)=\displaystyle\left(\frac{b}{p}\right)\).
If \(p\vert a\) or \(p\vert b\), then \(p\vert ab\) and consequently \(\displaystyle\left(\frac{ab}{p}\right)=0=\displaystyle\left(\frac{a}{p}\right)\displaystyle\left(\frac{b}{p}\right)\).
Suppose \(p\nmid a\) and \(p\nmid b\). By the Euler's criterion,
\[\displaystyle\left(\frac{ab}{p}\right) \equiv (ab)^{\frac{p-1}{2}} \equiv a^{\frac{p-1}{2}} b^{\frac{p-1}{2}} \equiv \displaystyle\left(\frac{a}{p}\right)\displaystyle\left(\frac{b}{p}\right) \:\left(\mathrm{mod}\:p\right).\]
Note that each of \(\displaystyle\left(\frac{ab}{p}\right)\) and \(\displaystyle\left(\frac{a}{p}\right)\displaystyle\left(\frac{b}{p}\right)\) is \(1\) or \(-1\).
If \(\displaystyle\left(\frac{ab}{p}\right)\neq \displaystyle\left(\frac{a}{p}\right)\displaystyle\left(\frac{b}{p}\right)\),
then we get \(1\equiv -1 \:\left(\mathrm{mod}\:p\right)\) or \(-1\equiv 1 \:\left(\mathrm{mod}\:p\right)\) implying
\(2\equiv 0 \:\left(\mathrm{mod}\:p\right)\), a contradiction to the fact \(p>2\).
◼
Example.
Let us compute \(\displaystyle\left(\frac{150}{7}\right)\) by the above properties.
\[\displaystyle\left(\frac{150}{7}\right)=\displaystyle\left(\frac{2\cdot 3\cdot 5^2}{7}\right)
=\displaystyle\left(\frac{2}{7}\right)\displaystyle\left(\frac{3}{7}\right)\displaystyle\left(\frac{5^2}{7}\right)
=\displaystyle\left(\frac{2}{7}\right)\displaystyle\left(\frac{3}{7}\right)\cdot 1.\]
By the Euler's criterion, \(\displaystyle\left(\frac{2}{7}\right)\equiv 8\equiv 1 \:\left(\mathrm{mod}\:7\right)\) and
\(\displaystyle\left(\frac{3}{7}\right) \equiv 3^{\frac{7-1}{2}} \equiv 27\equiv -1 \:\left(\mathrm{mod}\:7\right)\).
So \(\displaystyle\left(\frac{2}{7}\right)=1\) and \(\displaystyle\left(\frac{3}{7}\right)=-1\). Thus
\(\displaystyle\left(\frac{150}{7}\right)=-1\) and \(x^2 \equiv 150 \:\left(\mathrm{mod}\:7\right)\) has no solution.
Alternatively, using \(150\equiv 3 \:\left(\mathrm{mod}\:7\right)\), we get \(\displaystyle\left(\frac{150}{7}\right)=
\displaystyle\left(\frac{3}{7}\right)=-1\).