Unveiling The Law Of Quadratic Reciprocity: A Practical Guide

The law of quadratic reciprocity is a theorem in number theory that allows us to determine the solvability of quadratic equations modulo odd prime numbers. It was first proved by Gauss, who referred to it as the fundamental theorem and later the golden theorem. The theorem states that for distinct odd prime numbers p and q, the congruences are both solvable or both unsolvable unless p and q leave a remainder of 3 when divided by 4, in which case one is solvable and the other is not. The law of quadratic reciprocity is useful in computing the Legendre symbol, which helps determine whether congruences of the form x^2 ≡ a (mod p) have a solution.

Legendre symbols and their computation

The Legendre symbol, denoted as (a/p), is a number theoretic function that determines whether a number is a quadratic residue modulo an odd prime. It was introduced by Adrien-Marie Legendre in 1798 in his attempts to prove the law of quadratic reciprocity.

The Legendre symbol is defined as follows:

Definition: Let p be an odd prime and a be an integer. The Legendre symbol of a with respect to p, denoted as (a/p), is defined as:

\[(a/p) = \begin{cases}

1 & \text{ if } a \text{ is a quadratic residue modulo } p \text{ and } a \not\equiv 0\pmod{p} \\

1 & \text{ if } a \text{ is a quadratic non-residue modulo } p \\

0 & \text{ if } a \equiv 0 \pmod{p}

\end{cases}\]

This definition can be used to compute the Legendre symbol for various values of a and p. For example, let's compute (2/7):

We have p = 7, which is an odd prime, and a = 2, an integer.

Since 2 is not a quadratic residue modulo 7 (as there is no number that squares to 2 modulo 7), we get:

\[(2/7) = -1\]

This computation can be extended to larger numbers using the properties of the Legendre symbol. For instance, to compute (12345/331), we can use the property that (ab/p) = (a/p)(b/p):

\[(12345/331) = (3 \cdot 5 \cdot 823/331) = (3/331)(5/331)(823/331)\]

We can further break down each term:

\[(3/331) = (331/3) = -1\]

\[(5/331) = (331/5) = -1\]

\[(823/331) = (7 \cdot 11 \cdot 17 / 331) = (7/331)(11/331)(17/331)\]

Continuing this process and using the properties of the Legendre symbol, we can eventually evaluate each term and multiply them together to get the final value of (12345/331).

Additionally, there are special formulas for small values of a. For example, for an odd prime p ≠ 3, we have:

\[(3/p) = (-1)^{\lfloor (p+1)/6 \rfloor}\]

These formulas can be used as shortcuts for specific cases.

The Legendre symbol is a valuable tool for computations and answering questions related to quadratic residues. It plays a crucial role in the law of quadratic reciprocity, simplifying its notation and making it easier to work with.

Gauss's lemma on quadratic residues

Gauss's lemma in number theory provides a condition for an integer to be a quadratic residue. While it is not useful for computation, it is theoretically significant and is used in some proofs of quadratic reciprocity.

Statement of the Lemma

For any odd prime p, let a be an integer that is coprime to p. Consider the integers:

A, 2a, 3a, ..., (p-1)/2a

And their least positive residues modulo p. These residues are all distinct, so there are (p − 1)/2 of them. Let n be the number of these residues that are greater than p/2. Then:

A/p) = (−1)n

Where (a/p) is the Legendre symbol.

Proof

Let b1, ..., bt be the members of the set less than p/2, and c1, ..., cu be the members greater than p/2. Then u + t = (p-1)/2. Consider the sequence:

0 < b1, ..., bt, p − c1, ..., p − cu < p/2

Each of these is distinct: clearly bi ≠ bj and ci ≠ cj whenever i ≠ j (since q is invertible), and if bi = p − cj, then let bi = rq and cj = sq. Then r + s = 0, which is a contradiction since:

0 < r, s < p / 2

Hence they must be precisely the numbers 1, ..., (p-1)/2 in some order, thus:

Q(2q)...(q(p-1)/2) = b1...btc1...cu = (−1)u b1...bt(p − c1)...(p − cu) = (−1)u ((p-1)/2)!

Dividing both sides by (((p-1)/2))! completes the proof.

Gauss's lemma can be used to prove quadratic reciprocity, which is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers.

Eisenstein's proof of quadratic reciprocity

The proof of the Quadratic Reciprocity Theorem was first proved by Gauss in the early 1800s and was reproved many times thereafter (at least eight times by Gauss). The proof due to the brilliant young mathematician Gotthold Eisenstein, who died at 29 of tuberculosis, is a simplification of Gauss's third proof. Eisenstein's proof is more geometrically intuitive and requires less technical manipulation.

