Quadratic Residues

Quadratic Residues

Quadratic residues are integers that are perfect squares modulo a given modulus. The study of quadratic residues is central to number theory and has applications in cryptography, primality testing, and the theory of quadratic forms.

The crown jewel of this theory is the Law of Quadratic Reciprocity, which Gauss called the golden theorem and proved multiple times using different methods.

Definition

Let p be an odd prime and a an integer not divisible by p. Then a is a quadratic residue modulo p if the congruence x2≡a*mod(p) has a solution.

If no such solution exists, a is called a quadratic nonresidue modulo p.

Example

Modulo 7, the squares are 1=1, 2=4, 3=2, 4=2, 5=4, 6=1.

So the quadratic residues mod 7 are {1,2,4} and the nonresidues are {3,5,6}.

The Legendre Symbol

The Legendre symbol (a/p) encodes whether a is a quadratic residue modulo the odd prime p:

(a/p)={[1,if *a* is a QR mod *p],[−1,if *a* is a QNR mod *p],[0,if *p|a])

Eulers Criterion

The Legendre symbol can be computed using Eulers criterion:

(a/p)≡a((p−1)/2)*(mod(p))

This follows from Fermat's little theorem: a(p−1)≡1, so a((p−1)/2)≡±1.

Properties of the Legendre Symbol

The Legendre symbol is multiplicative:

((a*b)/p)=(a/p)*(b/p)

This makes it a completely multiplicative function of a.

Special Values

When is -1 a Quadratic Residue?

((−1)/p)=(−1)((p−1)/2)={[1,if *p≡1*(mod(4))],[−1,if *p≡3*(mod(4))])

So -1 is a quadratic residue mod p if and only if p is congruent to 1 mod 4.

When is 2 a Quadratic Residue?

(2/p)=(−1)((p2−1)/8)={[1,if *p≡±1*(mod(8))],[−1,if *p≡±3*(mod(8))])

So 2 is a quadratic residue mod p if and only if p is congruent to plus or minus 1 mod 8.

The Law of Quadratic Reciprocity

Let p and q be distinct odd primes. Then:

(p/q)*(q/p)=(−1)((p−1)/2⋅(q−1)/2)

Equivalently, (p/q)=(q/p) unless both p and q are congruent to 3*mod(4), in which case (p/q)=−(q/p).

This remarkable theorem allows us to compute Legendre symbols efficiently by reducing large numbers modulo small primes.

The Jacobi Symbol

The Jacobi symbol generalizes the Legendre symbol to composite odd moduli. For n=(p_1)(a_1)*(p_2)(a_2)⋯ (odd), define:

(a/n)=(a/(p_1))(a_1)*(a/(p_2))(a_2)⋯

The Jacobi symbol retains the multiplicativity and reciprocity properties, making it useful for computation even when we do not know the factorization of n.

Counting Quadratic Residues

Among the integers 1,2,…,p−1, exactly (p−1)/2 are quadratic residues and (p−1)/2 are nonresidues.

This follows because the squaring map x↦x2 is two-to-one on the nonzero elements: x and −x have the same square.

Applications

Primality Testing

The Solovay-Strassen primality test uses the Jacobi symbol and Euler's criterion. If n is prime, then the Jacobi symbol (a/n) equals a((n−1)/2)*mod(n) for all a. Composites usually fail this test.

Cryptography

Quadratic residuosity is the basis for several cryptographic systems. The Goldwasser-Micali cryptosystem uses the difficulty of distinguishing quadratic residues from nonresidues modulo a composite.

Solving Quadratic Congruences

To solve x2≡a*(mod(p)) when a is a quadratic residue, the Tonelli–Shanks algorithm efficiently finds square roots modulo primes.

Gaussian Periods and Gauss Sums

Gauss sums are exponential sums that encode information about quadratic residues:

g=(∑_a=0^p−1)(a/p)*e(2*π*i*a/p)

Gauss showed that g2=((−1)/p)*p. These sums are fundamental in algebraic number theory and the proof of quadratic reciprocity.

Historical Note

Euler and Legendre studied quadratic residues and conjectured the reciprocity law. Gauss provided the first complete proof in 1796 at age 18, later giving seven more proofs using different methods.

Quadratic reciprocity inspired the search for higher reciprocity laws, leading to class field theory and modern algebraic number theory.

Algorithm for Computing Legendre Symbol

To compute (a/p) efficiently:

Reduce a modulo p.

Factor out powers of 2 and use the formula for (2/p).

For odd factors, use quadratic reciprocity to swap the arguments.

Reduce the arguments and repeat until the result is determined.

This is similar to the Euclidean algorithm and runs in polynomial time.

Distribution of Quadratic Residues

Quadratic residues are not randomly distributed. Consecutive quadratic residues and nonresidues exhibit patterns studied by number theorists.

The least quadratic nonresidue modulo p is expected to be O*((log_)(p)) for most primes, though proving good bounds unconditionally remains difficult.

Quadratic residues form a fundamental concept connecting number theory, algebra, and cryptography, with the Law of Quadratic Reciprocity standing as one of the most beautiful theorems in mathematics.

Quadratic Character

The Legendre symbol defines a group homomorphism from the multiplicative group of integers mod p to {−1,1}. This is the unique quadratic character modulo p, a concept generalized by Dirichlet characters in analytic number theory.