✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-098

Legendre Symbol

The Legendre symbol is a mathematical notation used in number theory to determine whether an integer is a quadratic residue modulo an odd prime. It takes one of three values: 1, −1, or 0.

NameExpressionDescription

Legendre Symbol Definition

(a/p) = 1 if a is a nonzero quadratic residue modulo p; −1 if it is a non-residue; 0 if p | a

Defines the three possible values of the Legendre symbol.

Multiplicative Property

(ab/p) = (a/p)(b/p)

The Legendre symbol is multiplicative in its numerator.

Euler's Criterion

a^((p−1)/2) ≡ (a/p) (mod p), when p does not divide a

Calculates the Legendre symbol through modular exponentiation.

Value for −1

(−1/p) = (−1)^((p−1)/2)

Determines whether −1 is a quadratic residue modulo an odd prime.

Explanation

The Legendre symbol is an important tool in the study of quadratic residues and modular arithmetic. For an odd prime p and an integer a, the Legendre symbol is written as (a/p). Its value indicates whether the congruence x² ≡ a (mod p) has a solution.

If a is not divisible by p and is a quadratic residue modulo p, then (a/p) = 1. If a is not divisible by p and is a quadratic non-residue modulo p, then (a/p) = −1. If p divides a, then (a/p) = 0.

For example, modulo 7, the nonzero quadratic residues are 1, 2, and 4 because they are obtained by squaring the nonzero residue classes. Therefore, (2/7) = 1, while (3/7) = −1 and (7/7) = 0.

The Legendre symbol has several useful properties. It is multiplicative in its numerator, meaning that (ab/p) = (a/p)(b/p). Euler's Criterion provides a way to calculate the symbol using modular exponentiation: for p not dividing a, (a/p) is congruent to a^((p−1)/2) modulo p, with the result interpreted as 1 or −1. The Legendre symbol is also central to the Quadratic Reciprocity Law, one of the most important theorems in elementary number theory.

Variables

A

An integer whose quadratic-residue status is being tested.

P

An odd prime number.

X

An integer used in the congruence x² ≡ a (mod p).

(a/p)

The Legendre symbol of a modulo p.

P | a

The statement that p divides a.

Example or application

A worked example has not yet been added.

Definition

For an odd prime p and an integer a, the Legendre symbol (a/p) equals 1 if a is a nonzero quadratic residue modulo p, −1 if a is a quadratic non-residue modulo p, and 0 if p divides a.

Purpose

The purpose of the Legendre symbol is to represent quadratic-residue information compactly and provide algebraic rules for investigating whether congruences of the form x² ≡ a (mod p) have solutions.

Importance

  • It provides a compact notation for quadratic-residue classification.

  • It helps determine whether a congruence has a square root modulo an odd prime.

  • It is multiplicative in its numerator.

  • Euler's Criterion provides an efficient way to calculate its value.

  • It is essential to the Quadratic Reciprocity Law.

  • It is used in advanced modular arithmetic and number theory.

Key Concepts

NameDescription

Quadratic Residue

An integer congruent to a square modulo a given modulus.

Quadratic Non-Residue

An integer that is not congruent to any square modulo the given modulus.

Legendre Symbol

A notation indicating whether an integer is a quadratic residue, non-residue, or divisible by an odd prime.

Odd Prime Modulus

The prime p used as the modulus, with p greater than 2.

Euler's Criterion

A theorem that determines the Legendre symbol through exponentiation modulo p.

Characteristics

  • The Legendre symbol is defined for an odd prime denominator.

  • Its possible values are −1, 0, and 1.

  • It is zero exactly when the prime denominator divides the numerator.

  • It is multiplicative in the numerator.

  • Euler's Criterion can be used to evaluate it.

  • It is closely connected to the classification of nonzero quadratic residues.

  • It is a central tool in the proof and application of quadratic reciprocity.

Types

NameDescription

Positive Legendre Symbol

The value 1 indicates that the numerator is a nonzero quadratic residue modulo the prime.

Negative Legendre Symbol

