"Is a a quadratic residue modulo p?" is really a three-way question in disguise: yes, no, or "well, p divides a so the question doesn't quite apply." Writing that out in words every time gets tiresome fast — especially once you start multiplying several of these yes/no answers together. The Legendre symbol squashes the whole three-way answer into a single number: +1, -1 or 0. Once residue-or-not becomes a number, it can be multiplied, substituted into formulas, and computed with ordinary arithmetic instead of with a list of squares.

Definition

For an odd prime p and integer a:

Read \left(\tfrac{a}{p}\right) as "the Legendre symbol of a over p" — it looks like a fraction but it is not division; it is purely notation for which of the three cases holds. Nothing about the underlying mathematics is new here — everything the symbol reports was already decided the moment a, p were fixed. What's new is a name for the answer that behaves like a number: you can multiply two Legendre symbols together, substitute them into formulas, and reason about them algebraically instead of re-deriving "residue or not?" from scratch every time.

Worked examples: computing by direct check

The most literal way to evaluate a Legendre symbol is to list the quadratic residues and look up the answer, exactly as before. Modulo 7 the nonzero residues are \{1, 2, 4\}, so:

Modulo 11 the residues are \{1, 3, 4, 5, 9\} (check: 4^2 = 16 \equiv 5), so:

This works fine for small primes, but listing every square modulo a 300-digit prime is hopeless — which is exactly why the next shortcut matters. Notice, too, that the direct check already confirms the multiplication rule from before is doing real work: knowing \left(\tfrac{3}{7}\right) = -1 means 3 times any residue must land on a non-residue, and vice versa — a fact we'll lean on again shortly.

Worked example: Euler's criterion as a shortcut

Rather than listing squares, a single exponentiation settles the question directly:

Check it against the values just computed. For \left(\tfrac{3}{7}\right), compute 3^{(7-1)/2} = 3^{3} = 27 \equiv 6 \equiv -1 \pmod 7 — matching the -1 found by direct search. For \left(\tfrac{5}{11}\right), compute 5^{(11-1)/2} = 5^{5}: since 5^{2} \equiv 3, 5^{4} \equiv 3^{2} = 9, so 5^{5} \equiv 9 \times 5 = 45 \equiv 1 \pmod{11} — matching +1. One exponentiation (fast even for huge numbers, via repeated squaring) replaces an entire table of squares. The proof that this formula always works is Euler's criterion, next.

It's completely multiplicative

Check it modulo 7: we already know \left(\tfrac{2}{7}\right) = +1 (since 3^2 \equiv 2) and \left(\tfrac{3}{7}\right) = -1. Multiplying, 2 \times 3 = 6, and modulo 7 the residue 6 is a non-residue, so \left(\tfrac{6}{7}\right) = -1. Indeed (+1)(-1) = -1 — the formula checks out exactly. This means you can evaluate any symbol by factoring the top and handling each prime factor separately — which, combined with the deep reciprocity law to come, makes the symbol genuinely computable without ever testing squares.

Combining known values: factor and conquer

Multiplicativity means you never need to test a composite a directly — factor it and look up (or compute) each prime factor's symbol separately. A useful side note first: any perfect square k^{2} coprime to p is automatically a quadratic residue (it's a square by construction!), so \left(\tfrac{k^{2}}{p}\right) = +1 always.

Put these together to evaluate \left(\tfrac{12}{13}\right) without squaring a single thing beyond what we already know. Factor 12 = 4 \times 3 = 2^{2} \times 3:

From our earlier list, the residues modulo 13 are \{1, 3, 4, 9, 10, 12\}, so 3 is a residue and \left(\tfrac{3}{13}\right) = +1. Hence \left(\tfrac{12}{13}\right) = +1 — which matches 12 sitting right there in the residue list, confirming the shortcut. With bigger numbers this factor-and-combine approach, sped up further by the reciprocity law still to come, is exactly how the symbol gets evaluated in practice — never by brute-force listing.

A first special value

One famous case follows quickly: when is -1 a square modulo p? The answer depends only on p \bmod 4:

So -1 is a square mod 5 (indeed 2^2 = 4 \equiv -1) but not mod 7. The tool that proves such formulas is Euler's criterion.

A second special value: is 2 a square?

The same style of question — "for which primes is a fixed number a square?" — has a clean answer for a = 2 as well, depending only on p \bmod 8:

Test it against residues we already listed. Modulo 7, we have 7 \equiv -1 \pmod 8, so the formula predicts \left(\tfrac{2}{7}\right) = +1 — and indeed 3^2 \equiv 2 \pmod 7, confirming it. Modulo 11, we have 11 \equiv 3 \pmod 8, so the formula predicts \left(\tfrac{2}{11}\right) = -1 — and checking the residue set \{1,3,4,5,9\}, 2 is indeed missing. Two completely different-looking special formulas — one for -1, one for 2 — both fall out of the same machinery, and together with the multiplicative property they let you evaluate \left(\tfrac{a}{p}\right) for plenty of small a by factoring a into primes and combining known special values, with no square-hunting at all.

Putting the toolkit together

Step back and count what's now available for evaluating \left(\tfrac{a}{p}\right) without ever listing squares: Euler's criterion turns any single symbol into one modular exponentiation; multiplicativity lets you factor a and handle each prime factor on its own; and the two special-value formulas for -1 and 2 hand you instant answers for those two factors without any computation at all. Together they already crack a surprising number of cases by hand.

The one piece still missing is what happens when a itself is an odd prime different from p — say, evaluating \left(\tfrac{7}{13}\right). Multiplicativity can't break 7 down any further, and it isn't -1 or 2. That gap is exactly what the astonishing law of quadratic reciprocity closes, by relating \left(\tfrac{7}{13}\right) to \left(\tfrac{13}{7}\right) — flipping the symbol upside down.