Proof of Eisenstein's lemma

Proof

1. Let $p$ be an odd prime, $a$ a positive integer with $p \nmid a$, and $h = (p-1)/2$. Let $E = \set{2, 4, \dots, p - 1}$, a set of $h$ even numbers.
2. For $u \in E$, let $r(u)$ be the least positive residue of $au$ modulo $p$. By Euclid's lemma, $p \nmid au$, so $1 \le r(u) \le p - 1$.
3. Let $e(u) = r(u)$ if $r(u)$ is even, and $e(u) = p - r(u)$ if $r(u)$ is odd. In both cases $e(u)$ is even with $1 \le e(u) \le p - 1$, because $p$ is odd. So $e(u) \in E$.
4. In both cases $r(u) \equiv (-1)^{r(u)} e(u) \pmod p$.
5. The map $u \mapsto e(u)$ is injective on $E$. Suppose $e(u) = e(v)$. Then $r(u) \equiv \pm r(v)$, so $au \equiv \pm av$, and $p \mid u - v$ or $p \mid u + v$ by Euclid's lemma.
6. Here $\abs{u - v} < p$. Also $u + v$ is even with $4 \le u + v \le 2p - 2$, and the only multiple of $p$ in this range is the odd number $p$. So $u - v = 0$.
7. Since $E$ is finite, $u \mapsto e(u)$ is a bijection of $E$. So $\prod_{u \in E} e(u) = \prod_{u \in E} u$.
8. By step 4 and products of congruences, $a^h \prod_{u \in E} u = \prod_{u \in E} au \equiv \prod_{u \in E} r(u) \equiv (-1)^{\sum_u r(u)} \prod_{u \in E} u \pmod p$.
9. Each $u \in E$ is less than $p$, so $p \nmid \prod_{u \in E} u$ by Euclid's lemma. Hence $a^h \equiv (-1)^{\sum_u r(u)} \pmod p$.
10. By the division algorithm, $au = p q(u) + r(u)$ with $q(u) = \lfloor au/p \rfloor$, since $0 < r(u) < p$ and the floor function picks the integer part.
11. Here $au$ is even and $p$ is odd. So $0 \equiv q(u) + r(u) \pmod 2$, and $r(u) \equiv q(u) \pmod 2$. Thus $(-1)^{\sum_u r(u)} = (-1)^{\sum_u \lfloor au/p \rfloor}$.
12. By Euler's criterion, $\left(\frac{a}{p}\right) \equiv a^h \equiv (-1)^{\sum_u \lfloor au/p \rfloor} \pmod p$.
13. Both sides are $\pm 1$, since $p \nmid a$ and by the definition of the Legendre symbol. Two signs that agree modulo $p \ge 3$ are equal, which proves the lemma.