Safekipedia
Algebraic number theoryModular arithmeticQuadratic residueTheorems in number theory

Quadratic reciprocity

Adapted from Wikipedia · Discoverer experience

A page from Gauss's Disquisitiones Arithmeticae showing mathematical formulas about quadratic reciprocity.

In number theory, the law of quadratic reciprocity is a fascinating theorem that helps us solve quadratic equations when working with prime numbers. It tells us how to determine whether a number can be a perfect square modulo another number. This idea might sound complicated, but it’s like a special rule that makes solving these kinds of problems much easier.

Gauss published the first and second proofs of the law of quadratic reciprocity on arts 125–146 and 262 of Disquisitiones Arithmeticae in 1801.

The law was first clearly stated by mathematicians Leonhard Euler and Adrien-Marie Legendre, and later proven by Carl Friedrich Gauss, who called it the "fundamental theorem" and even the "golden theorem" in private notes. Gauss was so excited about this theorem that he found six different ways to prove it, and even after he passed away, two more proofs were discovered in his papers!

Quadratic reciprocity is not just a curious math trick; it has had a huge impact on many areas of modern mathematics. It helped shape the development of modern algebra, algebraic geometry, and even led to big ideas like class field theory and the Langlands program. Today, there are over 240 known proofs of this theorem, showing just how important and interesting it is to mathematicians around the world.

Motivating examples

Quadratic reciprocity helps us understand patterns in numbers that are perfect squares modulo certain primes. Let’s look at some examples.

Consider the expression ( n^2 - 5 ). When we look at the prime factors of this expression for different values of ( n ), we notice something interesting: certain primes, like those ending in 1 or 9, appear, while others, like those ending in 3 or 7, do not. This pattern helps us understand when a number like 5 can be written as a square modulo a prime ( p ).

Quadratic residues are numbers that can be written as a square modulo a prime. For example, modulo 5, the numbers 1 and 4 are quadratic residues because they are squares of 1 and 2, respectively. The study of these residues shows patterns that are useful in number theory. For instance, the product of two quadratic residues is also a residue, while the product of a residue and a non-residue is a non-residue. These patterns help mathematicians solve complex problems involving primes and squares.

n⁠ f ( n ) {\displaystyle f(n)} ⁠       ⁠ f ( n ) {\displaystyle f(n)} ⁠       n
1−4−22162512513195622⋅239
2−1−11728422⋅713210191019
34221831911⋅2933108422⋅271
411111935622⋅893411511151
52022⋅5203955⋅7935122022⋅5⋅61
631312143622⋅1093612911291
74422⋅112247947937136422⋅11⋅31
859592352422⋅1313814391439
97622⋅192457157139151622⋅379
10955⋅192562022⋅5⋅314015955⋅11⋅29
1111622⋅292667111⋅6141167622⋅419
121391392772422⋅1814217591759
1316422⋅412877919⋅4143184422⋅461
141911912983622⋅11⋅194419311931
1522022⋅5⋅11308955⋅17945202022⋅5⋅101
Squares mod primes
n12345678910111213141516171819202122232425
n2149162536496481100121144169196225256289324361400441484529576625
mod 31101101101101101101101101
mod 51441014410144101441014410
mod 71422410142241014224101422
mod 111495335941014953359410149
mod 13149312101012394101493121010123941
mod 171491682151313152816941014916821513
mod 19149166171175571117616941014916617
mod 23149162133181286681218313216941014
mod 2914916257206231352824222224285132362072516
mod 31149162551821972820141088101420287192185
mod 3714916253612277261033211133430282830343112133
mod 411491625368234018392153220102373331313337210
mod 431491625366213814351540241041312317131111131723
mod 47149162536217346273288372174232241814121214
q
357111317192329313741434753596167717379838997
p3 NRNRNRNNRRNRNNNRRNRRNNR
5N NRNNRNRRNRNNNRRNRNRNRN
7NN RNNNRRNRNRNRNNRRNRNNN
11RRN NNNRNRRNNRRRNRRNNNRR
13RNNN RNRRNNNRNRNRNNNRNNN
17NNNNR RNNNNNRRRRNRNNNRRN
19NRRRNR RNNNNRRNNRNNRNRNN
23RNNNRNN RRNRNRNRNNRRNNNN
29NRRNRNNR NNNNNRRNRRNNRNN
31NRRNNNRNN NRNRNRNRRNNNNR
37RNRRNNNNNN RNRRNNRRRNRNN
41NRNNNNNRNRR RNNRRNNRNRNN
43NNNRRRNRNRNR RRRNRNNRRNR
47RNRNNRNNNNRNN RRRNRNRRRR
53NNRRRRNNRNRNRR RNNNNNNRR
59RRRNNRRNRNNRNNR NNRNRNNN
61RRNNRNRNNNNRNRNN NNRNRNR
67NNNNNRRRRNRNNRNRN RRNRRN
71RRNNNNRNRNRNRNNNNN RRRRN
73RNNNNNRRNNRRNNNNRRR RNRR
79NRNRRNRRNRNNNNNNNRNR RRR
83RNRRNRNRRRRRNNNRRNNNN NN
89NRNRNRNNNNNNNRRNNRRRRN R
97RNNRNNNNNRNNRRRNRNNRRNR 
q
837971675947433123191173513172937415361738997
p83 NNNRNNRRNRRRNNRRRRNRNNN
79R NRNNNRRRRNNRRNNNNNNRRR
71RR NNNRNNRNNRRNNRRNNNRRN
67RNR RRNNRRNNNNNRRRNNNRRN
59NRRN NNNNRNRRRNRRNRRNNNN
47RRRNR NNNNNRRNNRNRNRRNRR
43RRNRRR RRNRNNNRRNNRRNNNR
31NNRRRRN NRNRNRNNNNRNNNNR
23NNRNRRNR NNNRNRNRNRNNRNN
19RNNNNRRNR RRNRNRNNNNRRNN
11NNRRRRNRRN NRRNNNRNRNNRR
7NRRRNNRNRNR NNNNRRNRNNNN
3NRNRNNRRNRNR NRNNRNNRRNR
5NRRNRNNRNRRNN NNRNRNRNRN
13NRNNNNRNRNNNRN RRNNRRNNN
17RNNRRRRNNRNNNNR NNNRNNRN
29RNRRRNNNRNNRNRRN NNRNNNN
37RNRRNRNNNNRRRNNNN RRNRNN
41RNNNRNRRRNNNNRNNNR NRRNN
53NNNNRRRNNNRRNNRRRRN NNRR
61RNNNNRNNNRNNRRRNNNRN RNR
73NRRRNNNNRRNNRNNNNRRNR RR
89NRRRNRNNNNRNNRNRNNNRNR R
97NRNNNRRRNNRNRNNNNNNRRRR 

