Back to the on-screen lesson ·
One exponentiation decides whether a residue is a square, proves the symbol multiplicative, and settles when minus one is a square.
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 evaluate a Legendre symbol by raising the residue to the power $(p-1)/2$, prove the criterion from a primitive root, derive the multiplicativity of the symbol from it, state the first supplement and say which primes have a square root of minus one, and reduce a composite numerator by discarding square factors.
Lesson 16: every non-zero residue modulo a prime is a power of a fixed primitive root $g$, and $g^{(p-1)/2}$ has order $2$, so it is $-1$.
Lesson 17: the quadratic residues are exactly the even powers of $g$.
Put those together and something falls out. Raising $g^{k}$ to the power $(p-1)/2$ gives $\left(g^{(p-1)/2}\right)^{k} = (-1)^{k}$, which is $+1$ when $k$ is even and $-1$ when it is odd — that is, $+1$ exactly for the squares. A single exponentiation reports the parity of an exponent nobody computed.
A criterion is a condition equivalent to the property in question, and here it is also computable, which a criterion need not be — Wilson's was not.
The supplements to quadratic reciprocity are the two symbols the main law does not cover, because their numerators are not odd primes: $\left(\frac{-1}{p}\right)$ (the first) and $\left(\frac{2}{p}\right)$ (the second).
A character modulo $p$ is a multiplicative map from the units to the unit circle. $\left(\frac{\cdot}{p}\right)$ is the quadratic character, the one everybody meets first, and it is the only one taking just the values $\pm 1$ non-trivially.
Euler's criterion. For an odd prime $p$ and $p \nmid a$, $$a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \pmod p.$$
Proof. Fix a primitive root $g$ and write $a = g^{k}$. The squares are the even powers, so $\left(\frac{a}{p}\right) = +1$ exactly when $k$ is even. Now $g^{(p-1)/2}$ squares to $g^{p-1} \equiv 1$, and it is not $1$ because its exponent is below the order of $g$; modulo a prime the only square roots of $1$ are $\pm 1$, so it is $-1$. Hence $$a^{\frac{p-1}{2}} = \left(g^{\frac{p-1}{2}}\right)^{k} = (-1)^{k},$$ which is the symbol.
Why the power can only be $\pm 1$. Its square is $a^{p-1} \equiv 1$ by Fermat, and a prime modulus admits only two square roots of $1$. So the computation is self-checking: any other answer means an arithmetic slip, or a modulus that is not prime.
Multiplicativity, free. $(ab)^{(p-1)/2} = a^{(p-1)/2}b^{(p-1)/2}$, so $$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$$ Lesson 17 proved this with primitive roots; here it is a line of exponent algebra, and it holds for the same reason.
The first supplement. Put $a = -1$: $$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases}+1 & p \equiv 1 \pmod 4\\ -1 & p \equiv 3 \pmod 4.\end{cases}$$ So $x^{2} \equiv -1$ is solvable modulo $5, 13, 17, 29$ and not modulo $3, 7, 11, 19$. That single fact decides which primes are sums of two squares, in unit 5.
The second supplement, stated without proof here: $\left(\frac{2}{p}\right) = +1$ exactly when $p \equiv \pm 1 \pmod 8$. It is needed because $2$ is not an odd prime and reciprocity does not reach it.
Another way: steps
Another way: example
$\left(\frac{7}{11}\right)$: compute $7^{5} \bmod 11$. $7^{2} = 49 \equiv 5$, $7^{4} \equiv 25 \equiv 3$, so $7^{5} \equiv 21 \equiv 10 \equiv -1$. So $7$ is a non-residue modulo $11$ — and indeed the residues modulo $11$ are $\{1, 3, 4, 5, 9\}$, with $7$ absent.
Euler's criterion evaluates any Legendre symbol by one exponentiation, which is cheap — a few thousand multiplications even for a prime of several hundred digits. So why does anyone need quadratic reciprocity, which is much harder to prove?
Three reasons, and they are of different kinds.
Speed. Exponentiation modulo $p$ costs about $\log p$ multiplications of numbers of size $p$. Reciprocity costs a run that looks exactly like Euclid's algorithm — reduce, flip, reduce, flip — with no multiplication of large numbers at all. It is faster by roughly the same factor that Euclid's algorithm beats factorisation, and for the Jacobi symbol it is the only practical method.
Generality. Euler's criterion is about a fixed prime modulus: it answers "is $a$ a square modulo this $p$". Reciprocity relates $\left(\frac{q}{p}\right)$ to $\left(\frac{p}{q}\right)$, so it can answer the other question — "for which primes $p$ is this fixed $a$ a square?" — and the answer turns out to be a congruence condition on $p$. That is a completely different kind of statement, and the criterion cannot produce it. The first supplement is the smallest example: $-1$ is a square modulo $p$ exactly when $p \equiv 1 \pmod 4$, a condition on the modulus.
Depth. The criterion is a two-line consequence of facts already in hand. Reciprocity is not a consequence of anything elementary: Euler conjectured it, Legendre gave an incomplete proof, and Gauss proved it at nineteen and returned to it eight times over his life, producing six distinct proofs. There is no known short argument, and the theorem is the doorway to algebraic number theory, where it becomes a statement about how primes split in field extensions.
So the criterion is the computational tool for one modulus, and reciprocity is the structural theorem about how the symbol behaves when the modulus varies. The next lesson is the second of those.
Using it modulo a composite. The proof needs a primitive root and needs $\pm 1$ to be the only square roots of $1$; neither holds in general. Modulo $15$, $2^{7} \equiv 8$, which is neither $1$ nor $14$, and the criterion says nothing.
Forgetting the prime must be odd. Every statement here assumes $p$ odd. Modulo $2$ the exponent $(p-1)/2$ is $1/2$, which is not an exponent.
Reading $p - 1$ as a large number rather than as $-1$. The output is a sign written as a least residue. Seeing $p-1$ and not recognising $-1$ makes the whole criterion unreadable.
Expecting the criterion to produce a root. It produces a sign. Extracting a square root when the symbol is $+1$ needs a separate algorithm, and for $p \equiv 1 \pmod 4$ a substantially cleverer one.
Thinking multiplicativity means $\left(\frac{a + b}{p}\right)$ behaves too. It does not. The symbol respects multiplication and nothing else — there is no rule for a sum, and a symbol must always be reduced and factorised, never split across a sum.
$\left(\frac{5}{13}\right)$ by the criterion: $5^{6} \bmod 13$. $5^{2} = 25 \equiv 12 \equiv -1$, so $5^{6} = (5^{2})^{3} \equiv (-1)^{3} = -1$.
Recognising $12$ as $-1$ shortens the work.
So $5$ is a non-residue modulo $13$.
The criterion reports a sign, not a root.
Check by listing: the squares modulo $13$ are $1, 4, 9, 3, 12, 10$. $5$ is absent, as the criterion said.
The list is available at this size and not at any useful one.
$\left(\frac{18}{23}\right)$. Factorise: $18 = 2 \cdot 3^{2}$, and the square drops out, so the symbol equals $\left(\frac{2}{23}\right)$.
Discarding squares is always the first move.
The second supplement: $23 \equiv 7 \equiv -1 \pmod 8$, so $\left(\frac{2}{23}\right) = +1$.
A congruence on the modulus, with no computing.
So $18$ is a square modulo $23$. Confirming with the criterion: $18^{11} \bmod 23$ does come to $1$, but the factorisation route took no exponentiation at all.
The structural route is shorter, and that is the next lesson's theme.
Factorise the numerator: $-4 = (-1) \cdot 2^{2}$, and use multiplicativity.
Split before evaluating.
The square contributes $+1$, so the symbol is just $\left(\frac{-1}{p}\right)$.
Squares never affect the answer.
By the first supplement that is $+1$ exactly when $p \equiv 1 \pmod 4$. So $-4$ is a square modulo $5, 13, 17, 29, \ldots$ and not modulo $3, 7, 11, \ldots$
Working modulo $13$, compute $9^{6}$, then give the Legendre symbol it determines.
| Value | |
|---|---|
| $9^{6}$ modulo $13$ | |
| The Legendre symbol |
What is $10^{11}$ modulo $23$? Give the least residue.
Answer:
Build the proof that $a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod p$ for an odd prime $p$ not dividing $a$.
This task has no paper form; do it on a device.
Is this true: the criterion needs the prime not to divide the residue?
Match each Legendre symbol to its value, for an odd prime $p$ not dividing $3$.
| $+1$ | $-1$ | |
|---|---|---|
| $\left(\frac{3^{2}}{p}\right)$ | ||
| $\left(\frac{-1}{p}\right)$ when $p \equiv 1 \pmod 4$ | ||
| $\left(\frac{-1}{p}\right)$ when $p \equiv 3 \pmod 4$ | ||
| $\left(\frac{3}{p}\right)^{2}$ |
Modulo $11$ you are told that $\left(\frac{7}{11}\right) = -1$ and that $\left(\frac{b}{11}\right) = -1$ for some $b$. Give $\left(\frac{7b}{11}\right)$ and $\left(\frac{7b^{2}}{11}\right)$.
first symbol a, second symbol c
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Working modulo $23$, compute $13^{11}$, then give the Legendre symbol it determines.
| Value | |
|---|---|
| $13^{11}$ modulo $23$ | |
| The Legendre symbol |
You can decide whether any residue is a square modulo an odd prime with a single exponentiation, and reduce a symbol before computing it. Say in your own words why the power can only come out as plus or minus one. Next: the law that lets the two numbers in a symbol change places.
9. Your turn: for which odd primes $p$ is $\left(\frac{-4}{p}\right) = 1$?, step 3