Quadratic residues

It turns an existence question (does some $x$ square to $a$?) into a single modular exponentiation, which is exactly what makes the Legendre symbol computable and multiplicative.

Since $(\mathbb{Z}/p\mathbb{Z})^{*}$ is cyclic of order $p-1$ (a standard fact for prime moduli), fix a primitive root $g$ and write $a \equiv g^k \pmod p$ for some $0 \le k \le p-2$. The quadratic residues modulo $p$ are exactly the even powers of $g$: if $a=g^{2m}$ then $x=g^m$ satisfies $x^2\equiv a$, and conversely every square $x^2=(g^j)^2=g^{2j}$ is an even power. So $a$ is a quadratic residue exactly when $k$ is even.

Now compute $a^{(p-1)/2} \equiv g^{k(p-1)/2} \pmod p$. If $k$ is even, write $k=2m$; then $g^{k(p-1)/2}=g^{m(p-1)}=(g^{p-1})^m\equiv 1^m=1\pmod p$ by Fermat's little theorem, matching the residue case.

If $k$ is odd, then $g^{k(p-1)/2}$ is a square root of $g^{k(p-1)}=(g^{p-1})^k\equiv 1\pmod p$, so $a^{(p-1)/2}\equiv \pm 1$. It cannot be $1$: if it were, the order of $g$ would have to divide $k(p-1)/2$, but $\operatorname{ord}(g)=p-1$ and $k$ is odd means $k(p-1)/2$ is not a multiple of $p-1$ unless $(p-1)/2$ already is, contradicting that $g$ is a primitive root of exact order $p-1$. Hence $a^{(p-1)/2}\equiv -1\pmod p$ exactly when $k$ is odd, i.e. exactly when $a$ is a nonresidue.

Combining both cases: $a^{(p-1)/2}\equiv 1\pmod p$ iff $a$ is a quadratic residue, and $\equiv -1$ otherwise, which is precisely the statement $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$.

It says whether $p$ is a square mod $q$ and whether $q$ is a square mod $p$ are the same question, up to a sign that depends only on the residues of $p,q$ mod $4$ — turning a hard-looking two-variable problem into a one-line rule.

We use Gauss's lemma as a stepping stone: for an odd prime $p$ and $\gcd(a,p)=1$, look at the least positive residues of $a, 2a, \dots, \frac{p-1}{2}a$ modulo $p$, and let $\mu$ be how many of them exceed $p/2$. Gauss's lemma states $\left(\dfrac{a}{p}\right)=(-1)^{\mu}$; it follows from pairing each such "large" residue $r$ with $p-r\le p/2$ and tracking signs when multiplying the $\frac{p-1}{2}$ numbers together in two different ways.

Eisenstein's refinement expresses $\mu$ as a lattice-point count: one shows $\mu \equiv \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor \pmod 2$ when $a=q$ is odd, by comparing $\lfloor kq/p\rfloor$ (the number of multiples of $p$ below $kq$) to how far $kq \bmod p$ sits from $p/2$. Applying the same counting argument symmetrically gives $\left(\frac{q}{p}\right)=(-1)^{S(q,p)}$ and $\left(\frac{p}{q}\right)=(-1)^{S(p,q)}$, where $S(q,p)=\sum_{k=1}^{(p-1)/2}\left\lfloor \frac{kq}{p}\right\rfloor$ and $S(p,q)=\sum_{k=1}^{(q-1)/2}\left\lfloor \frac{kp}{q}\right\rfloor$.

Geometrically, $S(q,p)+S(p,q)$ counts the lattice points $(x,y)$ with $1\le x\le \frac{p-1}{2}$, $1\le y\le \frac{q-1}{2}$ lying strictly below the line $qx=py$ (that count is $S(q,p)$) plus those strictly above it (that count is $S(p,q)$, by the symmetric roles of $p,q$). No lattice point lies exactly on the line since $\gcd(p,q)=1$ and $x<p$, so together these two counts exhaust the full rectangle of $\frac{p-1}{2}\cdot\frac{q-1}{2}$ lattice points.

Therefore $S(q,p)+S(p,q) = \frac{p-1}{2}\cdot\frac{q-1}{2}$, and multiplying the two Legendre-symbol formulas gives $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{S(p,q)+S(q,p)}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$, which is exactly $\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$.