Back to the on-screen lesson ·
The law relating the two symbols of a pair of odd primes, the supplements it needs, and the Euclid-like algorithm it gives.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state quadratic reciprocity and say exactly when flipping a symbol changes its sign, apply the two supplements for minus one and for two, evaluate any Legendre symbol by reducing, factorising and flipping until the numerator is one, and use the law to express the set of primes for which a fixed number is a square as a congruence condition.
Lesson 18 gave two things: Euler's criterion, which evaluates $\left(\frac{a}{p}\right)$ by one exponentiation, and multiplicativity, which reduces any symbol to symbols with prime numerators.
So the outstanding question is how to evaluate $\left(\frac{q}{p}\right)$ for two odd primes. The criterion answers it by computing; this lesson answers it by turning the symbol upside down, which makes the numbers smaller and lets the process repeat — exactly the shape of Euclid's algorithm, and for the same reason it terminates.
Quadratic reciprocity is the law relating $\left(\frac{p}{q}\right)$ and $\left(\frac{q}{p}\right)$ for distinct odd primes. Reciprocity means the relation runs both ways: neither symbol is determined, only their product.
The supplements cover the numerators the law cannot take: $-1$, decided by $p$ modulo $4$, and $2$, decided by $p$ modulo $8$.
The Jacobi symbol $\left(\frac{a}{n}\right)$ extends the notation to odd composite $n$ by multiplying the Legendre symbols of its prime factors. It obeys the same reciprocity law, which makes it computable without factorising $n$ — but a value of $+1$ no longer means $a$ is a square.
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}}.$$
The exponent is odd exactly when both $\frac{p-1}{2}$ and $\frac{q-1}{2}$ are odd, that is when $p \equiv q \equiv 3 \pmod 4$. So, stated in words: the two symbols are equal, unless both primes are $3$ modulo $4$, in which case they are opposite.
The supplements. $$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}, \qquad \left(\frac{2}{p}\right) = (-1)^{\frac{p^{2}-1}{8}},$$ so $-1$ is a square exactly for $p \equiv 1 \pmod 4$, and $2$ exactly for $p \equiv \pm 1 \pmod 8$. They are needed because neither $-1$ nor $2$ is an odd prime.
The algorithm. To evaluate $\left(\frac{a}{p}\right)$: reduce $a$ modulo $p$; factorise and discard squares; pull out $-1$ and $2$ with the supplements; for each remaining odd prime $q$, flip to $\left(\frac{p}{q}\right)$ with the sign the two residues modulo $4$ determine; repeat. The numbers shrink at every flip, so the process terminates — and it is Euclid's algorithm with a sign carried along.
No multiplication of large numbers happens anywhere in it, which is why it beats the criterion for speed.
What the law is not. It does not evaluate either symbol on its own; it relates them. It says nothing about square roots. And it does not extend to composite numerators or moduli in the form stated — the Jacobi symbol does that, at the cost of the value $+1$ no longer meaning is a square.
Why it is deep. Nothing about $\left(\frac{q}{p}\right)$ obviously has anything to do with $q$ as a modulus. Euler conjectured the law from tables, Legendre's proof was incomplete, and Gauss proved it at nineteen and gave six distinct proofs across his life. There is still no short elementary argument, and in modern terms it is the first case of class field theory: a statement about how one prime behaves in a field built from another.
Another way: steps
Another way: example
$\left(\frac{30}{53}\right)$. Factorise: $30 = 2 \cdot 3 \cdot 5$. $53 \equiv 5 \pmod 8$, so $\left(\frac{2}{53}\right) = -1$. $53 \equiv 1 \pmod 4$, so both flips are free of sign: $\left(\frac{3}{53}\right) = \left(\frac{53}{3}\right) = \left(\frac{2}{3}\right) = -1$, and $\left(\frac{5}{53}\right) = \left(\frac{53}{5}\right) = \left(\frac{3}{5}\right) = -1$. Product: $(-1)(-1)(-1) = -1$.
Euler's criterion answers is $a$ a square modulo this $p$. Reciprocity can answer a question the criterion cannot even express: for which primes $p$ is a fixed $a$ a square?
The reason is that flipping moves $p$ into the numerator, where it is reduced modulo the small fixed number — so the answer depends only on $p$ modulo something small.
Take $a = 3$. For $p > 3$, reciprocity gives $\left(\frac{3}{p}\right) = \pm\left(\frac{p}{3}\right)$ with the sign decided by $p$ modulo $4$, and $\left(\frac{p}{3}\right)$ depends only on $p$ modulo $3$ — it is $+1$ when $p \equiv 1$ and $-1$ when $p \equiv 2 \pmod 3$. Combining the two conditions with the Chinese remainder theorem, $$\left(\frac{3}{p}\right) = +1 \iff p \equiv \pm 1 \pmod{12}.$$
One congruence condition on $p$, covering every prime at once. The criterion could never produce this: it evaluates one symbol for one modulus, and there are infinitely many moduli.
The same move works for any fixed $a$: the set of primes for which $a$ is a square is always a union of congruence classes modulo $4|a|$. That is a striking statement — whether a fixed number is a square modulo $p$ is decided by $p$'s remainder on division by a fixed number, no matter how large $p$ is.
It also explains the first supplement's role in unit 5. $-1$ is a square modulo $p$ exactly when $p \equiv 1 \pmod 4$; that turns out to be exactly the condition for $p$ to be a sum of two squares, and the proof runs through the square root of $-1$. A congruence condition on a prime, deciding a representation problem — that is the pattern, and reciprocity is what generates such conditions.
Applying it to composite numbers. The Legendre symbol needs a prime modulus, and the law needs both numbers prime. Factorise the numerator first; for a composite modulus you are in Jacobi territory, where $+1$ does not mean is a square.
Using the main law on $2$ or $-1$. Neither is an odd prime. They have their own supplements, and skipping to the main law with a numerator of $2$ is simply not an available step.
Getting the sign condition backwards. The symbols agree in three of the four cases. They differ only when both primes are $3$ modulo $4$ — the rarer case, and the one to check for rather than assume.
Forgetting to reduce before flipping. Flipping a symbol whose numerator exceeds the denominator wastes the step. Reduce first; that is what makes the numbers shrink and the process terminate.
Expecting a root. The whole unit decides solvability. A symbol of $+1$ guarantees two roots exist and hands you neither.
$\left(\frac{11}{19}\right)$. Both are odd primes, and $11 \equiv 3$, $19 \equiv 3 \pmod 4$ — both $3$, so flipping changes the sign.
Check the residues before flipping, not after.
So $\left(\frac{11}{19}\right) = -\left(\frac{19}{11}\right) = -\left(\frac{8}{11}\right)$, reducing $19$ modulo $11$.
Reduce immediately after flipping.
$8 = 2^{3} = 2^{2} \cdot 2$, so the square drops and $\left(\frac{8}{11}\right) = \left(\frac{2}{11}\right)$. Now $11 \equiv 3 \pmod 8$, so that is $-1$. The answer is $-(-1) = +1$.
The supplement finishes it with no exponentiation anywhere.
For which primes $p > 5$ is $5$ a square modulo $p$? Since $5 \equiv 1 \pmod 4$, flipping never changes the sign: $\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right)$.
One of the two primes being $1$ modulo $4$ removes the sign entirely.
$\left(\frac{p}{5}\right)$ depends only on $p$ modulo $5$, and the squares modulo $5$ are $\{1, 4\}$.
The numerator is now reduced against a fixed small prime.
So $5$ is a square modulo $p$ exactly when $p \equiv \pm 1 \pmod 5$. One congruence, covering every prime — and this is the fact behind the appearance of $\sqrt5$ in the Fibonacci numbers modulo $p$.
A statement the criterion cannot express.
$13 \equiv 1 \pmod 4$, so flipping does not change the sign, whatever $7$ is modulo $4$.
One prime being $1$ modulo $4$ settles the sign on its own.
So $\left(\frac{7}{13}\right) = \left(\frac{13}{7}\right) = \left(\frac{6}{7}\right)$, reducing $13$ modulo $7$.
Reduce straight after the flip.
$6 = 2 \cdot 3$, so split: $\left(\frac{2}{7}\right) = +1$ since $7 \equiv -1 \pmod 8$, and $\left(\frac{3}{7}\right) = -\left(\frac{7}{3}\right) = -\left(\frac{1}{3}\right) = -1$ since both are $3$ modulo $4$. The product is $-1$.
You are evaluating $\left(\frac{11}{23}\right)$ by reciprocity. Put the steps into the order you carry them out.
Number the steps in order (write the number in the box):
What is $\left(\frac{19}{7}\right)$? The answer is $1$ or $-1$.
Answer:
Is this true: reciprocity gives the square roots when the symbol is $1$?
For the primes $31$ and $17$, give each one modulo $4$, and then both Legendre symbols.
| Value | |
|---|---|
| $31$ modulo $4$ | |
| $17$ modulo $4$ | |
| The symbol of $17$ over $31$ | |
| The symbol of $31$ over $17$ |
For each pair of primes, say whether the two Legendre symbols agree or differ.
| the two symbols agree | the two symbols differ | |
|---|---|---|
| $5$ and $11$ | ||
| $31$ and $19$ | ||
| $23$ and $17$ |
Does $x^{2} \equiv 19 \pmod{31}$ have a solution? Answer with the Legendre symbol: $1$ for yes, $-1$ for no.
answer a
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
You are evaluating $\left(\frac{3}{13}\right)$ by reciprocity. Put the steps into the order you carry them out.
Number the steps in order (write the number in the box):
You can evaluate any Legendre symbol without exponentiating, by reducing and flipping. Say in your own words what the law does and does not tell you about the square roots. Next: the equations these residue questions were always about.
9. Your turn: evaluate the symbol of $7$ over $13$, step 3