Problème — Le théorème de Wilson, et quand $-1$ est un carré modulo $p$

1) Chaque reste non nul a un inverse. Soit $a\in \{1,\dots ,p-1\}$. Comme $p$ est premier et ne divise pas $a$ (car $0<a<p$), on a $a\wedge p=1$. Par le théorème du cours sur l'inversibilité modulo $n$, il existe $u\in \mathbb{Z}$ tel que $au\equiv 1[p]$, et cet inverse est unique modulo $p$. Soit $a^{\prime }$ le reste de $u$ dans la division par $p$ : $a^{\prime }\in \{0,\dots ,p-1\}$ et $a{a}^{\prime }\equiv au\equiv 1[p]$. Enfin $a^{\prime }\ne 0$, sinon $a{a}^{\prime }=0\equiv 1[p]$ imposerait $p\mid 1$. Donc $a^{\prime }\in \{1,\dots ,p-1\}$, et il est unique dans cet ensemble : deux éléments de $\{1,\dots ,p-1\}$ congrus modulo $p$ sont égaux. Chaque $a$ a un unique inverse $a^{\prime }$ dans $\{1,\dots ,p-1\}$, et l'on remarque que $(a^{\prime }{)}^{\prime }=a$ : l'application $a\mapsto a^{\prime }$ est une involution de $\{1,\dots ,p-1\}$.

2) Les éléments qui sont leur propre inverse. $a^{\prime }=a$ si et seulement si $a^2\equiv 1[p]$, si et seulement si $p\mid a^2-1=(a-1)(a+1)$. Comme $p$ est premier, s'il divise le produit $(a-1)(a+1)$, il divise l'un des facteurs : en effet, si $p\nmid a-1$, alors $p\wedge (a-1)=1$ et le lemme de Gauss donne $p\mid a+1$. Donc $a^{\prime }=a$ si et seulement si $a\equiv 1[p]$ ou $a\equiv -1[p]$, c'est-à-dire, dans $\{1,\dots ,p-1\}$, si et seulement si $a=1$ ou $a=p-1$.

Le point délicat. C'est la primalité de $p$ qui donne « un produit nul modulo $p$ a un facteur nul modulo $p$ ». Modulo $8$, par exemple, $3^2=9\equiv 1$ et $5^2=25\equiv 1$ : il y a quatre éléments qui sont leur propre inverse, et le théorème qui suit tombe.

3) Le théorème de Wilson. L'ensemble $E=\{2,\dots ,p-2\}$ a $p-3$ éléments, nombre pair puisque $p$ est impair (il est vide pour $p=3$). Par le 1) et le 2), l'involution $a\mapsto a^{\prime }$ envoie $E$ dans $E$ (si $a\in E$, alors $a^{\prime }\ne 1$, sinon $a\equiv 1$, et $a^{\prime }\ne p-1$, sinon $a\equiv -1$) et n'y a aucun point fixe. Elle partage donc $E$ en $\frac{p-3}{2}$ paires $\{a,a^{\prime }\}$ disjointes, chacune de produit $a{a}^{\prime }\equiv 1[p]$. Le produit de tous les éléments de $E$ est donc congru à $1$, et $$(p-1)!=1\times (\prod _{a\in E}a)\times (p-1)\equiv 1\times 1\times (-1)=-1[p].$$ Pour tout premier impair $p$, $(p-1)!\equiv -1[p]$ — et c'est vrai aussi pour $p=2$ : $1!=1\equiv -1[2]$. Vérification : pour $p=7$, les paires sont $\{2,4\}$ et $\{3,5\}$ ($2\times 4=8\equiv 1$, $3\times 5=15\equiv 1$), et $6!=720=7\times 103-1$. Pour $p=11$ : $\{2,6\}$, $\{3,4\}$, $\{5,9\}$, $\{7,8\}$, et $10!=3628800=11\times 329891-1$.

4) La réciproque. Soit $n\ge 4$ non premier : $n=ab$ avec $2\le a\le b<n$.

Si $a<b$. Alors $a$ et $b$ sont deux facteurs distincts du produit $(n-1)!=1\times 2\times \cdots \times (n-1)$, puisque $2\le a<b\le n-1$ : $ab=n$ divise $(n-1)!$, et $(n-1)!\equiv 0[n]$.

Si $a=b$, c'est-à-dire $n=a^2$. Si $a\ge 3$, alors $a$ et $2a$ sont deux entiers distincts, tous deux inférieurs à $n-1$ (car $2a\le a^2-1$ équivaut à $a^2-2a-1\ge 0$, vrai pour $a\ge 3$) : ils sont deux facteurs distincts de $(n-1)!$, donc $a\cdot 2a=2n$ divise $(n-1)!$, et a fortiori $n$ le divise : $(n-1)!\equiv 0[n]$. Reste $a=2$, $n=4$ : $3!=6\equiv 2[4]$, qui n'est ni $0$ ni $-1\equiv 3$.

