Lemme d'Eisenstein

Pour $1 \leqslant k \leqslant P$, écrivons $ak = p\,q_k + t_k$ avec $q_k = \lfloor ak/p \rfloor$ et $0 \leqslant t_k < p$ ; on a $t_k \neq 0$, puisque $p$ ne divise pas $ak$. Avec les notations du lemme de Gauss (Lemme de Gauss), $r_k = t_k$ si $t_k \leqslant P$, et $r_k = t_k - p < 0$ si $t_k > P$ : le nombre $\mu$ est celui des indices $k$ tels que $t_k > P$.

Notons $A$ la somme des $t_k$ qui sont au plus $P$, et $B$ celle des $t_k$ qui dépassent $P$. En additionnant les égalités $ak = p\,q_k + t_k$, on obtient $$a\sum_{k=1}^P k = p\,S(a, p) + A + B.$$

Les $|r_k|$ sont les entiers $1, \dots, P$, chacun une fois (même nœud, (i)) ; ils valent $t_k$ dans le premier cas et $p - t_k$ dans le second, si bien que $$\sum_{k=1}^P k = A + \mu p - B.$$

En retranchant, $(a - 1)\sum_k k = p\,S(a, p) - \mu p + 2B$. Comme $a - 1$ est pair et $p$ impair, la réduction modulo $2$ donne $S(a, p) \equiv \mu \pmod 2$, et le lemme de Gauss conclut.