Supplements to quadratic reciprocity

The supplements to quadratic reciprocity help solve specific cases of the main theorem more easily. They give simple rules for when certain numbers can be perfect squares modulo a prime number.

One important supplement deals with -1. It shows that -1 is a perfect square modulo a prime p if and only if p is congruent to 1 modulo 4. Another supplement deals with 2, showing that 2 is a perfect square modulo a prime p if and only if p is congruent to ±1 modulo 8. These supplements make it easier to work with quadratic equations in modular arithmetic without needing the full theorem.

Statement of the theorem

Quadratic reciprocity is a big idea in math that helps us figure out when certain equations have solutions. It tells us about solving equations like (x^2 \equiv a \pmod{p}), where we want to know if there’s a whole number (x) that makes the equation true when we work with remainders after dividing by a prime number (p).

The theorem gives us special rules. For example, if we have two special numbers (p) and (q), and both follow certain patterns when divided by 4, we can swap them in the equation and still know if a solution exists. This helps mathematicians understand these kinds of problems better, even though it doesn’t tell us how to find the actual solutions.

Proof

Main article: Proofs of quadratic reciprocity

Quadratic reciprocity is a big idea in math that helps us understand patterns with numbers. One important part of this is figuring out whether certain equations have solutions. For example, we might want to know if there's a number that, when squared, gives another specific number when we think about these numbers only up to a certain point (called a modulus).

There are many ways to prove quadratic reciprocity, and new proofs are still being found. These proofs help us understand deep connections between numbers and solve problems that seem hard at first glance.

History and alternative statements

The law of quadratic reciprocity is a big idea in number theory. It helps us figure out when certain equations have solutions with whole numbers. This law was understood in different ways by many mathematicians over time.

Part of Article 131 in the first edition (1801) of the Disquisitiones, listing the 8 cases of quadratic reciprocity

Fermat, an early mathematician, looked at expressing prime numbers using simple equations. Euler and Lagrange worked on similar ideas but didn’t fully state the law of quadratic reciprocity. Later, Legendre introduced a special symbol to make these ideas easier to work with. Gauss, another famous mathematician, gave us the modern form of the law.

Today, we use these ideas to solve problems about whether a number can be written as a square of another number, but only in special cases involving prime numbers. This law remains important in deeper areas of mathematics.

Main article: Legendre symbol

