Additional Examples of Evaluating Legendre Symbols

We are going to be using the following properties from the Legendre Symbols and Quadratic Reciprocity pages in order to evaluate these Legendre symbols for p being an odd prime, $p \nmid a$, and $p \nmid b$.

• A) The Legendre symbol $(a/p)$ is defined only if p is an odd prime and a is not a multiple of p ($p \nmid a$).

• B) If $a \equiv b \pmod p$, then $(a/p) = (b/p)$.

• C) $(a^2/p) = 1$ since $x^2 \equiv a^2 \pmod p$ has solutions, namely the least residue of a (mod p).

• D) $(ab/p) = (a/p)(b/p)$.

• E) $(-1/p) = 1$ if $p \equiv 1 \pmod 4$.

• F) $(-1/p) = -1$ if $p \equiv 3 \pmod 4$.

• G) $(p/q) = -(q/p)$ if $p \equiv q \equiv 3 \pmod 4$. Otherwise $(p/q) = (q/p)$.

• H) $(2/p) = 1$ if $p \equiv 1 \pmod 8$ or $p \equiv 7 \pmod 8$.

• I) $(2/p) = -1$ if $p \equiv 3 \pmod 8$ or $p \equiv 5 \pmod 8$.

We should now be able to calculate if any quadratic congruence in the form $x^2 \equiv a \pmod p$ has solutions or not by being able to calculate the $(a/p)$.

Example 1

Calculate the Legendre symbol $(1000/11)$.

We know that 11 is an odd prime, and $11 \nmid 1000$, so the Legendre symbol $(1000/11)$ is defined. First, let's break 1000 down into its prime power decomposition. That is, $1000 = 2^3 \cdot 5^3$. Hence it follows that by (D) that:

(1)

\begin{align} \quad \left ( \frac{1000}{11} \right ) = \left ( \frac{2^3}{11} \right ) \left ( \frac{3^3}{11} \right ) = \left ( \frac{2^2}{11} \right )\left ( \frac{2}{11} \right )\left ( \frac{5^2}{11} \right )\left ( \frac{5}{11} \right ) \end{align}

By (C), we know that $\left ( \frac{2^2}{11} \right ) = 1$, and $\left ( \frac{5^2}{11} \right ) = 1$, hence:

(2)

\begin{align} \left ( \frac{1000}{11} \right ) = \left ( \frac{2}{11} \right ) \left ( \frac{5}{11} \right ) \end{align}

By (I), we know that $\left ( \frac{2}{11} \right ) = -1$ since $11 \equiv 3 \pmod 8$:

(3)

\begin{align} \left ( \frac{1000}{11} \right ) = (-1)\left ( \frac{5}{11} \right ) \end{align}

$5 \equiv 1 \pmod 4$, and $11 \equiv 3 \pmod 4$. By (G), we know that $\left ( \frac{5}{11} \right ) = \left ( \frac{11}{5} \right )$, hence:

(4)

\begin{align} \left ( \frac{1000}{11} \right ) = (-1)\left ( \frac{11}{5} \right ) \end{align}

By (B), we can reduce 11. That is $11 \equiv 1 \pmod 5$, so:

(5)

\begin{align} \left ( \frac{1000}{11} \right ) = (-1)\left ( \frac{1}{5} \right ) \end{align}

And by (C), 1 is a square, so $\left ( \frac{1}{5} \right ) = 1$, hence:

(6)

\begin{align} \left ( \frac{1000}{11} \right ) = (-1)(1) \\ \left ( \frac{1000}{11} \right ) = -1 \end{align}

Hence the Legendre symbol $(1000/11) = -1$. Hence the quadratic congruence $x^2 \equiv 1000 \pmod {11}$ has no solutions since 1000 is a quadratic nonresidue (mod 11).

Example 2

Does the quadratic congruence $x^2 \equiv 341 \pmod {17}$ have solutions?

We can determine if this quadratic congruence has solutions by evaluating the Legendre symbol $(341/17)$. By (A), we know this Legendre symbol is defined since 17 is an odd prime and $17 \nmid 341$. For evaluating this Legendre symbol, we are going to first use (B) to reduce 341. Note that we could have used this in example 1 too! $341 \equiv 1 \pmod {17}$. Hence it follows that:

(7)