The proof makes use of the following theorem, which is similar to Wilson's Theorem:

Theorem

> If $p$ does not divide $b$ then $(p-1)!\equiv -\legendre{b}{p}b^{(p-1)/2} \pmod p.

The proof of this theorem is as follows:

> Recall that for every $x\in\{1,2,3,\ldots,p-1\}$ there is a unique $y\in\{1,2,3,\ldots,p-1\}$ such that $xy\equiv b$. If $b$ is a quadratic residue then $y$ may be equal to $x$, but if $b$ is a quadratic nonresidue then $y\not=x$.

>

> Suppose that $b$ is a quadratic nonresidue. Then the numbers $1, 2, …, p-1$ can be grouped into $(p-1)/2$ pairs $\{x_i,y_i\}$ with $x_iy_i \equiv b$. Thus $$(p-1)!=\prod_{i=1}^{(p-1)/2}x_iy_i\equiv b^{(p-1)/2} \pmod p.$$ Now suppose that $b$ is a quadratic residue. There are exactly two numbers in $\{1,2,\ldots,p-1\}$, say $c$ and $p-c$, such that $c^2\equiv(p-c)^2\equiv b$. The remaining $p-3$ numbers can be paired up as before. Then $$(p-1)!=c(p-c)\prod_{i=1}^{(p-3)/2}x_iy_i\equiv (pc-c^2)b^{(p-3)/2} \equiv(-b)b^{(p-3)/2}\equiv -b^{(p-1)/2},$$ where all congruences are $(\bmod\; p). This completes the proof. $\qed$

The following corollary is known as Euler's Criterion:

Corollary (Euler's Criterion)

> If $b$ is not divisible by $p$ then $$\legendre{b}{p}\equiv b^{(p-1)/2}\pmod p.$$

The proof of this corollary is as follows:

> Using Wilson's Theorem and the above theorem, $$-1\equiv (p-1)! \equiv -\legendre{b}{p}b^{(p-1)/2},$$ so $$1\equiv \legendre{b}{p}b^{(p-1)/2}.$$ This implies the desired congruence.$\qed$

The proof of the Quadratic Reciprocity Theorem is as follows:

Theorem (Quadratic Reciprocity Theorem)

> If $p$ and $q$ are distinct odd primes, then $$\legendre{p}{q}\legendre{q}{p}=(-1)^{((p-1)/2)((q-1)/2)}.

The proof of this theorem is as follows:

> Let $E=\{2,4,6,\ldots,p-1\}$ and $r_e=eq \bmod p$. We claim that $$\{(-1)^{r_e}r_e \bmod p : e\in E

Proof using quadratic Gauss sums

The proof of Quadratic Reciprocity using Gauss sums is one of the more common and classic proofs. These proofs work by comparing computations of single values in two different ways, one using Euler's Criterion and the other using the Binomial theorem.

First Supplemental Case

By Euler's criterion,

> {\displaystyle \left({\frac {-1}{p}}\right)\equiv (-1)^{\frac {p-1}{2}}{\bmod {p}}}

But since both sides of the equivalence are ±1 and p is odd, we can deduce that

> {\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}}

Second Supplemental Case

Let

> {\displaystyle \zeta _{8}=e^{2\pi i/8}}

Be a primitive 8th root of unity and set

> {\displaystyle \tau =\zeta _{8}+\zeta _{8}^{-1}}

Since

> {\displaystyle \zeta _{8}^{2}=i} and

> {\displaystyle \zeta _{8}^{-2}=-i}

We see that

> {\displaystyle \tau ^{2}=2}

Because

> {\displaystyle \tau }

Is an algebraic integer, if p is an odd prime it makes sense to talk about it modulo p. Using Euler's criterion, it follows that

> {\displaystyle \tau ^{p-1}=(\tau ^{2})^{\frac {p-1}{2}}=2^{\frac {p-1}{2}}\equiv \left({\frac {2}{p}}\right){\pmod {p}}}

We can then say that

> {\displaystyle \tau ^{p}\equiv \left({\frac {2}{p}}\right)\tau {\pmod {p}}}

But we can also compute

> {\displaystyle \tau ^{p}{\pmod {p}}}

Using the binomial theorem. Because the cross terms in the binomial expansion all contain factors of p, we find that

> {\displaystyle \tau ^{p}\equiv \zeta _{8}^{p}+\zeta _{8}^{-p}{\pmod {p}}}

We can evaluate this more exactly by breaking this up into two cases

> {\displaystyle p\equiv \pm 1{\pmod {8}}\Rightarrow \zeta _{8}^{p}+\zeta _{8}^{-p}=\zeta _{8}+\zeta _{8}^{-1}}

> {\displaystyle p\equiv \pm 3{\pmod {8}}\Rightarrow \zeta _{8}^{p}+\zeta _{8}^{-p}=-\zeta _{8}-\zeta _{8}^{-1}}

These are the only options for a prime modulo 8 and both of these cases can be computed using the exponential form

> {\displaystyle \zeta _{8}=e^{\frac {2\pi i}{8}}}

We can write this succinctly for all odd primes p as

> {\displaystyle \tau ^{p}\equiv (-1)^{\frac {p^{2}-1}{8}}\tau {\pmod {p}}}

Combining these two expressions for

> {\displaystyle \tau ^{p}{\pmod {p}}}

And multiplying through by

> {\displaystyle \tau }

We find that

> {\displaystyle 2\cdot \left({\frac {2}{p}}\right)\equiv 2\cdot (-1)^{\frac {p^{2}-1}{8}}{\pmod {p}}}

Since both

> {\displaystyle \left({\frac {2}{p}}\right)}

And

> {\displaystyle (-1)^{\frac {p^{2}-1}{8}}}

Are ±1 and 2 is invertible modulo p, we can conclude that

> {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}}

General Proof

The idea for the general proof follows the above supplemental case: Find an algebraic integer that somehow encodes the Legendre symbols for p, then find a relationship between Legendre symbols by computing the qth power of this algebraic integer modulo q in two different ways, one using Euler's criterion the other using the binomial theorem.

> {\displaystyle g_{p}=\sum _{k=1}^{p-1}\left({\frac {k}{p}}\right)\zeta _{p}^{k}}

Where

> {\displaystyle \zeta _{p}=e^{2\pi i/p}}

Is a primitive pth root of unity. This is a quadratic Gauss sum. A fundamental property of these Gauss sums is that

> {\displaystyle g_{p}^{2}=p^{*}}

Where

> {\displaystyle p^{*}=\left({\frac {-1}{p}}\right)p}

To put this in context of the next proof, the individual elements of the Gauss sum are in the cyclotomic field

> {\displaystyle L=\mathbb {Q} (\zeta _{p})}

But the above formula shows that the sum itself is a generator of the unique quadratic field contained in L. Again, since the quadratic Gauss sum is an algebraic integer, we can use modular arithmetic with it. Using this fundamental formula and Euler's criterion we find that

> {\displaystyle g_{p}^{q-1}=(g_{p}^{2})^{\frac {q-1}{2}}=(p^{*})^{\frac {q-1}{2}}\equiv \left({\frac {p^{*}}{q}}\right){\pmod {q}}}

Therefore

> {\displaystyle g_{p}^{q}\equiv \left({\frac {p^{*}}{q}}\right)g_{p}{\pmod {q}}}

Using the binomial theorem, we also find that

> {\displaystyle g_{p}^{q}\equiv \sum _{k=1}^{p-1}\left({\frac {k}{p}}\right)\zeta _{p}^{qk}{\pmod {q}}}

If we let a be a multiplicative inverse of

> {\displaystyle q{\pmod {p}}}

, then we can rewrite this sum as

> {\displaystyle \left({\frac {a}{p}}\right)\sum _{t=1}^{p-1}\left({\frac {t}{p}}\right)\zeta _{p}^{t}}

Using the substitution

> {\displaystyle t=qk}

, which doesn't affect the range of the sum. Since

> {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {q}{p}}\right)}

, we can then write

> {\displaystyle g_{p}^{q}\equiv \left({\frac {q}{p}}\right)g_{p}{\pmod {q}}}

Using these two expressions for

> {\displaystyle g_{p}^{q}{\pmod {q}}}

, and multiplying through by

> {\displaystyle g_{p}}

Gives

> {\displaystyle \left({\frac {q}{p}}\right)p^{*}\equiv \left({\frac {p^{*}}{q}}\right)p^{*}{\pmod {q}}}

Since

> {\displaystyle p^{*}}

Is invertible modulo q, and the Legendre symbols are either ±1, we can then conclude that

> {\displaystyle \left({\frac {q}{

Proof using algebraic number theory

The proof presented here is by no means the simplest known; however, it is quite a deep one in the sense that it motivates some of the ideas of Artin reciprocity.

Cyclotomic Field Setup

Suppose that p is an odd prime. The action takes place inside the cyclotomic field

L = Q(ζp), where ζp is a primitive pth root of unity. The basic theory of cyclotomic fields informs us that there is a canonical isomorphism

G = Gal (L/Q) ≅ (Z/pZ)×

Which sends the automorphism σa satisfying

Σa(ζp) = ζpa

To the element

A ∈ (Z/pZ)×. In particular, this isomorphism is injective because the multiplicative group of a field is a cyclic group:

F× ≅ Cp−1

Now, consider the subgroup H of squares of elements of G. Since G is cyclic, H has index 2 in G, so the subfield corresponding to H under the Galois correspondence must be a quadratic extension of Q. (In fact, it is the unique quadratic extension of Q contained in L.) The Gaussian period theory determines which one; it turns out to be

Q(√p), where

P = {p if p ≡ 1 (mod 4),

−p if p ≡ 3 (mod 4).

At this point, we start to see a hint of quadratic reciprocity emerging from our framework. On the one hand, the image of H in (Z/pZ)× consists precisely of the (nonzero) quadratic residues modulo p. On the other hand, H is related to an attempt to take the square root of p (or possibly of −p). In other words, if now q is a prime (different from p), we have shown that

Q/p) = 1 ⟺ σq ∈ H ⟺ σq fixes Q(√p).

The Frobenius Automorphism

In the ring of integers

OL = Z[ζp], choose any unramified prime ideal β of lying over q, and let

Φ ∈ Gal (L/Q)

Be the Frobenius automorphism associated with β; the characteristic property of ϕ is that

Φ(x) ≡ xq (mod β) for any x ∈ OL

The existence of such a Frobenius element depends on quite a bit of algebraic number theory machinery.)

The property of ϕ that we need is that for any subfield K of L,

Q splits completely in K ⟺ ϕ fixes K

Indeed, let δ be any ideal of OK below β (and hence above q). Then, since

Φ(x) ≡ xq (mod δ) for any x ∈ OK, we see that

Φ|K ∈ Gal (K/Q)

Is a Frobenius for δ. A standard result concerning ϕ is that its order is equal to the corresponding inertial degree; that is,

Ord(ϕ|K) = [OK/δOK : Z/qZ]

The left-hand side is equal to 1 if and only if ϕ fixes K, and the right-hand side is equal to one if and only if q splits completely in K, so we are done.

Now, since the pth roots of unity are distinct modulo β (i.e., the polynomial Xp − 1 is separable in characteristic q), we must have

Φ(ζp) = ζpq

Φ coincides with the automorphism σq defined earlier. Taking K to be the quadratic field in which we are interested, we obtain the equivalence

Q splits completely in K ⟺ ( q/p) = 1

Completing the Proof

Finally, we must show that

Q splits completely in K ⟺ ( p/q) = 1

Once we have done this, the law of quadratic reciprocity falls out immediately since

• P/q) = ( q/p) if p ≡ 1 (mod 4),
• P/q) = −( q/p) if p ≡ 3 (mod 4).

To show the last equivalence, suppose first that

P/q) = 1

In this case, there is some integer x (not divisible by q) such that

X2 ≡ p (mod q), say

X2 − p = cq for some integer c.

Let

K = Q(√p),

And consider the ideal

X − √p, q) of K. It certainly divides the principal ideal (q). It cannot be equal to (q), since

X − √p

Is not divisible by q. It cannot be the unit ideal, because then

X + √p)(x − √p, q) = (cq, q( x + √p))

Is divisible by q, which is again impossible. Therefore (q) must split in K.

Conversely, suppose that (q) splits, and let β be a prime of K above q. Then

Q) ⊊ β,

So we may choose some

A + b √p ∈ β \ ( q), where a, b ∈ Q.

P ≡ 1 (mod 4), elementary theory of quadratic fields implies that the ring of integers of K is precisely

Z[1 + √p]/2],

So the denominators of a and b are at worst equal to 2. Since q ≠ 2, we may safely multiply a and b by 2, and assume that

A + b √p ∈ β \ ( q), where now a and b are in Z. In this case, we have

A + b √p)(a − b √p) = a2 − b2p ∈ β ∩ Z = ( q)

Q|a2 − b2p

However, q cannot divide b, since then also q divides a, which contradicts our choice of

A + b √p

Therefore, we may divide by b modulo q, to obtain

P ≡ (ab−1)2 (mod q) as desired.

Frequently asked questions