Proof of Gauss's lemma on quadratic residues

Proof

1. Let $p$ be an odd prime, $a$ an integer with $p \nmid a$, and $h = (p-1)/2$. For $k = 1, \dots, h$, let $r_k$ be the least positive residue of $ka$ modulo $p$.
2. By Euclid's lemma, $p \nmid ka$, so $1 \le r_k \le p - 1$. Since $p$ is odd, $r_k \ne p/2$.
3. Put $s_k = r_k$ and $\varepsilon_k = 1$ if $r_k < p/2$. Put $s_k = p - r_k$ and $\varepsilon_k = -1$ if $r_k > p/2$.
4. Then $1 \le s_k \le h$ and $ka \equiv \varepsilon_k s_k \pmod p$. Exactly $n$ of the $\varepsilon_k$ equal $-1$, where $n$ is the number in the statement.
5. The $s_k$ are distinct. Suppose $s_k = s_l$ with $1 \le k, l \le h$. Then $ka \equiv \pm la$, so $p \mid (k \mp l) a$. As $p \nmid a$, Euclid's lemma gives $p \mid k - l$ or $p \mid k + l$.
6. But $\abs{k - l} < p$ and $2 \le k + l \le p - 1$. So $k + l$ is not a multiple of $p$, and $k - l = 0$.
7. So $s_1, \dots, s_h$ are $h$ distinct numbers in $\set{1, \dots, h}$. Hence they are $1, \dots, h$ in some order.
8. Multiplying the congruences of step 4 with products of congruences gives $a^h \cdot h! = \prod_{k=1}^{h} ka \equiv \prod_{k=1}^{h} \varepsilon_k s_k = (-1)^n h! \pmod p$.
9. So $p \mid h! \left(a^h - (-1)^n\right)$. Every factor of $h!$ is less than $p$, so $p \nmid h!$ by Euclid's lemma. Thus $a^h \equiv (-1)^n \pmod p$.
10. By Euler's criterion, $\left(\frac{a}{p}\right) \equiv a^h \equiv (-1)^n \pmod p$.
11. Since $p \nmid a$, the Legendre symbol is $\pm 1$. Two signs that agree modulo $p \ge 3$ are equal. So $\left(\frac{a}{p}\right) = (-1)^n$.