\begin{align} \left ( \frac{341}{7} \right ) = \left ( \frac{1}{7} \right ) \end{align}

And since 1 is a square, then $\left ( \frac{1}{7} \right ) = 1$. Hence it follows that the Legendre symbol $(341/17) = 1$. So the quadratic congruence $x^2 \equiv 341 \pmod {17}$ has solutions. In fact, we can find them rather easily:

(8)

\begin{align} x^2 \equiv 341 \pmod {17} \\ x^2 \equiv 1 \pmod {17} \\ \end{align}

So x is 1 (mod 17) or -1 (mod 17). -1 is not in least residue, so instead our other solution is 16 (mod 17). Hence our solutions are x = 1 and x = 16.

Example 3

Evaluate the Legendre symbol $(14014/5)$.

We know that this Legendre symbol is defined since 5 is an odd prime and $5 \nmid 14014$. Using property (B), we know that $14014 \equiv 4 \pmod 5$. Hence:

(9)

\begin{align} \left ( \frac{14014}{5} \right ) = \left ( \frac{4}{5} \right ) \end{align}

We know that 4 is a square since $\left ( \frac{4}{5} \right ) = \left ( \frac{2^2}{5} \right )$. Hence $(14014/5) = 1$.

Example 4

Evaluate the Legendre symbol $(342/113)$.

Once again, this Legendre symbol is defined. By property (B), $342 \equiv 3 \pmod {113}$. Hence:

(10)

\begin{align} \left ( \frac{342}{113} \right ) = \left ( \frac{3}{113} \right ) \end{align}

Notice that $3 \equiv 3 \pmod 4$ and $3 \equiv 1 \pmod 4$. Hence by (G):

(11)

\begin{align} \left ( \frac{3}{113} \right ) = \left ( \frac{113}{3} \right ) \end{align}

And reducing 113 (mod 3), we obtain $113 \equiv 2 \pmod 3$, so:

(12)

\begin{align} \left ( \frac{113}{3} \right ) = \left ( \frac{2}{3} \right ) \end{align}

Notice that $3 \equiv 3 \pmod 8$, so by (I),$\left ( \frac{2}{3} \right ) = -1$, and hence the Legendre symbol $(342/113) = -1$.

Example 5

Suppose that g and h are primitive roots of p. Is it possible that gh is a primitive root of p?

We first note that if g and h are primitive roots of p, then $(g/p) = -1$, and $(h/p) = -1$ since primitive roots of quadratic non-residues. By property (D), it thus follows that $(gh/p) = (g/p)(h/p) = (-1)(-1) = 1$. Hence gh is NOT a primitive root of p. Hence if g and h are primitive roots of p, then gh is NOT a primitive root of p.

Example 6

Suppose that 2 and 3 are primitive roots of p. Is it possible that 6 is a primitive root of p?

We note that this question is almost identical to example 5. First, we note that if 2 is a primitive root of p, then it follows that $(2/p) = -1$ and $(3/p) = -1$. Hence $(6/p) = (2/p)(3/p) = (-1)(-1) = 1$, so 6 is NOT a primitive root of p.

Example 7

Using Euler's Criterion for quadratic residues and Legendre symbols, determine if 2, 3, or 5 are primitive roots of 5639.

We first note that the possible orders of 5369 are divisors of 5368. The divisors of 5368 are 1, 2, 2819, 5638. We note that the orders of 2, 3, 5, and 7 will not be 1 or 2. We can thus check to see if the orders of 2, 3, 5 or 7 are 2819.

Now we know that from Euler's Criterion that $a^{2819} \equiv \left ( \frac{a}{5369} \right ) \pmod {5369}$. Given that, we can evaluate the Legendre symbols $(2/5369), (3/5369), (5/5369), (7/5369)$.

The Legendre symbol $(2/5369) = 1$ since $5369 \equiv 1 \pmod 8$. Hence 2 is NOT a primitive root of 5369, since 2 has order 2819.

The Legendre symbol $(3/5369) = (5369/3) = (2/3) = -1$. Hence 3 IS a primitive root of 5369, since 3 has order 2819.

The Legendre symbol $(5/5369) = (5369/5) = (4/5) = 1$. Hence 5 is NOT a primitive root of 5369, since 5 has order 2819.