The value −1 indicates that the numerator is a quadratic non-residue modulo the prime.

Zero Legendre Symbol

The value 0 indicates that the numerator is divisible by the prime.

Components

NameDescription

Numerator

The integer a whose quadratic-residue status is being investigated.

Prime Denominator

The odd prime p that serves as the modulus.

Residue Classification

The determination of whether a is a quadratic residue or non-residue modulo p.

Symbol Value

The value 1, −1, or 0 assigned according to the classification.

Properties

  • The Legendre symbol takes only the values −1, 0, and 1.

  • (a/p) = 0 if and only if p divides a.

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

  • (a²/p) = 1 whenever p does not divide a.

  • (1/p) = 1 for every odd prime p.

  • (−1/p) = 1 when p ≡ 1 (mod 4), and −1 when p ≡ 3 (mod 4).

  • Euler's Criterion provides a method for calculating the symbol.

  • For a nonzero quadratic residue modulo p, there are exactly two square roots modulo p when p is odd.

Examples

TitleProblemSolutionAnswer

Legendre Symbol of a Quadratic Residue

Evaluate (2/7).

The nonzero squares modulo 7 are 1² ≡ 1, 2² ≡ 4, 3² ≡ 2, 4² ≡ 2, 5² ≡ 4, and 6² ≡ 1. Since 2 occurs among the quadratic residues and 7 does not divide 2, the symbol equals 1.

(2/7) = 1.

Legendre Symbol of a Non-Residue

Evaluate (3/7).

The nonzero quadratic residues modulo 7 are 1, 2, and 4. Since 3 does not appear in this set and 7 does not divide 3, it is a quadratic non-residue.

(3/7) = −1.

Using Euler's Criterion

Evaluate (2/7) using Euler's Criterion.

Euler's Criterion gives 2^((7−1)/2) = 2³ = 8 ≡ 1 (mod 7). Therefore, the Legendre symbol is 1.

(2/7) = 1.

Applications

  • Testing whether modular square roots exist.

  • Studying quadratic residues and non-residues.

  • Applying Euler's Criterion.

  • Proving and applying quadratic reciprocity.

  • Solving congruences involving squares.

  • Studying advanced properties of prime moduli.

Prerequisites

  • Prime numbers

  • Modular arithmetic

  • Congruence relations

  • Quadratic residues

  • Euler's Criterion

Learning Objectives

  • Define the Legendre symbol.

  • Identify the three possible values of the symbol.

  • Determine whether an integer is a quadratic residue modulo an odd prime.

  • Apply the multiplicative property of the Legendre symbol.

  • Use Euler's Criterion to calculate Legendre symbols.

  • Explain the relationship between the Legendre symbol and quadratic reciprocity.

Common Mistakes

  • Using the Legendre symbol with a composite denominator while treating it as an ordinary Legendre symbol.

  • Confusing a quadratic residue with a primitive root.

  • Assigning −1 when the numerator is divisible by the prime.

  • Forgetting that the denominator must be an odd prime.

  • Applying Euler's Criterion without checking whether p divides a.

  • Assuming every nonzero residue class is a quadratic residue.

Practice Questions

  • Evaluate (1/11), (2/11), and (3/11).

  • Find the value of (5/13).

  • Use Euler's Criterion to evaluate (3/7).

  • State the multiplicative property of the Legendre symbol.

  • Determine the value of (−1/13).

  • Explain the difference between a quadratic residue and a quadratic non-residue.

  • Why must the denominator of a Legendre symbol be an odd prime?

Key Takeaway

The Legendre symbol compresses the question of whether an integer is a quadratic residue modulo an odd prime into one of three values. Its multiplicative property and connection to Euler's Criterion make it a central tool in quadratic number theory.

Related Topics

  • Quadratic Residues

  • Quadratic Non-Residues

  • Euler's Criterion

  • Quadratic Reciprocity Law

  • Modular Arithmetic

  • Prime Numbers

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.

Suggest a correction or source · More in Arithmetic & Number Theory