TheoremWhenit follows that
Ib a − 1 2 ≡ 1 ( mod a ) {\displaystyle b^{\frac {a-1}{2}}\equiv 1{\pmod {a}}} a b − 1 2 ≡ 1 ( mod b ) {\displaystyle a^{\frac {b-1}{2}}\equiv 1{\pmod {b}}}
IIa b − 1 2 ≡ − 1 ( mod b ) {\displaystyle a^{\frac {b-1}{2}}\equiv -1{\pmod {b}}} b a − 1 2 ≡ − 1 ( mod a ) {\displaystyle b^{\frac {a-1}{2}}\equiv -1{\pmod {a}}}
IIIa A − 1 2 ≡ 1 ( mod A ) {\displaystyle a^{\frac {A-1}{2}}\equiv 1{\pmod {A}}} A a − 1 2 ≡ 1 ( mod a ) {\displaystyle A^{\frac {a-1}{2}}\equiv 1{\pmod {a}}}
IVa A − 1 2 ≡ − 1 ( mod A ) {\displaystyle a^{\frac {A-1}{2}}\equiv -1{\pmod {A}}} A a − 1 2 ≡ − 1 ( mod a ) {\displaystyle A^{\frac {a-1}{2}}\equiv -1{\pmod {a}}}
Va b − 1 2 ≡ 1 ( mod b ) {\displaystyle a^{\frac {b-1}{2}}\equiv 1{\pmod {b}}} b a − 1 2 ≡ 1 ( mod a ) {\displaystyle b^{\frac {a-1}{2}}\equiv 1{\pmod {a}}}
VIb a − 1 2 ≡ − 1 ( mod a ) {\displaystyle b^{\frac {a-1}{2}}\equiv -1{\pmod {a}}} a b − 1 2 ≡ − 1 ( mod b ) {\displaystyle a^{\frac {b-1}{2}}\equiv -1{\pmod {b}}}
VIIb B − 1 2 ≡ 1 ( mod B ) {\displaystyle b^{\frac {B-1}{2}}\equiv 1{\pmod {B}}} B b − 1 2 ≡ − 1 ( mod b ) {\displaystyle B^{\frac {b-1}{2}}\equiv -1{\pmod {b}}}
VIIIb B − 1 2 ≡ − 1 ( mod B ) {\displaystyle b^{\frac {B-1}{2}}\equiv -1{\pmod {B}}} B b − 1 2 ≡ 1 ( mod b ) {\displaystyle B^{\frac {b-1}{2}}\equiv 1{\pmod {b}}}
CaseIfThen
1)±a R a′±a′ R a
2)±a N a′±a′ N a
3)+a R b
−a N b		±b R a
4)+a N b
−a R b		±b N a
5)±b R a+a R b
−a N b
6)±b N a+a N b
−a R b
7)+b R b′
−b N b′		−b′ N b
+b′ R b
8)−b N b′
+b R b′		+b′ R b
−b′ N b
CaseIfThen
9)±a R A±A R a
10)±b R A+A R b
−A N b
11)+a R B±B R a
12)−a R B±B N a
13)+b R B−B N b
+N R b
14)−b R B+B R b
−B N b

Connection with cyclotomic fields

Early proofs of quadratic reciprocity were hard to understand. Things changed when Gauss showed that certain number patterns, called quadratic fields, are part of bigger patterns known as cyclotomic fields. This helped explain quadratic reciprocity better.

Later, a mathematician named Robert Langlands suggested a big idea called the Langlands program. It aims to extend our understanding even further. Langlands himself said he didn’t find quadratic reciprocity interesting at first, but later saw its importance.

Other rings

There are quadratic reciprocity laws that work in structures other than the regular whole numbers. These help us understand patterns in more complex mathematical systems.

Gaussian integers

Carl Friedrich Gauss discovered a version of quadratic reciprocity for Gaussian integers, which are numbers of the form a + b_i, where i is the square root of -1. This work was part of his studies on quartic reciprocity, though he didn’t fully prove it himself. Later mathematicians built on his ideas to show how these patterns connect to the usual whole numbers.

Eisenstein integers

Eisenstein integers are another special set of numbers, involving a special kind of cube root of unity. Similar reciprocity laws apply here, helping us understand how these numbers behave in modular arithmetic.

Imaginary quadratic fields

More general versions of quadratic reciprocity exist for imaginary quadratic fields — these are number systems built around solutions to equations like _x² + y² = 1. These laws help us understand properties of these more complex number systems.

Polynomials over a finite field

Quadratic reciprocity also applies to polynomials over finite fields — sets with a limited number of elements. This helps us study patterns in polynomial equations within these constrained systems.

Higher powers

Further information: Cubic reciprocity, Quartic reciprocity, Octic reciprocity, and Eisenstein reciprocity

Mathematicians in the 1800s tried to expand the ideas of quadratic reciprocity to work with numbers raised to higher powers than just two. This led them to study more complex number systems.

One of the big unsolved problems in math, posed in 1900, was to find a general rule for these higher powers. Later, a mathematician named Emil Artin found a broad theorem called Artin reciprocity that includes all earlier rules as special cases.

This article is a child-friendly adaptation of the Wikipedia article on Quadratic reciprocity, available under CC BY-SA 4.0.

Images from Wikimedia Commons. Tap any image to view credits and license.