Théorème de Wilson
-
On résout l'équation de congruence :
\begin{align*}
x^2-1 &\equiv 0 \pmod p \\
(x-1)(x+1) &\equiv 0 \pmod p
\end{align*}
Puisque $p$ est un nombre premier, il divise le produit si et seulement s'il divise l'un des facteurs (lemme d'Euclide). Soit :
\[ x \equiv 1 \pmod p \quad \text{ou} \quad x \equiv -1 \pmod p \]
Autrement dit, les seules solutions modulo $p$ sont $x \equiv 1 \pmod p$ ou $x \equiv p-1 \pmod p$.
-
La question précédente montre que les seuls entiers $x \in \{1, \cdots, p-1\}$ qui sont égaux à leur propre inverse modulo $p$ sont $1$ et $p-1$.
Pour les autres entiers $x \in \{2, \cdots, p-2\}$, il existe un unique inverse $y \in \{2, \cdots, p-2\}$ tel que $x \neq y$ et $xy \equiv 1 \pmod p$.
L'ensemble $\{2, \cdots, p-2\}$ peut donc être partitionné en paires $(x,y)$ d'éléments distincts, chacun étant l'inverse de l'autre.
Par conséquent, le produit de tous ces éléments vaut $1$ modulo $p$ :
\[ 2 \times 3 \times \cdots \times (p-2) \equiv 1 \pmod p \]
Autrement dit :
\[ (p-2)! \equiv 1 \pmod p \qquad (*) \]
-
En multipliant l'égalité $(*)$ par $(p-1)$ :
\begin{align*}
(p-2)! \times (p-1) &\equiv 1 \times (p-1) \pmod p \\
(p-1)! &\equiv p-1 \pmod p
\end{align*}
Or, $p-1 \equiv -1 \pmod p$. On obtient donc le Théorème de Wilson :
\[ (p-1)! \equiv -1 \pmod p \]
-
Montrons par l'absurde la réciproque : si $(p-1)! \equiv -1 \pmod p$, alors $p$ est premier.
Supposons que $p$ n'est pas premier (c'est-à-dire $p$ composé) tout en vérifiant $(p-1)! \equiv -1 \pmod p$.
Soit $q$ le plus petit diviseur propre de $p$ (avec $q > 1$). Il existe un entier $d$ tel que $p = qd$. Puisque $q$ est le plus petit diviseur, on a nécessairement $q \le d$. Trois cas se présentent :
- Cas $q < d$ :
Les entiers $q$ et $d$ sont distincts et strictement compris entre $1$ et $p-1$. Ils apparaissent donc comme deux facteurs distincts dans le produit $(p-1)!$.
Leur produit $qd = p$ divise donc $(p-1)!$, ce qui implique :
\[ (p-1)! \equiv 0 \pmod p \]
C'est une contradiction avec notre hypothèse $(p-1)! \equiv -1 \pmod p$.
- Cas $q = d$ et $q > 2$ :
Dans ce cas, $p = q^2$. Puisque $q > 2$, on a $2q < q^2 = p$, soit $2q \le p-1$.
Les entiers $q$ et $2q$ sont distincts et apparaissent tous les deux dans le produit $(p-1)!$. Leur produit $q \times 2q = 2q^2 = 2p$ divise $(p-1)!$.
On a donc à nouveau $(p-1)! \equiv 0 \pmod p$. C'est une contradiction.
- Cas $q = d = 2$ :
Dans ce cas particulier, $p = 4$. On vérifie directement :
\[ (4-1)! = 3! = 6 \equiv 2 \pmod 4 \]
Puisque $2 \not\equiv -1 \pmod 4$, on aboutit à nouveau à une contradiction.
Dans tous les cas, l'hypothèse que $p$ est composé mène à une absurdité. On en déduit que $p$ est obligatoirement un nombre premier. L'équivalence du théorème de Wilson est ainsi démontrée.
Application : Démonstration du Petit Théorème de Fermat
Soit $a$ un entier tel que $a \land p = 1$. Soit $f$ la fonction définie par :
\begin{align*}
f : \mathbb{Z}/p\mathbb{Z} &\longrightarrow \mathbb{Z}/p\mathbb{Z} \\
\overline{k} &\longmapsto \overline{k} \cdot \overline{a}
\end{align*}
-
Montrons que $f$ est injective :
\begin{align*}
f(\overline{m}) = f(\overline{n}) &\implies \overline{m} \cdot \overline{a} = \overline{n} \cdot \overline{a} \\
&\implies (\overline{m} - \overline{n}) \cdot \overline{a} = \overline{0}
\end{align*}
Puisque $p$ est premier, $\mathbb{Z}/p\mathbb{Z}$ est un corps (il n'y a pas de diviseur de zéro). On a donc :
\[ \overline{m} - \overline{n} = \overline{0} \quad \text{ou} \quad \overline{a} = \overline{0} \]
Or, $a \land p = 1$, donc $\overline{a} \neq \overline{0}$. Par conséquent, $\overline{m} = \overline{n}$.
La fonction $f$ est injective. Étant une application d'un ensemble fini dans lui-même, $f$ est donc une bijection.
-
Puisque $f(\overline{0}) = \overline{0}$, la restriction de $f$ aux éléments non nuls est une bijection de $(\mathbb{Z}/p\mathbb{Z})^*$ dans lui-même.
L'ensemble des images est égal à l'ensemble de départ :
\[ \{\overline{1}\cdot\overline{a}, \overline{2}\cdot\overline{a}, \cdots, (\overline{p-1})\cdot\overline{a}\} = \{\overline{1}, \overline{2}, \cdots, \overline{p-1}\} \]
En faisant le produit de tous les éléments de ces deux ensembles, on conserve l'égalité :
\begin{align*}
(\overline{1}\cdot\overline{a}) \times (\overline{2}\cdot\overline{a}) \times \cdots \times ((\overline{p-1})\cdot\overline{a}) &= \overline{1} \times \overline{2} \times \cdots \times \overline{p-1} \\
(\overline{1} \times \overline{2} \times \cdots \times \overline{p-1}) \times \overline{a}^{p-1} &= \overline{(p-1)!} \\
\overline{(p-1)!} \cdot \overline{a}^{p-1} &= \overline{(p-1)!} \qquad (**)
\end{align*}
Conclusion via le Théorème de Wilson :
D'après le théorème de Wilson, $(p-1)! \equiv -1 \pmod p$. L'équation $(**)$ devient :
\begin{align*}
-\overline{1} \cdot \overline{a}^{p-1} &= -\overline{1} \\
\overline{a}^{p-1} &= \overline{1}
\end{align*}
Soit : $a^{p-1} \equiv 1 \pmod p$.
N.B : Conclusion directe (sans Wilson) :
L'égalité $(**)$ peut s'écrire :
\[ \overline{(p-1)!} \cdot (\overline{a}^{p-1} - \overline{1}) = \overline{0} \]
Or, $(p-1)!$ est un produit d'éléments non nuls dans un corps, il est donc inversible (et non congru à $0$ modulo $p$). On peut simplifier par $\overline{(p-1)!}$, ce qui donne immédiatement :
\[ \overline{a}^{p-1} - \overline{1} = \overline{0} \implies a^{p-1} \equiv 1 \pmod p \]