Back to the on-screen lesson ·
Which residues are squares, why exactly half are, why a square has exactly two roots, and the sign that records the answer.
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 list the quadratic residues modulo a small odd prime and say why there are exactly half of them, find both square roots of a residue and say why there are no others, state what the Legendre symbol records, and use its multiplicativity to reduce a symbol by discarding square factors.
Lesson 16 fixed a primitive root $g$ modulo a prime and observed that every non-zero residue is $g^{k}$ for exactly one $k$ between $1$ and $p-1$.
Now ask which residues are squares. $g^{k}$ is a square exactly when $k$ is even, since $(g^{j})^{2} = g^{2j}$ covers the even exponents and nothing else. Half the exponents are even, so half the residues are squares — and the whole of this lesson is a study of a fact that took one line to establish. What takes work is deciding which half a given residue is in, without knowing its discrete logarithm.
For an odd prime $p$ and $p \nmid a$: $a$ is a quadratic residue modulo $p$ when $x^{2} \equiv a \pmod p$ has a solution, and a quadratic non-residue when it does not. Note $0$ is excluded by convention.
The Legendre symbol $\left(\frac{a}{p}\right)$ is $+1$ when $a$ is a residue, $-1$ when it is a non-residue, and $0$ when $p \mid a$. It is a function of $a$ modulo $p$, so $\left(\frac{a}{p}\right)$ depends only on the class of $a$.
The quadratic character is another name for the map $a \mapsto \left(\frac{a}{p}\right)$, which stresses what matters: it is multiplicative, so it behaves like a sign.
Exactly half. Squaring sends $x$ and $p - x$ to the same residue, and those are different residues for $x \ne 0$. So the map $x \mapsto x^{2}$ on the $p-1$ non-zero residues is two-to-one onto its image, and the image has $(p-1)/2$ elements. Exactly half the non-zero residues are squares.
Exactly two roots. If $x^{2} \equiv y^{2} \pmod p$ then $p \mid (x-y)(x+y)$, and a prime divides one factor, so $x \equiv \pm y$. A solvable congruence therefore has exactly two solutions, $x$ and $p - x$, which add to $p$. Over a composite modulus this fails: $x^{2} \equiv 1 \pmod{15}$ has four solutions.
The symbol, and why it multiplies. Writing residues as powers of a primitive root, $a = g^{i}$ and $b = g^{j}$, a residue is a square exactly when its exponent is even. Then $ab = g^{i+j}$, and the parity of $i + j$ is the product of the parities: $$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$$
Read the three cases out: residue times residue is a residue; residue times non-residue is a non-residue; and non-residue times non-residue is a residue. The last is the surprising one, and it is the reason a $\pm 1$ symbol is the right notation — the residues behave like even and the non-residues like odd.
A first consequence. $\left(\frac{a^{2}b}{p}\right) = \left(\frac{b}{p}\right)$, since a square contributes $+1$. So only the squarefree part of a number matters, which is what lets the next two lessons reduce any symbol to symbols of primes.
What it does not give. The symbol decides solvability and produces no root. Deciding is cheap; extracting a root is a genuinely separate problem, and for $p \equiv 1 \pmod 4$ it needs an algorithm of its own.
Another way: steps
Another way: example
Modulo $11$: the squares of $1, \ldots, 5$ are $1, 4, 9, 5, 3$. So the residues are $\{1, 3, 4, 5, 9\}$ — five of them, as $(11-1)/2$ requires — and the non-residues are $\{2, 6, 7, 8, 10\}$. Check multiplicativity: $2 \cdot 6 = 12 \equiv 1$, a residue, from two non-residues.
A definition that only ever gets two values might as well be a yes-or-no question, and writing it as $\pm 1$ looks like decoration. It is not, and the reason is one property: it multiplies.
A yes-or-no answer does not compose. Knowing that $a$ is a square and $b$ is not tells you nothing about $ab$ unless you also know the rule — and the rule, written in words, is three separate cases. Written as $\pm 1$ it is one equation, $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$, and the three cases become ordinary multiplication of signs.
That turns the evaluation of a symbol into a factorisation problem. To decide $\left(\frac{42}{p}\right)$, factorise: $42 = 2 \cdot 3 \cdot 7$, so the answer is the product of three symbols with prime numerators. Square factors drop out for free, since $\left(\frac{a^{2}}{p}\right) = +1$ always. So every symbol reduces to symbols of primes, and if those can be evaluated then everything can.
That is exactly the shape of the next two lessons. Euler's criterion (lesson 18) evaluates any symbol by a single exponentiation, and also proves the multiplicativity cleanly. Quadratic reciprocity (lesson 19) evaluates a symbol of two primes by swapping them over, which makes the numerator smaller and lets the whole thing be computed by a process that looks exactly like Euclid's algorithm — and needs no exponentiation at all.
There is a further reason the notation earns its place: $\left(\frac{\cdot}{p}\right)$ is the first example of a character, a multiplicative map from the units to the complex numbers of modulus one. Dirichlet's theorem in the last unit is proved with characters, and this is the one everybody meets first.
Expecting a root when the symbol says there is one. The symbol reports solvability. Extracting the root is a different computation, and for $p \equiv 1 \pmod 4$ a substantially harder one.
Assuming a residue has one square root. It has two, and they add to $p$. Reporting only the smaller is reporting half the answer.
Using the symbol with a composite modulus. $\left(\frac{a}{p}\right)$ is defined for an odd prime $p$. There is a related symbol for composite moduli — the Jacobi symbol — and its value $+1$ does not mean $a$ is a square.
Thinking two non-residues cannot multiply to a residue. They always do. Parity of exponents is the right intuition; not being a square is not a property that survives multiplication.
Forgetting $p$ must be odd. Modulo $2$ everything is a square and the whole theory is empty, which is why every statement in this unit says odd prime.
Modulo $13$, square $1$ through $6$: $1, 4, 9, 3, 12, 10$.
Only up to the halfway point; the rest repeat.
So the quadratic residues are $\{1, 3, 4, 9, 10, 12\}$ — six of them, which is $(13-1)/2$ as it must be.
The count is a check on the work.
$7^{2} = 49 \equiv 10$, the same as $6^{2}$, because $7 = 13 - 6$. Every value from here on repeats one already found.
The two-to-one map, seen directly.
Evaluate $\left(\frac{45}{11}\right)$. First reduce the top: $45 \equiv 1 \pmod{11}$, and $1$ is a square.
Reducing the numerator is always the first move.
So the answer is $+1$. Alternatively, factorise before reducing: $45 = 3^{2} \cdot 5$, and the square contributes $+1$, so the symbol equals $\left(\frac{5}{11}\right)$.
Square factors drop out.
And $5$ is on the list of residues modulo $11$ computed above, so $+1$ again. Two routes, one answer — which is what multiplicativity guarantees.
The two routes agreeing is the property being used.
Write each residue as $g^{2k}$ for a primitive root $g$, with $k$ running from $1$ to $(p-1)/2$.
The residues are exactly the even powers.
The product is $g^{2(1 + 2 + \cdots + (p-1)/2)} = g^{m(m+1)}$ where $m = (p-1)/2$, and $m(m+1)$ is a multiple of $m = (p-1)/2$.
Sum the exponents rather than multiplying the residues.
So the product is a power of $g^{(p-1)/2}$, which is $-1$ — hence the product is $\pm 1$ according to the parity of $m + 1$.
Working modulo $13$, square each of $2$, $3$ and $4$ and give the least residue.
| Least residue | |
|---|---|
| $2^{2}$ | |
| $3^{2}$ | |
| $4^{2}$ |
How many of the non-zero residues modulo $13$ are quadratic residues — that is, squares of something?
Answer:
Is $10$ a quadratic residue modulo $11$ — that is, does $x^{2} \equiv 10 \pmod{11}$ have a solution?
Mark the smaller solution of $x^{2} \equiv 11 \pmod{19}$. The line runs from $0$ to $19$.
0 |——————————| 19
Mark the position with a cross, then write the value:
Give both solutions of $x^{2} \equiv 13 \pmod{23}$, in increasing order.
smaller root a, larger root c
Modulo the prime $17$, match each product to what it is.
| a quadratic residue | not a quadratic residue | |
|---|---|---|
| a quadratic residue times a quadratic residue | ||
| a quadratic residue times a non-residue | ||
| a non-residue times a non-residue |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Working modulo $7$, square each of $2$, $3$ and $4$ and give the least residue.
| Least residue | |
|---|---|
| $2^{2}$ | |
| $3^{2}$ | |
| $4^{2}$ |
You can decide whether a residue is a square modulo an odd prime and find both of its roots when it is. Say in your own words why the product of two non-residues is a residue. Next: a single exponentiation that decides any of these.
9. Your turn: show that the product of all the quadratic residues modulo an odd prime is $\pm 1$, step 3