Legendre Symbol

Given an odd prime \( p \) and an integer \( a \), the Legendre symbol \(\left(\frac{a}{p}\right)\) is defined as follows: \[ \left(\frac{a}{p}\right) = \begin{cases} \phantom{-}1 & \text{if \( a \) is a quadratic residue modulo \( p \)} \\ -1 & \text{if \( a \) is not a quadratic residue modulo \( p \)} \\ \phantom{-}0 & \text{if } p \text{ divides } a \end{cases} \]

The Legendre symbol is a mathematical function that tells us whether an integer \( a \) is a quadratic residue modulo \( p \). It takes the value 1, -1, or 0, depending on the situation.

What is a quadratic residue?

An integer \( a \) is a quadratic residue if there exists an integer \( x \) such that: \[ x^2 \equiv a \pmod{p} \] In other words, \( a \) is a quadratic residue if it is the square of some integer modulo \( p \). Otherwise, if no such \( x \) exists, \( a \) is not a quadratic residue.

It's important to note that the Legendre symbol is only defined when the modulus is a prime number.

If the modulus is composite, we use the Jacobi symbol instead.

Note: The Legendre symbol is commonly used in primality tests, such as the Solovay-Strassen test, and in cryptographic applications, particularly in algorithms involving quadratic residues. It also plays a role in verifying Euler pseudoprimes.

Example Calculation

Let's compute the following Legendre symbol:

$$ \left(\frac{4}{7}\right) $$

Since \( 4 = 2^2 \) is a perfect square, we can find an integer \( x = 2 \) such that \( x^2 \equiv 4 \pmod{7} \).

Thus, the Legendre symbol evaluates to 1:

\[ \left(\frac{4}{7}\right) = 1 \]

Example 2

Now, let's consider another case:

$$ \left(\frac{3}{7}\right) $$

We need to check if there exists an integer \( x \) such that \( x^2 \equiv 3 \pmod{7} \).

By listing the quadratic residues modulo \( 7 \):

• \( 0^2 = 0 \equiv 0 \pmod{7} \)
• \( 1^2 = 1 \equiv 1 \pmod{7} \)
• \( 2^2 = 4 \equiv 4 \pmod{7} \)
• \( 3^2 = 9 \equiv 2 \pmod{7} \)
• \( 4^2 = 16 \equiv 2 \pmod{7} \)
• \( 5^2 = 25 \equiv 4 \pmod{7} \)
• \( 6^2 = 36 \equiv 1 \pmod{7} \)

None of these are congruent to \( 3 \), so \( 3 \) is not a quadratic residue modulo \( 7 \).

Thus, the Legendre symbol evaluates to -1:

\[ \left(\frac{3}{7}\right) = -1 \]

Example 3

Now, let's examine one final case:

$$ \left(\frac{7}{7}\right) $$

Since \( 7 \) is divisible by itself (\( 7 \equiv 0 \pmod{7} \)), the Legendre symbol evaluates to zero:

\[ \left(\frac{7}{7}\right) = 0 \]

Note: Listing out quadratic residues like this is an intuitive way to understand the concept, but it quickly becomes impractical for large primes. In such cases, Euler’s criterion provides a more efficient method for computing the Legendre symbol.

Euler’s Criterion

This formula allows us to determine whether an integer \( a \) is a quadratic residue modulo \( p \) without explicitly computing all quadratic residues.

Example 1

Let's determine whether \( a = 4 \) is a quadratic residue modulo \( p = 7 \).

$$ \left(\frac{4}{7}\right) $$

We use Euler’s criterion to find out:

\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]

Substituting \( a = 4 \) and \( p = 7 \), we get:

\[ \left(\frac{4}{7}\right) \equiv 4^{\frac{7-1}{2}} \pmod{7} \]

\[ \left(\frac{4}{7}\right) \equiv 4^3 \pmod{7} \]

\[ \left(\frac{4}{7}\right) \equiv 64 \pmod{7} \]

\[ \left(\frac{4}{7}\right) \equiv 1 \pmod{7} \]

Since the result is 1, we conclude that 4 is a quadratic residue modulo 7.

Example 2

Now, let's check whether \( a = 3 \) is a quadratic residue modulo \( p = 7 \).

$$ \left(\frac{3}{7}\right) $$

Applying Euler’s criterion again:

\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]

\[ \left(\frac{3}{7}\right) \equiv 3^3 \pmod{7} \]

\[ \left(\frac{3}{7}\right) \equiv 27 \pmod{7} \]

\[ \left(\frac{3}{7}\right) \equiv 6 \pmod{7} \]

Since 6 is congruent to -1 modulo 7, we get:

\[ \left(\frac{3}{7}\right) \equiv -1 \pmod{7} \]

Therefore, the Legendre symbol is -1, meaning that 3 is not a quadratic residue modulo 7.

Properties of the Legendre Symbol

The Legendre symbol satisfies several key properties:

• Multiplicativity
  If \( a \) and \( b \) are integers, the Legendre symbol is multiplicative with respect to the numerator: \[ \left(\frac{a b}{p}\right) = \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right) \]

  Example: Suppose we need to compute \( \left(\frac{6}{7}\right) \). We can break it down as: \[ \left(\frac{6}{7}\right) = \left(\frac{2}{7}\right) \cdot \left(\frac{3}{7}\right) \] This approach is useful when we already know the values of individual Legendre symbols or when using quadratic reciprocity to simplify calculations.

• Quadratic Reciprocity
  One of the most powerful tools for computing the Legendre symbol without manually listing all quadratic residues is the quadratic reciprocity law. It states that if \( p \) and \( q \) are distinct odd primes, then: \[  \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}} \cdot \left(\frac{p}{q}\right) \]

  Example: Let's compute \( \left(\frac{3}{11}\right) \), which would otherwise require checking all quadratic residues modulo 11. Instead, we use quadratic reciprocity. Swapping the numerator and denominator, we get: \[ \left(\frac{3}{11}\right) = (-1)^{\frac{(11-1)(3-1)}{4}} \cdot \left(\frac{11}{3}\right) \] Simplifying the exponent: \[ \left(\frac{3}{11}\right) = (-1)^5 \cdot \left(\frac{11}{3}\right) \] \[ \left(\frac{3}{11}\right) = (-1) \cdot \left(\frac{11}{3}\right) \] Since \( 11 \equiv 2 \pmod{3} \), we substitute \( \left(\frac{11}{3}\right) \) with \( \left(\frac{2}{3}\right) \): \[ \left(\frac{3}{11}\right) = (-1) \cdot \left(\frac{2}{3}\right) \] Knowing that \( 2 \equiv -1 \pmod{3} \), we replace \( \left(\frac{2}{3}\right) \) with -1: \[ \left(\frac{3}{11}\right) = (-1) \times (-1) = 1 \] So \( 3 \) is a quadratic residue modulo 11. We can verify this by checking that \( 5^2 \equiv 3 \pmod{11} \): \[ 5^2 = 25 \equiv 3 \pmod{11} \] This example highlights how quadratic reciprocity allows us to compute the Legendre symbol efficiently, avoiding the need to list all quadratic residues.

• Notable Values
  By definition, we set $$ \left( \frac{0}{p} \right) = 0 $$ $$ \left( \frac{1}{p} \right) = 1 $$

And so on.