Proof. Considering the prime factorisation of \(|a|\) and using the multiplicativity of the Legendre symbol, we may suppose that we are in one of three cases: \(a = -1,\) \(a = 2,\) or \(a\) is an odd prime. The first two cases are OK by the two supplementary laws, so we suppose we are in the third case.

Since \(p = q \bmod 4|a|,\) either \(p = q = 1 \bmod 4\) or \(p = q = 3 \bmod 4.\) If \(p = q = 1 \bmod 4,\) or if \(a = 1 \bmod 4,\) then we have \[\left(\frac{a}{p}\right) = \left(\frac{p}{a}\right) = \left(\frac{q}{a}\right) = \left(\frac{a}{q}\right).\] If \(a, p, q\) are all \(3 \bmod 4,\) then we have similarly \[\left(\frac{a}{p}\right) = -\left(\frac{p}{a}\right) = -\left(\frac{q}{a}\right) = \left(\frac{a}{q}\right).\]

Proof. Let us compute \(\prod_{x \in L} a x.\)

On the one hand, we can pull out all the factors of \(L\) and get \[\prod_{x \in L} a x = a^{(\#L)} \cdot \prod_{x \in L} x = a^{(p-1)/2} \left(\tfrac{p-1}{2}\right)!.\]

On the other hand, for \(x \in U_p,\) exactly one of \(x\) and \(-x\) is in \(L\); let’s write \(\lambda(x) = x\) if \(x \in L,\) and \(\lambda(x) = -x\) otherwise, and \(\epsilon(x) = x / \lambda(x) \in \{\pm 1\}.\) So we can write \[\begin{aligned} \prod_{x \in L} a x &= \prod_{x \in L} \epsilon(ax) \lambda(ax) \\ &= \left(\prod_{x \in L} \epsilon(ax)\right) \cdot \left(\prod_{x \in L} \lambda(ax)\right)\\ &= \left(-1\right)^s \cdot \left(\prod_{x \in L} \lambda(ax)\right),\\ \end{aligned}\] since the first product has \(s\) terms \(-1\) and all the rest \(+1.\)

We claim \(x \mapsto \lambda(ax)\) is a bijection \(L \to L,\) so the second product is just a re-ordering of the product \(\prod_{x \in L} x = \left(\tfrac{p-1}{2}\right)!.\) It suffices to show the map is injective, since \(L\) is finite. If \(\lambda(ax) = \lambda(ay)\) for some \(x, y \in L,\) then \(ax = \pm ay.\) Since \(a\) is a unit, this implies \(x = \pm y,\) and since \(x, y \in L,\) this forces \(x = y,\) as required.

So we have \(\prod_{x \in L} a x = (-1)^s \left(\tfrac{p-1}{2}\right)!.\) Comparing this with the previous formula for the same product, we have \[a^{(p-1)/2} \left(\tfrac{p-1}{2}\right)! = (-1)^s \left(\tfrac{p-1}{2}\right)!\] and cancelling the (nonzero) common factor \(\left(\tfrac{p-1}{2}\right)!\) gives the lemma.

Proof. Clearly, for an integer \(a \in \{1, \dots, \tfrac{p-1}{2}\},\) we have \(2a \in L\) if \(1 \leqslant a \leqslant\tfrac{p-1}{4},\) and \(2a \notin L\) if \(\tfrac{p-1}{4} < a \leqslant\tfrac{p-1}{2}\}.\) So \(\left(\frac{2}{p}\right)\) is \((-1)^s,\) where \(s = \#\{ a : \tfrac{p-1}{4} < a \leqslant\tfrac{p-1}{2}\}.\)

Now we consider cases:

• \(p = 8q + 1\): then \(s = \#\{ a : 2q < a \leqslant 4q \} = 2q\) even

• \(p = 8q + 3\): then \(s = \#\{ a : 2q + \tfrac{1}{2} < a \leqslant 4q + 1 \} = 2q + 1\) odd

• \(p = 8q + 5\): then \(s = \#\{ a : 2q + 1 < a \leqslant 4q + 2 \} = 2q + 1\) odd

• \(p = 8q + 7\): then \(s = \#\{ a : 2q + \tfrac{3}{2} < a \leqslant 4q + 3\} = 2q + 2\) even.

Proof. It suffices to show that \(t = s\bmod 2,\) where \(s\) is as in Gauss’ lemma. For each \(i,\) we write \[i a = p \cdot \lfloor \tfrac{ia}{p} \rfloor + r_i\] where \(r_i\) is the unique integer in \(\{1, \dots, p-1\}\) congruent to \(ia \bmod p.\) Adding these equations together, and reducing mod 2 (remembering that \(a\) and \(p\) are odd), we obtain \[(1 + \dots + \tfrac{p-1}{2}) = t + \sum r_i.\]

As in the proof of Gauss’ lemma, for each \(\ell \in L,\) exactly one of \(\ell\) or \(p - \ell\) occurs among the \(r_i.\) Moreover, the number of times that \(p - \ell\) occurs is \(s.\) Since \(p - \ell = 1 + \ell \bmod 2,\) we have \(\sum r_i = s + (1+ \dots + \tfrac{p-1}{2}).\) Plugging this into the above, we deduce that \[(1 + \dots + \tfrac{p-1}{2}) = t + s + (1 + \dots + \tfrac{p-1}{2}) \bmod 2,\] so \(t = -s = s \bmod 2.\)

Proof of Quadratic Reciprocity. We’re going to do this by “counting lattice points”. Consider the rectangle \(R\) in the \((x, y)\) plane with vertices at \((0, 0),\) \((p/2, 0),\) \((p/2, q/2)\) and \((0, q/2).\) The diagonal \(y = \tfrac{q}{p}\) x divides this into two triangles.

We want to count the pairs \((x, y) \in \mathbb{Z}^2\) which lie in the interior of \(R.\) Evidently there are exactly \(\tfrac{p-1}{2} \cdot \tfrac{q-1}{2}\) of these in total; and none of them lie exactly on the diagonal (since \(p\) and \(q\) are distinct primes).

On the other hand, how many lie below the diagonal? For each \(i = 1, \dots, \tfrac{p-1}{2},\) the number of points below the diagonal in the “vertical column” with \(x = i\) is exactly \(\lfloor \tfrac{iq}{p}\rfloor.\) Thus the total number is the quantity \(t\) from the last lemma; so \((-1)^t = \left(\frac{q}{p}\right).\)

Reversing the roles of \(p\) and \(q,\) the number of lattice points above the diagonal, \(t',\) satisfies \((-1)^{t'} = \left(\frac{p}{q}\right).\) Since every point must lie above or below the diagonal, \(t + t' = \tfrac{(p-1)}{2} \cdot \tfrac{(q-1)}{2},\) and hence \[\left(\frac{q}{p}\right) \cdot \left(\frac{p}{q}\right) = (-1)^{t + t'} = (-1)^{\tfrac{(p-1)}{2} \cdot \tfrac{(q-1)}{2}}.\] which proves the theorem.