[proofplan] Apply the general form of [Gauss's Lemma](/theorems/1719) to rewrite both Legendre symbols as $\left(\frac{q}{p}\right) = (-1)^\mu$ and $\left(\frac{p}{q}\right) = (-1)^\nu$, where $\mu$ and $\nu$ count lattice points in the rectangle $S = \{1, \ldots, (p-1)/2\} \times \{1, \ldots, (q-1)/2\}$ in two complementary regions defined by the lines $kp - jq = 0$ and $\pm \frac{p}{2}$, $\pm \frac{q}{2}$. A point-reflection symmetry on $S$ pairs the "excess" regions in $\mu$ and $\nu$, showing their difference from $|S|$ is even; this yields $\mu + \nu \equiv |S| \pmod 2$ and hence $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{|S|} = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$. [/proofplan] [step:Express both Legendre symbols via Gauss's Lemma on the rectangle $S$] Let $p, q$ be distinct odd primes. Set \begin{align*} S = \left\{(j, k) \in \mathbb{Z}^2 : 1 \le j \le \tfrac{p-1}{2},\ 1 \le k \le \tfrac{q-1}{2}\right\}, \end{align*} so $|S| = \frac{p-1}{2} \cdot \frac{q-1}{2}$. Apply [Gauss's Lemma](/theorems/1719) with $a = q$ and the odd prime $p$, valid because $(q, p) = 1$ (distinct primes). For each $j \in \{1, \ldots, (p-1)/2\}$, reduce $qj$ into the symmetric system $(-p/2, p/2)$: the sign $\epsilon_j^{(q/p)}$ is $-1$ exactly when the representative is negative, i.e. when there exists an integer $k \ge 1$ with \begin{align*} -\tfrac{p}{2} < q j - k p < 0. \end{align*} Since $q, j \ge 1$ and the left-hand side forces $k \ge 1$, and since $j \le (p-1)/2$ gives $k \le \frac{qj}{p} + \frac{1}{2} \le \frac{q-1}{2} + 1$, one checks that in fact $k$ lies in $\{1, \ldots, (q-1)/2\}$. (If $k = (q+1)/2$ or larger, then $kp - qj > p/2$, contradicting the bound.) Hence \begin{align*} \mu := \#\left\{(j, k) \in S : 0 < k p - q j < \tfrac{p}{2}\right\}, \end{align*} and [Gauss's Lemma](/theorems/1719) gives $\left(\frac{q}{p}\right) = (-1)^\mu$. Swapping the roles of $p$ and $q$ (using $a = p$ and the odd prime $q$, with $(p, q) = 1$), \begin{align*} \nu := \#\left\{(j, k) \in S : 0 < j q - k p < \tfrac{q}{2}\right\}, \end{align*} and $\left(\frac{p}{q}\right) = (-1)^\nu$. [/step] [step:Partition $S$ by the sign of $kp - jq$ and by "excess" regions] For $(j, k) \in S$, note $kp - jq \ne 0$: if $kp = jq$ then $p \mid jq$, so $p \mid j$ (as $p \ne q$ prime), but $1 \le j \le (p-1)/2 < p$, contradiction. So $S$ partitions into two sets: \begin{align*} S^+ &= \{(j, k) \in S : kp - jq > 0\}, & S^- &= \{(j, k) \in S : kp - jq < 0\}. \end{align*} We further decompose $S^+$ and $S^-$ according to whether the magnitude exceeds $p/2$ or $q/2$ respectively. Define \begin{align*} A &= \{(j, k) \in S^+ : kp - jq > \tfrac{p}{2}\}, & B &= \{(j, k) \in S^- : jq - kp > \tfrac{q}{2}\}. \end{align*} Then \begin{align*} S^+ = \{(j,k) \in S : 0 < kp - jq < \tfrac{p}{2}\} \sqcup A \sqcup \{(j,k) \in S : kp - jq = \tfrac{p}{2}\}, \end{align*} but $kp - jq = p/2$ would force $p \mid 2jq$, which is impossible since $p$ is odd and $(p, jq) = 1$. So the middle exceptional set is empty, and $|S^+| = \mu + |A|$. By the symmetric argument (using that $q$ is odd, so $jq - kp = q/2$ is impossible), \begin{align*} |S^-| = \nu + |B|. \end{align*} Therefore \begin{align*} |S| = |S^+| + |S^-| = \mu + \nu + |A| + |B|. \end{align*} [/step] [step:Establish a bijection between $A$ and $B$ via point-reflection through the centre of $S$] Define the involution \begin{align*} \sigma : S &\to S \\ (j, k) &\mapsto \left(\tfrac{p+1}{2} - j,\ \tfrac{q+1}{2} - k\right) = (j', k'). \end{align*} We first verify $\sigma$ maps $S$ to $S$: since $1 \le j \le (p-1)/2$, we have $1 \le \frac{p+1}{2} - j \le \frac{p-1}{2}$, and similarly for $k'$. Moreover $\sigma \circ \sigma = \operatorname{id}_S$, so $\sigma$ is an involution. Next we compute how $\sigma$ transforms the quantity $kp - jq$. With $j' = (p+1)/2 - j$ and $k' = (q+1)/2 - k$, \begin{align*} k' p - j' q &= \left(\tfrac{q+1}{2} - k\right) p - \left(\tfrac{p+1}{2} - j\right) q \\ &= \tfrac{(q+1)p - (p+1)q}{2} - (kp - jq) \\ &= \tfrac{p - q}{2} - (kp - jq). \end{align*} So \begin{align*} j' q - k' p = (kp - jq) - \tfrac{p - q}{2} = (kp - jq) + \tfrac{q - p}{2}. \end{align*} [claim:$\sigma$ restricts to a bijection $A \to B$] [proof] Suppose $(j, k) \in A$, i.e. $(j, k) \in S$ and $kp - jq > p/2$. We check $(j', k') \in B$, i.e. $j' q - k' p > q/2$: \begin{align*} j' q - k' p = (kp - jq) + \tfrac{q - p}{2} > \tfrac{p}{2} + \tfrac{q - p}{2} = \tfrac{q}{2}. \end{align*} So $\sigma(A) \subseteq B$. Applying the same argument with $p, q$ swapped and $\sigma$ replaced by itself (noting $\sigma$ is symmetric in $(j, k) \leftrightarrow (j', k')$), if $(j', k') \in B$ then $kp - jq > p/2$, i.e. $\sigma(B) \subseteq A$. Since $\sigma \circ \sigma = \operatorname{id}$, $\sigma|_A : A \to B$ is a bijection. [/proof] [/claim] In particular, $|A| = |B|$. [/step] [step:Combine the counts to conclude] From the two previous steps, \begin{align*} |S| = \mu + \nu + |A| + |B| = \mu + \nu + 2|A|. \end{align*} Reducing modulo $2$, \begin{align*} |S| \equiv \mu + \nu \pmod{2}. \end{align*} Therefore \begin{align*} \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^\nu (-1)^\mu = (-1)^{\mu + \nu} = (-1)^{|S|} = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}. \end{align*} [guided] We have assembled the identity \begin{align*} |S| = \mu + \nu + 2|A|, \end{align*} which came from two ingredients: the partition $|S| = \mu + \nu + |A| + |B|$ (from Step 2) and the equality $|A| = |B|$ (from Step 3, via the point-reflection $\sigma$). Why does this give quadratic reciprocity? The Legendre symbol formulas $\left(\frac{q}{p}\right) = (-1)^\mu$ and $\left(\frac{p}{q}\right) = (-1)^\nu$ from [Gauss's Lemma](/theorems/1719) depend on $\mu$ and $\nu$ only through their parities. And their parities are determined by $|S| \bmod 2$ (up to the $2|A|$, which is always even). Concretely, \begin{align*} \mu + \nu \equiv |S| = \tfrac{p-1}{2} \cdot \tfrac{q-1}{2} \pmod{2}, \end{align*} so \begin{align*} \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\mu + \nu} = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}. \end{align*} Why do we need the upgrade from congruence in $\{\pm 1\}$ to equality? Both sides of the final display lie in $\{+1, -1\}$: the left side as a product of two Legendre symbols of units (each $\pm 1$), the right side by construction. A congruence modulo $p$ or $q$ would require such an upgrade, but here we are equating integers directly: $(-1)^{\mu + \nu}$ and $(-1)^{|S|}$ are equal as integers whenever $\mu + \nu \equiv |S| \pmod 2$, which we established. The key geometric input is the involution $\sigma$. Why does it work? $\sigma$ is the point-reflection of $S$ through its centre $\left(\frac{p+1}{4}, \frac{q+1}{4}\right)$. The linear form $kp - jq$ picks up a constant shift of $(p - q)/2$ and a sign flip under this reflection; consequently the region $\{kp - jq > p/2\}$ (which is $A$) maps to the region $\{jq - kp > q/2\}$ (which is $B$). Without the reflection, there is no reason to expect $|A| = |B|$; with it, the identity is transparent. Finally, why are $kp - jq = 0$ and $kp - jq = \pm p/2$, $\pm q/2$ all impossible on $S$? The first because $(p, q) = 1$ and $j < p$, the others because $p, q$ are odd (so $p/2, q/2$ are not integers, let alone integers of the form $kp - jq$). These "boundary" cases being empty lets us write clean strict inequalities throughout the partition and bijection arguments. [/guided] [/step]