What is Quadratic Reciprocity?

Quadratic reciprocity is a fundamental and elegant theorem in number theory that describes the relationship between quadratic residues of different prime numbers. It provides a powerful shortcut for determining whether an integer is a perfect square modulo a prime number, without having to check every possible square. This theorem simplifies calculations involving modular arithmetic and is a cornerstone of advanced number theory.

Legendre Symbol (a/p)

The Legendre Symbol is a notation used to express whether an integer 'a' is a quadratic residue modulo a prime 'p'. It is defined as:

(a/p) = {

1 if 'a' is a quadratic residue modulo 'p' (meaning x² ≡ a (mod p) has a solution and p does not divide a).
-1 if 'a' is a quadratic non-residue modulo 'p' (meaning x² ≡ a (mod p) has no solution).
0 if 'p' divides 'a' (meaning a ≡ 0 (mod p)).

Law of Quadratic Reciprocity

For distinct odd primes 'p' and 'q', the law states:

(p/q)(q/p) = (-1)^((p-1)/2 * (q-1)/2)

This formula tells us how the Legendre symbol (p/q) relates to (q/p). Specifically:

If at least one of 'p' or 'q' is of the form 4k + 1, then (p/q) = (q/p). This means if 'p' is a quadratic residue modulo 'q', then 'q' is a quadratic residue modulo 'p', and vice versa.
If both 'p' and 'q' are of the form 4k + 3, then (p/q) = -(q/p). This means if 'p' is a quadratic residue modulo 'q', then 'q' is a quadratic non-residue modulo 'p', and vice versa.

This "reciprocity" between primes is what makes the theorem so remarkable and useful.

Key Concepts in Quadratic Reciprocity

Quadratic Residues: An integer 'a' is a quadratic residue modulo 'p' if it is congruent to a perfect square modulo 'p'. In simpler terms, if you can find an integer 'x' such that x² leaves the same remainder as 'a' when divided by 'p', then 'a' is a quadratic residue. For example, modulo 5, 1 and 4 are quadratic residues because 1² ≡ 1 (mod 5) and 2² ≡ 4 (mod 5).
Quadratic Non-Residues: Conversely, an integer 'a' is a quadratic non-residue modulo 'p' if there is no integer 'x' such that x² ≡ a (mod p). For example, modulo 5, 2 and 3 are quadratic non-residues.
Euler's Criterion: This criterion provides an alternative way to calculate the Legendre symbol (a/p) without checking all squares. It states that for an odd prime 'p' and an integer 'a' not divisible by 'p', a^((p-1)/2) ≡ (a/p) (mod p). This means if a^((p-1)/2) ≡ 1 (mod p), then 'a' is a quadratic residue; if a^((p-1)/2) ≡ -1 (mod p), then 'a' is a quadratic non-residue.
Supplementary Laws: The main law of quadratic reciprocity applies to two distinct odd primes. However, there are special "supplementary laws" for the cases involving the prime 2 and the integer -1.
- First Supplementary Law (for -1): (-1/p) = (-1)^((p-1)/2). This means -1 is a quadratic residue modulo 'p' if 'p' is of the form 4k + 1, and a quadratic non-residue if 'p' is of the form 4k + 3.
- Second Supplementary Law (for 2): (2/p) = (-1)^((p²-1)/8). This means 2 is a quadratic residue modulo 'p' if 'p' is of the form 8k ± 1, and a quadratic non-residue if 'p' is of the form 8k ± 3.
Chinese Remainder Theorem: While not directly part of quadratic reciprocity, the Chinese Remainder Theorem (CRT) is often used in conjunction with it. CRT helps solve systems of congruences, allowing us to combine information about quadratic residues modulo different primes to find solutions modulo their product.
Jacobi Symbol: The Jacobi symbol is a generalization of the Legendre symbol where the "denominator" can be any positive odd integer (not necessarily prime). It follows similar multiplication rules to the Legendre symbol and is very useful for calculations, even though it doesn't directly tell us if 'a' is a quadratic residue modulo a composite number.
Kronecker Symbol: This is a further generalization of the Jacobi symbol, extending its definition to include cases where the "denominator" is an even number or even zero, and the "numerator" can be any integer. It plays a role in more advanced number theory, particularly in algebraic number theory and the theory of quadratic forms.

Advanced Topics and Generalizations

The concept of quadratic reciprocity extends into more complex areas of number theory and has inspired significant mathematical developments.

Higher Reciprocity Laws

Beyond quadratic reciprocity, mathematicians have developed "higher reciprocity laws" for powers greater than 2. These include cubic reciprocity (for cubes) and biquadratic (or quartic) reciprocity (for fourth powers). These laws are significantly more complex and require working with numbers in extensions of the integers, such as Gaussian integers or Eisenstein integers.

Artin Reciprocity Law

The Artin Reciprocity Law is a vast generalization of all classical reciprocity laws, including quadratic, cubic, and biquadratic reciprocity. It is a central theorem in Class Field Theory, a major branch of algebraic number theory. It connects the arithmetic properties of number fields (extensions of rational numbers) to their Galois groups, providing a deep link between number theory and abstract algebra.

Gauss Sums

Gauss sums are specific sums of roots of unity that arise in number theory and harmonic analysis. They are intimately connected to quadratic reciprocity and provide a powerful tool for proving the law. The properties of Gauss sums are studied in character theory, which deals with representations of finite groups.

Applications in Cryptography and Coding Theory

Quadratic residues and the principles of quadratic reciprocity have practical applications in modern cryptography and coding theory. They are used in the design of public-key cryptosystems (like the Rabin cryptosystem), primality testing algorithms (like the Solovay-Strassen test), and error-correcting codes, which are essential for secure communication and reliable data transmission.

Historical Context of Quadratic Reciprocity

The Law of Quadratic Reciprocity has a rich history, with its discovery and proof spanning several centuries and involving some of the greatest mathematicians.

Euler's Observations (1744): Leonhard Euler, a prolific Swiss mathematician, was one of the first to observe the patterns that would later become the Law of Quadratic Reciprocity. He made conjectures about the conditions under which a prime 'p' would be a quadratic residue modulo another prime 'q', but he could not provide a complete proof.
Legendre's Conjecture (1785): Adrien-Marie Legendre, a French mathematician, independently formulated the full statement of the theorem and attempted a proof. He introduced the Legendre symbol notation, which is still used today. However, his proof had a gap, as it assumed the existence of certain primes, which was not proven at the time.
Gauss's Eight Proofs (1796 onwards): Carl Friedrich Gauss, often called the "Prince of Mathematicians," provided the first complete and rigorous proof of the Law of Quadratic Reciprocity in 1796, at the age of 19. He considered it his "golden theorem" and went on to publish eight different proofs throughout his lifetime, each offering new insights and using different mathematical techniques. His work solidified the theorem's place as a cornerstone of number theory.
Modern Developments: Since Gauss, many other mathematicians have provided alternative proofs and generalizations of the theorem, further demonstrating its depth and importance. These proofs often utilize diverse areas of mathematics, including algebraic number theory, complex analysis, and group theory.
Impact on Number Theory: The Law of Quadratic Reciprocity was a pivotal discovery that opened up new avenues of research in number theory. It led to the development of class field theory and inspired the search for higher reciprocity laws, profoundly shaping the direction of modern number theory and its applications.

Quadratic Reciprocity Calculator

Understanding Quadratic Reciprocity