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.
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.
| Name | Expression | Description |
|---|---|---|
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
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
| Name | Description |
|---|---|
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
| Name | Description |
|---|---|
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
| Name | Description |
|---|---|
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
| Title | Problem | Solution | Answer |
|---|---|---|---|
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