Quadratic Reciprocity

Here are two questions that seem unrelated: is $13$ a square mod $47$? Is $47$ a square mod $13$? Gauss proved, as a teenager, that the answers are linked by a simple sign rule. He called it the golden theorem and gave several different proofs of it. With it and the supplementary laws, any Legendre symbol shrinks quickly, much like the Euclidean algorithm.

The law of quadratic reciprocity. For distinct odd primes $p$ and $q$, $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}.$$ In words: $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$, unless $p \equiv q \equiv 3 \pmod{4}$, in which case $\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$.

Por qué funciona

The exponent $\frac{p-1}{2} \cdot \frac{q-1}{2}$ is odd only when both factors are odd, that is, when $p \equiv q \equiv 3 \pmod{4}$; that is where the minus sign comes from. The proof is beyond this lesson (one classical proof counts the lattice points under the diagonal of a $\frac{p}{2} \times \frac{q}{2}$ rectangle in two ways), but its power is easy to see: after flipping, the top number can be reduced mod the new bottom, so the numbers keep getting smaller until the supplementary laws or $\left(\frac{1}{q}\right) = 1$ finish the job.

Reduce the top mod the bottom.
Factor the top. Drop squared factors; handle $-1$ and $2$ with the supplementary laws.
For each odd prime on top, flip with reciprocity (minus sign if both are $3 \bmod 4$), and repeat.

Ejemplo resuelto: One flip

Find $\left(\frac{13}{47}\right)$.

$13 \equiv 1 \pmod{4}$, so no sign: $\left(\frac{13}{47}\right) = \left(\frac{47}{13}\right)$.
$47 \equiv 8 \pmod{13}$: $\left(\frac{8}{13}\right) = \left(\frac{2}{13}\right)^{3} = \left(\frac{2}{13}\right)$.
$13 \equiv 5 \pmod{8}$, so $\left(\frac{2}{13}\right) = -1$.

Respuesta: $\left(\frac{13}{47}\right) = -1$: 13 is not a square mod 47.

Ejemplo resuelto: Watch the sign

Find $\left(\frac{19}{43}\right)$.

$19 \equiv 43 \equiv 3 \pmod{4}$, so $\left(\frac{19}{43}\right) = -\left(\frac{43}{19}\right) = -\left(\frac{5}{19}\right)$.
$5 \equiv 1 \pmod{4}$: $\left(\frac{5}{19}\right) = \left(\frac{19}{5}\right) = \left(\frac{4}{5}\right) = 1$, since 4 is a square.
So $\left(\frac{19}{43}\right) = -1$.

Respuesta: $-1$.

Ejemplo resuelto: A composite top

Find $\left(\frac{12}{31}\right)$.

Factor first: $\left(\frac{12}{31}\right) = \left(\frac{2}{31}\right)^{2}\left(\frac{3}{31}\right) = \left(\frac{3}{31}\right)$.
$3 \equiv 31 \equiv 3 \pmod{4}$: $\left(\frac{3}{31}\right) = -\left(\frac{31}{3}\right) = -\left(\frac{1}{3}\right) = -1$.

Respuesta: $-1$.

Error común

Flipping a symbol whose top is not an odd prime. "$\left(\frac{15}{17}\right) = \left(\frac{17}{15}\right) = \left(\frac{2}{15}\right)$, and 2 is not a square mod 15, so the answer is $-1$" is wrong: 15 is not prime, so the law does not apply to it, and the true value is $\left(\frac{3}{17}\right)\left(\frac{5}{17}\right) = (-1)(-1) = 1$. Factor the top into primes first. And when both primes are $3 \bmod 4$, do not forget the minus sign.

Reciprocity also answers "for which primes $p$ is 3 a square?" in one stroke: $\left(\frac{3}{p}\right) = 1$ exactly when $p \equiv \pm 1 \pmod{12}$. (Try $p = 11$: $5^{2} = 25 \equiv 3$.) A version for composite bottoms, the Jacobi symbol, is left for a later course.

Idea clave

For distinct odd primes, $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$ unless both are $3 \bmod 4$, when there is a minus sign. Reduce, factor, flip, repeat.

Práctica

Se apoya en

Lleva a

Fuentes y lecturas