Properties of Legendre's Symbol

Supposing that $p$ and $q$ are odd primes, and $a$ and $b$ are integers not divisible by $p$, the following properties for the Legendre Symbol hold. The first five are easy to prove (in most cases, by appealing to Euler's Criterion), the sixth is an immediate consequence of a lemma by Gauss, and the last is one of the most famous and intriguing results of number theory, the Law of Quadratic Reciprocity (also due to the work of Gauss).

  1. If $a \equiv b \pmod{p}$, then $\displaystyle{\left( \frac{a}{p} \right) = \left( \frac{b}{p} \right)}$

  2. $\displaystyle{\left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p} \right)}$

  3. $\displaystyle{\left( \frac{a^2}{p} \right) = 1}$

  4. $\displaystyle{\left( \frac{1}{p} \right) = 1}$

  5. $\displaystyle{\left( \frac{-1}{p} \right) = \left\{ \begin{array}{cl} 1 & \textrm{ if } p \equiv 1\pmod{4}\\ -1 & \textrm{ if } p \equiv -1\pmod{4} \end{array} \right. }$

  6. $\displaystyle{\left( \frac{2}{p} \right) = (-1)^{\frac{p^2 -1}{8}}}$

  7. $\displaystyle{\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}}$     (The Law of Quadratic Reciprocity)

Taken together, these properties allow for quick computation of $\displaystyle{\left( \frac{a}{p} \right)}$, even for large values of $a$ and $p$.

For example, suppose we wished to calculate $\displaystyle{\left( \frac{713}{1009} \right)}$.

Upon noticing $1009$ is prime and $713 = 23 \times 31$, we immediately have from property (2) above:

$$\left( \frac{713}{1009} \right) = \left( \frac{23}{1009} \right) \left( \frac{31}{1009} \right)$$

Let us deal with these two factors separately. As explanation of each calculation below, the number of the property applied appears over the corresponding equals sign. As can be seen, applying these properties properly reduces quite quickly the magnitudes of the numbers involved, until the evaluation of the Legendre symbol becomes trivial.

$\displaystyle{\begin{array}{rcl} \left( \frac{23}{1009} \right) &\overset{7}{=}& \left( \frac{1009}{23} \right)\\ &\overset{1}{=}& \left( \frac{20}{23} \right)\\ &\overset{2}{=}& \left( \frac{2^2}{23} \right) \left( \frac{5}{23} \right)\\ &\overset{3}{=}& \left( \frac{5}{23} \right)\\ &\overset{7}{=}& \left( \frac{23}{5} \right)\\ &\overset{1}{=}& \left( \frac{3}{5} \right)\\ &\overset{7}{=}& \left( \frac{5}{3} \right)\\ &\overset{1}{=}& \left( \frac{2}{3} \right)\\ &\overset{6}{=}& -1 \end{array}}$
$\displaystyle{\begin{array}{rcl} \left( \frac{31}{1009} \right) &\overset{7}{=}& \left( \frac{1009}{31} \right)\\ &\overset{1}{=}& \left( \frac{17}{31} \right)\\ &\overset{7}{=}& \left( \frac{31}{17} \right)\\ &\overset{1}{=}& \left( \frac{14}{17} \right)\\ &\overset{2}{=}& \left( \frac{2}{17} \right) \left( \frac{7}{17} \right)\\ &\overset{6}{=}& \left( \frac{7}{17} \right)\\ &\overset{7}{=}& \left( \frac{17}{7} \right)\\ &\overset{1}{=}& \left( \frac{3}{7} \right)\\ &\overset{7}{=}& -\left( \frac{7}{3} \right)\\ &\overset{1}{=}& -\left( \frac{1}{3} \right)\\ &\overset{4}{=}& -1\\ \end{array}}$

But then, $\displaystyle{\left( \frac{23}{1009} \right) \left( \frac{31}{1009} \right) = (-1)(-1) = 1}$.

As such, we may conclude any of the following three equivalent statements: