Quadratic residues and non-residues are important concepts in modular arithmetic and number theory. An integer a is called a quadratic residue modulo n if there exists an integer x such that x² ≡ a (mod n). If no such integer exists, a is called a quadratic non-residue modulo n.
For example, consider the modulus 7. Squaring the residue classes 0, 1, 2, 3, 4, 5, and 6 gives residues 0, 1, 4, 2, 2, 4, and 1, respectively. Therefore, the quadratic residues modulo 7 are 0, 1, 2, and 4. The remaining residue classes 3, 5, and 6 are quadratic non-residues.
For an odd prime p, there are exactly (p−1)/2 distinct nonzero quadratic residues modulo p. This happens because the nonzero residue classes x and −x have the same square modulo p. Consequently, the nonzero residues are paired, with each pair producing one quadratic residue.
Quadratic residues are closely connected to the Legendre symbol and Euler's Criterion. These tools help determine whether a congruence has a solution without testing every possible residue class. The study of quadratic residues also leads to the Quadratic Reciprocity Law, which describes a remarkable relationship between the quadratic-residue behavior of two distinct odd primes.
Quadratic Residues and Non-Residues
A quadratic residue modulo an integer is a number congruent to the square of some integer, while a quadratic non-residue is a number that is not congruent to any square under the same modulus.
| Name | Expression | Description |
|---|---|---|
Definition of Quadratic Residue | x² ≡ a (mod n) | An integer a is a quadratic residue modulo n if this congruence has an integer solution x. |
Number of Nonzero Quadratic Residues | (p − 1)/2 | For an odd prime p, exactly half of the nonzero residue classes are distinct quadratic residues. |
Euler's Criterion | a^((p−1)/2) ≡ 1 (mod p) if a is a nonzero quadratic residue; ≡ −1 (mod p) if it is a non-residue | A test for quadratic residues modulo an odd prime p when p does not divide a. |
Legendre Symbol | (a/p) = 1 for a nonzero residue, −1 for a non-residue, and 0 if p | a | Encodes the quadratic-residue classification modulo an odd prime. |
Explanation
Variables
A
The integer being tested for quadratic-residue status.
X
An integer whose square may be congruent to a.
N
The modulus.
P
An odd prime modulus.
P | a
The condition that p divides a.
Example or application
A worked example has not yet been added.
Definition
An integer a is a quadratic residue modulo n if there exists an integer x satisfying x² ≡ a (mod n). Otherwise, a is a quadratic non-residue modulo n.
Purpose
The purpose of studying quadratic residues is to understand which integers can occur as squares modulo a given modulus. This helps solve modular equations, classify residue classes, and investigate deeper relationships between prime numbers.
Importance
Quadratic residues are fundamental to solving congruences involving squares.
They provide the foundation for the Legendre symbol.
Euler's Criterion offers an efficient way to test quadratic residues modulo odd primes.
Their distribution leads to the Quadratic Reciprocity Law.
They are used in algebraic and computational number theory.
They appear in several areas of cryptography and modular algorithms.
Key Concepts
| Name | Description |
|---|---|
Quadratic Residue | An integer congruent to the square of some integer modulo a specified modulus. |
Quadratic Non-Residue | An integer that is not congruent to any square modulo the specified modulus. |
Residue Class | A collection of integers that have the same remainder when divided by a modulus. |
Modular Square | The residue obtained by squaring an integer and reducing the result modulo n. |
Legendre Symbol | A notation used to classify quadratic residues and non-residues modulo an odd prime. |
Characteristics
Quadratic residues depend on the chosen modulus.
Zero is always a quadratic residue because 0² ≡ 0.
For an odd prime p, there are exactly (p−1)/2 distinct nonzero quadratic residues.
Every nonzero quadratic residue modulo an odd prime has exactly two square roots modulo that prime.
The integers x and −x have the same square modulo every modulus.
A quadratic non-residue has no square root in the relevant residue system.
The quadratic-residue structure is particularly simple when the modulus is an odd prime.
Types
| Name | Description |
|---|---|
Zero Quadratic Residue | The residue class 0, which is the square of zero modulo any positive modulus. |
Nonzero Quadratic Residue | A nonzero residue class that is congruent to the square of an integer. |
Quadratic Non-Residue | A residue class that is not congruent to the square of any integer. |
Quadratic Residues Modulo a Prime | The residue classes obtained by squaring integers modulo a prime number. |
Quadratic Residues Modulo a Composite | Residue classes obtained by squaring integers modulo a composite modulus, where the structure can be more complicated. |
Components
| Name | Description |
|---|---|
Modulus | The positive integer n that determines the modular system. |
Candidate Integer | The integer a whose quadratic-residue status is being investigated. |
Square Root | An integer x satisfying x² ≡ a (mod n), if one exists. |
Residue Classes | The possible remainders modulo n. |
Quadratic Classification | The determination of whether a is a residue or non-residue. |
Properties
Zero is a quadratic residue modulo every positive integer.
The square of every integer is a quadratic residue modulo any positive modulus.
If x is a square root of a modulo n, then −x is also a square root.
For an odd prime p, every nonzero quadratic residue has exactly two square roots modulo p.
There are exactly (p−1)/2 distinct nonzero quadratic residues modulo an odd prime p.
The product of two quadratic residues modulo a prime is also a quadratic residue.
The product of a quadratic residue and a non-residue modulo an odd prime is a non-residue.
The product of two quadratic non-residues modulo an odd prime is a quadratic residue.
Quadratic-residue behavior depends on the modulus and cannot be determined from the integer alone.
Examples
| Title | Problem | Solution | Answer |
|---|---|---|---|
Quadratic Residues Modulo 7 | Find all quadratic residues modulo 7. | Square the residue classes: 0² ≡ 0, 1² ≡ 1, 2² ≡ 4, 3² ≡ 2, 4² ≡ 2, 5² ≡ 4, and 6² ≡ 1 (mod 7). The distinct results are 0, 1, 2, and 4. | The quadratic residues modulo 7 are 0, 1, 2, and 4. The non-residues are 3, 5, and 6. |
Testing a Quadratic Residue | Determine whether 9 is a quadratic residue modulo 11. | Since 3² = 9, we have 3² ≡ 9 (mod 11). Therefore, 9 is a quadratic residue modulo 11. | 9 is a quadratic residue modulo 11. |
Testing a Quadratic Non-Residue | Determine whether 2 is a quadratic residue modulo 7. | The quadratic residues modulo 7 are 0, 1, 2, and 4. Since 2 appears in this set, it is actually a quadratic residue. For comparison, 3 is not in the set and is therefore a non-residue. | 2 is a quadratic residue modulo 7, while 3 is a quadratic non-residue. |
Applications
Solving quadratic congruences.
Studying modular square roots.
Applying the Legendre symbol and Euler's Criterion.
Understanding the Quadratic Reciprocity Law.
Analyzing algebraic structures modulo primes.
Developing number-theoretic methods used in cryptography.
Investigating prime residue patterns.
Prerequisites
Modular arithmetic
Congruence relations
Prime numbers
Integer squares
Quadratic equations
Learning Objectives
Define quadratic residues and non-residues.
Generate quadratic residues for a given modulus.
Determine whether a number is a quadratic residue modulo a prime.
Explain why nonzero quadratic residues occur in pairs of square roots.
Calculate the number of distinct nonzero quadratic residues modulo an odd prime.
Apply Euler's Criterion to test quadratic residues.
Connect quadratic residues with the Legendre symbol.
Common Mistakes
Confusing ordinary squares with their residues modulo n.
Assuming that a quadratic residue modulo one number remains a residue under every modulus.
Counting repeated square residues as distinct values.
Forgetting that zero is always a quadratic residue.
Assuming that every nonzero residue class is a quadratic residue.
Applying Euler's Criterion without checking that the modulus is an odd prime.
Confusing a square root modulo n with an ordinary integer square root.
Practice Questions
Find all quadratic residues modulo 5.
Find all quadratic residues modulo 11.
Determine whether 5 is a quadratic residue modulo 13.
Determine whether 6 is a quadratic non-residue modulo 11.
How many distinct nonzero quadratic residues exist modulo 17?
Explain why x and −x produce the same square modulo n.
State Euler's Criterion for quadratic residues.
What is the relationship between quadratic residues and the Legendre symbol?
Key Takeaway
Quadratic residues are the square values that occur in a modular system, while non-residues are the values that cannot be represented as modular squares. Their properties form the foundation of the Legendre symbol and Quadratic Reciprocity Law.
Related Topics
Modular Arithmetic
Congruence Relations
Legendre Symbol
Euler's Criterion
Quadratic Reciprocity Law
Prime Numbers
Modular Square Roots
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