Conclusion. Pour $n\ge 2$ : si $n$ est premier, $(n-1)!\equiv -1[n]$ par le 3) ; si $n$ est composé, $(n-1)!$ est congru à $0$ (pour $n\ne 4$) ou à $2$ (pour $n=4$) modulo $n$, jamais à $-1$ (car $0\equiv -1[n]$ exigerait $n\mid 1$). Un entier $n\ge 2$ est premier si et seulement si $(n-1)!\equiv -1[n]$ : c'est le théorème de Wilson, et il caractérise les nombres premiers — un test de primalité exact, mais inutilisable en pratique, car $(n-1)!$ est bien trop gros.

5) $-1$ est un carré quand $p\equiv 1[4]$. Écrivons $p=4m+1$ ; alors $\frac{p-1}{2}=2m$ est pair. Les entiers de $1$ à $p-1$ se répartissent en les paires $\{k,p-k\}$ pour $k=1,\dots ,\frac{p-1}{2}$ (chaque entier de $\{1,\dots ,p-1\}$ apparaît dans exactement une paire, puisque $k\le \frac{p-1}{2}$ équivaut à $p-k\ge \frac{p+1}{2}$). Donc $$(p-1)!=\prod _{k=1}^{(p-1)/2}k(p-k).$$ Or $p-k\equiv -k[p]$, et par compatibilité des congruences avec les produits, $$(p-1)!\equiv \prod _{k=1}^{(p-1)/2}k(-k)=(-1{)}^{(p-1)/2}{\left(\prod _{k=1}^{(p-1)/2}k\right)}^2=(-1{)}^{2m}{x}^2=x^2[p].$$ Avec le théorème de Wilson, $x^2\equiv (p-1)!\equiv -1[p]$ : $-1$ est un carré modulo $p$. Exemple : $p=13$, $x=6!=720=55\times 13+5\equiv 5$, et $5^2=25=2\times 13-1\equiv -1[13]$.

6) Et jamais quand $p\equiv 3[4]$. Écrivons $p=4m+3$, de sorte que $\frac{p-1}{2}=2m+1$ est impair. Supposons qu'un entier $x$ vérifie $x^2\equiv -1[p]$. Alors $p\nmid x$ (sinon $x^2\equiv 0$, et $-1\equiv 0$ imposerait $p\mid 1$). Par le petit théorème de Fermat, $x^{p-1}\equiv 1[p]$. Mais $$x^{p-1}={\left(x^2\right)}^{(p-1)/2}\equiv (-1{)}^{2m+1}=-1[p].$$ Donc $1\equiv -1[p]$, soit $p\mid 2$, impossible pour $p$ impair. Aucun entier n'a pour carré $-1$ modulo un premier $p\equiv 3[4]$.

Les diviseurs premiers de $m^2+1$. Soit $q$ un diviseur premier impair de $m^2+1$. Alors $m^2\equiv -1[q]$ : $-1$ est un carré modulo $q$, donc, par ce qui précède, $q\not\equiv 3[4]$. Un premier impair est congru à $1$ ou à $3$ modulo $4$ : $q\equiv 1[4]$.

L'infinité, à la manière d'Euclide. Supposons qu'il n'y ait qu'un nombre fini de nombres premiers congrus à $1$ modulo $4$, notés $p_1,\dots ,p_k$, et posons $N=(2p_1{p}_2\cdots p_k{)}^2+1$. L'entier $N$ est impair (carré d'un pair, plus $1$) et vaut au moins $5$ : il admet un diviseur premier $q$, nécessairement impair. Par ce qui précède, $q\equiv 1[4]$, donc $q$ est l'un des $p_i$. Mais alors $q$ divise $(2p_1\cdots p_k{)}^2$ et $q$ divise $N$, donc $q$ divise leur différence $1$ : absurde. Il existe une infinité de nombres premiers congrus à $1$ modulo $4$.

Les théorèmes obtenus.

Théorème de Wilson (1770, démontré par Lagrange en 1771). Un entier $n\ge 2$ est premier si et seulement si $(n-1)!\equiv -1[n]$.

Corollaire. Pour $p$ premier impair, $-1$ est un carré modulo $p$ si et seulement si $p\equiv 1[4]$ ; et il existe une infinité de nombres premiers congrus à $1$ modulo $4$.

Ce que le problème installe. Modulo un nombre premier, on peut diviser — chaque reste non nul a un inverse — et c'est cette propriété, combinée au lemme de Gauss, qui rend possible l'appariement de Wilson. Le corollaire montre la méthode reine pour décider si une équation modulo $p$ a des solutions : élever à la puissance $\frac{p-1}{2}$ et comparer à Fermat. Et l'argument d'Euclide, adapté à une classe de congruence, est le premier pas vers un théorème de deuxième année et au-delà : il existe une infinité de nombres premiers dans toute classe $a$ modulo $n$ dès que $a\wedge n=1$ (Dirichlet) — hors programme, mais le cas $1$ modulo $4$ vient d'être établi avec les seuls outils du chapitre.