1. What is a quadratic residue?
Let $p$ be an odd prime and let $a$ be an integer with $p \nmid a$. We call $a$ a quadratic residue modulo $p$ if there exists an integer $x$ such that
$$ x^2 \equiv a \pmod{p}. $$If no such $x$ exists, $a$ is a quadratic non-residue.
The question being asked is: among the nonzero residue classes mod $p$, which ones can be reached by squaring? Square every nonzero element, see what comes out.
Try $p = 7$. Squaring $1, 2, 3, 4, 5, 6$ modulo $7$ gives
$$ 1^2, 2^2, 3^2, 4^2, 5^2, 6^2 \;\equiv\; 1, 4, 2, 2, 4, 1 \pmod{7}. $$The image is $\{1, 2, 4\}$ — exactly three values. The non-residues are $\{3, 5, 6\}$, also three. The split is even. That isn't a coincidence:
For an odd prime $p$, exactly $\tfrac{p-1}{2}$ of the residues $\{1, 2, \ldots, p-1\}$ are quadratic residues, and the other $\tfrac{p-1}{2}$ are non-residues.
Why? The map $x \mapsto x^2$ on $\{1, \ldots, p-1\}$ pairs every value with its negative: $x^2 \equiv (-x)^2 \pmod{p}$, and modulo an odd prime $x \not\equiv -x$. So the squaring map is exactly two-to-one, and its image has $(p-1)/2$ elements.
Imagine folding the multiplicative group $(\mathbb{Z}/p)^\times$ in half — every element gets identified with its negative. The squares are the "fold lines," the half-sized image left over. The non-residues are exactly the elements that disappeared in the folding.
2. The Legendre symbol
We need a compact way to say "is $a$ a square mod $p$ or not?" That's what the Legendre symbol does — it's a yes/no flag written as if it were a fraction, but it isn't one.
For an odd prime $p$ and any integer $a$,
$$ \left(\frac{a}{p}\right) = \begin{cases} +1 & \text{if } a \text{ is a quadratic residue mod } p \text{ and } p \nmid a, \\ -1 & \text{if } a \text{ is a quadratic non-residue mod } p, \\ \phantom{+}0 & \text{if } p \mid a. \end{cases} $$The notation $\left(\tfrac{a}{p}\right)$ looks like a fraction but is one symbol. The bottom must be an odd prime; the top is any integer. Read it as "the Legendre symbol of $a$ over $p$."
From the $p = 7$ calculation above:
$$ \left(\tfrac{1}{7}\right) = \left(\tfrac{2}{7}\right) = \left(\tfrac{4}{7}\right) = +1, \qquad \left(\tfrac{3}{7}\right) = \left(\tfrac{5}{7}\right) = \left(\tfrac{6}{7}\right) = -1. $$3. Euler's criterion
Listing squares works for tiny primes. For real primes — five, six, ten digits — we need a formula. Euler gave one.
For an odd prime $p$ and any integer $a$ with $p \nmid a$,
$$ \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}. $$The right side is necessarily $\pm 1 \pmod p$, so this is an equation of integers in $\{-1, +1\}$, not just a congruence.
Short proof
By Fermat's little theorem, $a^{p-1} \equiv 1 \pmod p$. Therefore
$$ \bigl(a^{(p-1)/2}\bigr)^2 - 1 \equiv 0 \pmod{p}, $$which factors as $\bigl(a^{(p-1)/2} - 1\bigr)\bigl(a^{(p-1)/2} + 1\bigr) \equiv 0 \pmod p$. Since $p$ is prime, one factor must vanish, so
$$ a^{(p-1)/2} \equiv \pm 1 \pmod{p}. $$Now compare cases. Case 1: $a$ is a QR. Then $a \equiv x^2$ for some $x$, so
$$ a^{(p-1)/2} \equiv x^{p-1} \equiv 1 \pmod{p}, $$matching $\left(\tfrac{a}{p}\right) = +1$.
Case 2: $a$ is a non-residue. The polynomial $X^{(p-1)/2} - 1$ has at most $(p-1)/2$ roots mod $p$ — and we just saw every QR is a root. So no non-residue can be a root, and therefore $a^{(p-1)/2} \equiv -1 \pmod p$, matching $\left(\tfrac{a}{p}\right) = -1$. $\blacksquare$
Euler's criterion turns a search ("does some $x$ exist?") into a calculation (raise $a$ to a known power mod $p$ and check the sign). With fast modular exponentiation, you can decide quadratic residue-hood for a 1000-digit prime in a fraction of a second. The criterion is the theoretical hinge behind every Legendre/Jacobi-symbol algorithm.
4. Multiplicativity
The Legendre symbol respects multiplication on top:
$$ \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right). $$This drops out of Euler's criterion in one line:
$$ (ab)^{(p-1)/2} = a^{(p-1)/2} \cdot b^{(p-1)/2} \pmod{p}. $$So the QR/non-QR pattern obeys the same sign rules as multiplying $\pm 1$: residue · residue = residue; residue · non-residue = non-residue; non-residue · non-residue = residue. The last one is the surprising one — two "bad" numbers multiplied together give a "good" one.
Multiplicativity is what makes Legendre symbols computable. To find $\left(\tfrac{n}{p}\right)$, factor $n$ into primes, evaluate the Legendre symbol of each factor, and multiply the signs. Most of number-theoretic work on residues reduces to this.
5. The two supplementary laws
Before reciprocity itself, two special cases pin down what the Legendre symbol does to $-1$ and to $2$. Both are entirely about the prime $p$ — they tell us when $-1$ and $2$ are squares, with no second prime in sight.
First supplement: is $-1$ a square mod $p$?
For an odd prime $p$,
$$ \left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} +1 & \text{if } p \equiv 1 \pmod 4, \\ -1 & \text{if } p \equiv 3 \pmod 4. \end{cases} $$Plug $a = -1$ into Euler's criterion and you get this immediately: $(-1)^{(p-1)/2}$ is $+1$ when $(p-1)/2$ is even (i.e. $p \equiv 1 \pmod 4$) and $-1$ otherwise.
Check: $\left(\tfrac{-1}{5}\right) = +1$ (since $5 \equiv 1 \bmod 4$), and indeed $2^2 = 4 \equiv -1 \pmod 5$. Meanwhile $\left(\tfrac{-1}{7}\right) = -1$ (since $7 \equiv 3 \bmod 4$), and $-1 \equiv 6 \pmod 7$ is not among the squares $\{1, 2, 4\}$ we found earlier.
Second supplement: is $2$ a square mod $p$?
For an odd prime $p$,
$$ \left(\frac{2}{p}\right) = (-1)^{(p^2 - 1)/8} = \begin{cases} +1 & \text{if } p \equiv \pm 1 \pmod 8, \\ -1 & \text{if } p \equiv \pm 3 \pmod 8. \end{cases} $$The exponent $(p^2 - 1)/8$ is always an integer when $p$ is odd (since $p^2 \equiv 1 \bmod 8$). The case split into residues mod $8$ comes from working out when that exponent is even or odd.
The two supplements together let you handle the factors $-1$ and $2$ that pop out of any prime factorization. Combined with reciprocity, they give a complete decision procedure for every Legendre symbol.
6. Quadratic reciprocity
So far we've answered "is $a$ a square mod $p$?" by working with one prime at a time. Reciprocity is something different. It relates two completely separate questions — "is $p$ a square mod $q$?" and "is $q$ a square mod $p$?" — and says they are almost always the same question. The link between $p$ and $q$ is symmetric, with one small twist.
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}}. $$Read it slowly. The two Legendre symbols on the left know nothing about each other — one lives "mod $p$," the other "mod $q$." Reciprocity says their product is a sign that depends only on the residues of $p$ and $q$ modulo $4$.
The cleaner restatement
The exponent $\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}$ is even unless both $\tfrac{p-1}{2}$ and $\tfrac{q-1}{2}$ are odd — which happens exactly when both $p$ and $q$ are $\equiv 3 \pmod 4$. So reciprocity is the same as:
If $p \equiv 1 \pmod 4$ or $q \equiv 1 \pmod 4$, then $\left(\tfrac{p}{q}\right) = \left(\tfrac{q}{p}\right)$ — the two symbols agree. If $p \equiv 3 \pmod 4$ and $q \equiv 3 \pmod 4$, they disagree: $\left(\tfrac{p}{q}\right) = -\left(\tfrac{q}{p}\right)$.
That's the heart of it. The question of whether $p$ is a square mod $q$ is essentially the same as whether $q$ is a square mod $p$, with a single sign flip when both primes have the unlucky residue $3 \bmod 4$.
There is no a priori reason the arithmetic of squares mod $p$ should know anything about the arithmetic of squares mod $q$. They are two different worlds. Reciprocity says the worlds are mirrors — and the mirror is rigged by a sign rule that involves nothing harder than "$p$ mod $4$."
On the proof
We don't prove quadratic reciprocity here. It deserves its reputation for difficulty: Gauss called it the theorema aureum ("golden theorem") and gave eight different proofs over his lifetime, and the modern count is well past 300. Each proof comes from a different corner of mathematics — Gauss sums, lattice points, Eisenstein's lemma, cyclotomic fields, the Stickelberger relation, even ideas from algebraic geometry.
The flavor worth remembering is the geometric one. Eisenstein's lattice-point proof realizes the exponent $\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}$ as the number of integer points inside a certain rectangle, then chops the rectangle along its diagonal and shows each Legendre symbol counts the parity of lattice points on one side. The triangles match — except for an asymmetry pinned exactly by the residue of each prime mod $4$. That asymmetry is reciprocity.
Reciprocity has descendants. Higher reciprocity laws (cubic, biquadratic) generalize to roots beyond squares; the Artin reciprocity law of class field theory absorbs them all into a single statement about Galois groups. Quadratic reciprocity is the first signpost on that road.