Lemme de Gauss et seconde loi complémentaire

(i) Comme $p$ ne divise ni $a$ ni $k$, il ne divise pas $ak$ (lemme d'Euclide, Nombres premiers, (i)) : $r_k \neq 0$, et $|r_k| \in \{1, \dots, P\}$.

Si $|r_k| = |r_l|$, alors $ak \equiv \pm al$, et, la classe de $a$ étant inversible (Fermat, Euler, (i)), $k \equiv \pm l \pmod p$. Or $2 \leqslant k + l \leqslant p - 1$, si bien que $p$ ne divise pas $k + l$ : c'est donc $k \equiv l$, et $k = l$, puisque $|k - l| < p$. L'application $k \mapsto |r_k|$, injective de $\{1, \dots, P\}$ dans lui-même, en est une bijection.

En multipliant les congruences $ak \equiv r_k$ pour $k = 1, \dots, P$, on obtient $$\begin{aligned} a^P\,P! &\equiv \prod_{k=1}^P r_k = (-1)^\mu \prod_{k=1}^P |r_k| \\ &= (-1)^\mu\,P! \pmod p. \end{aligned}$$

L'entier $P!$, produit d'entiers compris entre $1$ et $p - 1$, n'est pas divisible par $p$, et sa classe est inversible : $a^P \equiv (-1)^\mu$. Le critère d'Euler (Symbole de Legendre, (ii)) donne $\big(\frac ap\big) \equiv (-1)^\mu$, et ces deux nombres, qui valent $\pm 1$, sont égaux.

(ii) Pour $a = 2$ et $1 \leqslant k \leqslant P$, l'entier $2k$ est compris entre $2$ et $p - 1$. Si $2k \leqslant P$, alors $r_k = 2k > 0$ ; si $2k > P$, alors $r_k = 2k - p$, compris entre $-P$ et $-1$. Il y a $\lfloor P/2 \rfloor$ indices de la première sorte, où $\lfloor P/2 \rfloor$ est le quotient de la division euclidienne de $P$ par $2$, d'où $\mu = P - \lfloor P/2 \rfloor$.

Écrivons $p = 8m + j$ avec $j \in \{1, 3, 5, 7\}$ et $c = \frac{j-1}2 \in \{0, 1, 2, 3\}$. Alors $P = 4m + c$ et $\mu = 2m + c - \lfloor c/2 \rfloor$, qui vaut $2m$, $2m + 1$, $2m + 1$ et $2m + 2$ pour $c = 0, 1, 2, 3$ : $\mu$ est pair si et seulement si $j = 1$ ou $j = 7$.

De même, pour $p = 8m \pm 1$, l'entier $\frac{p^2 - 1}8 = 8m^2 \pm 2m$ est pair, et pour $p = 8m \pm 3$, l'entier $\frac{p^2 - 1}8 = 8m^2 \pm 6m + 1$ est impair. Les deux exposants ont la même parité, et (i) conclut.