Le théorème de Wilson

Après avoir évoqué le théorème d’Euler ou encore le théorème des restes Chinois, je vous propose de poursuivre notre route sur le chemin des grands théorèmes de l’arithmétique élémentaire en parlant du théorème de Wilson. Mon but avec cette série d’articles est d’une part de rendre l’arithmétique plus accessible, et d’autre part de donner des démonstrations simples, qui contournent les preuves abstraites issues de la théorie des groupes, qui, aussi belles et élégantes soient-elles, ne font pas vraiment comprendre la nature profonde de ces théorèmes.

Sir John Wilson, posant aux côtés de ses deux caniches. (source: https://fr.wikipedia.org/wiki/John_Wilson_(math%C3%A9maticien))

Sir John Wilson, posant aux côtés de ses deux caniches. (source: Wikipedia)

Que dit le théorème de Wilson ?

Donnons sans plus attendre l’énoncé du théorème de Wilson:

Soit $p$ un entier naturel.
Le nombre $p$ est premier si, et seulement si, $(p-1)! \equiv - 1 \mod[p]$

Autrement dit, ce théorème affirme qu’un nombre $p$ est premier si, et seulement si, le nombre $(p-1)! + 1$ est divisible par $p$ .

Le théorème de Wilson est remarquable car c’est l’un des rares critères simples (avec la méthode naïve des divisions successives) permettant de dire avec certitude si un nombre est premier ou non. Malheureusement, il est peu utile en pratique ! Mais nous en reparlerons… Pour l’instant, donnons-en deux exemples:

Exemple 1 ― Si on prend $p=7$ , qui est premier alors $(p-1)! = 6 ! = 720$ et en calculant le reste de la division de 720 par 7, on obtient 6 (car 720 = 7 $\times$ 102 + 6). Comme 6 et -1 diffèrent d’un multiple de 7, on trouve bien $(7-1)! \equiv 6 \equiv -1 \mod[7]$ , comme nous l’annonçait le sens direct du théorème de Wilson.

Exemple 2 ― Prenons le nombre $p=8$ , qui n’est pas premier. En calculant $(p-1)!$ , on obtient 7! = 5 040, qui est divisible par 8 ( $5040= 8 \times 630$ ). Ainsi, $(8-1)! \equiv 0 \mod[8]$ qui est donc différent de -1 (ah bon ?). On a bien vérifié la réciproque du théorème (sous la forme de sa contraposée).

« We need to go deeper! »

Ces deux exemples sont bien beaux et illustrent parfaitement ce théorème mais ne nous font pas vraiment comprendre les rouages de celui-ci. Je vous propose donc d’approfondir chacun de ces exemples pour en tirer la substantifique moelle.

Exemple 1, Acte 2 ― On reprend $p=7$ , et au lieu de calculer directement le nombre $6!$ , nous allons sadiquement le décortiquer. Rappelons auparavant que:

$6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$

Pour calculer ce produit modulo 7, on a le droit de regrouper les termes dans l’ordre que l’on souhaite. Cela va nous être utile car, comme on va le voir, certains nombres se marient bien ensemble ! Par exemple, prenons les nombres 2 et 4. Leur produit vaut 8, qui est congru à 1 modulo 7. Ainsi, nous voyons qu’en regroupant 2 avec 4, nous pouvons les « simplifier ». On peut aussi regrouper 3 avec 5 car $3 \times 5 = 15 \equiv 1 \mod[7]$ . En revanche, on ne peut pas regrouper 1 avec 6 car $1 \times 6 = 6 \not\equiv 1 \mod[7]$ mais le calcul de (7-1)! est tout de même bien plus simple à présent:

$(7-1)! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = (2 \times 4) \times (3 \times 5) \times 1 \times 6$

donc

$(7-1)! \equiv (1) \times (1) \times 1 \times 6 = 6 \equiv -1 \mod[7]$

Nous voyons ici l’idée principale du théorème de Wilson: si $p$ est premier, on peut regrouper les nombres 2, 3, … , $p-2$ deux à deux de façon à ce que le produit de chaque paire de nombres vaille 1 modulo $p$ .

Lorsque p est premier, on peut regrouper deux à deux les facteurs de (p-1)! sauf 1 et p-1 de sorte que le produit de chaque couple de nombres soit égal à 1 modulo p.

Et si $p$ n’est pas premier, quelle est l’idée ? Pour cela reprenons l’exemple 2.

Exemple 2, Acte 2 ― On avait pris $p=8$ . Comme 8 n’est pas premier, on peut le décomposer comme le produit de deux nombres strictement compris entre 1 et 8: $8 = 2 \times 4$ . Il se trouve alors que 2 et 4 vont apparaître comme facteurs dans le nombre $(8-1)!$ . En effet, comme

$(8-1)! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7$

nous pouvons regrouper 2 et 4:

$(8-1)! = (2 \times 4) \times 1 \times 3 \times 5 \times 6 \times 7 = 8 \times 1 \times 3 \times 5 \times 6 \times 7$

et cela prouve que $(8-1)!$ est divisible par 8 et ne peut donc pas être congru à -1 modulo 8. Voilà, vous avez les idées principales en tête; nous sommes prêts à prouver le théorème dans sa généralité !

Preuve du sens direct

Commençons par démontrer la première implication du théorème de Wilson:

Si $p$ est premier, alors $(p-1)! \equiv -1 \mod [p]$ .

Nous avions dit que l’idée était qu’on pouvait regrouper les facteurs de $(p-1)!$ deux à deux, ce qui se traduit par la proposition suivante:

Propriété 1 ― Si $p$ est premier et si $a \in \{1, 2, ... , p-1\}$ alors il existe un unique nombre $b$ (modulo $p$ ) tel que $ab \equiv 1 \mod [p]$ .

Preuve: Commençons par l’existence. Comme $p$ est premier, il ne partage aucun diviseur en commun avec tout nombre $a$ tel que $1 \leq a \leq p-1$ . Ainsi, $p$ et $a$ sont premiers entre eux, et d’après le théorème de Bézout, il existe deux nombres $b$ et $m$ tels que $ab + mp = 1$ ce qui veut bien dire que $ab \equiv 1 \mod[p]$ .
Passons à l’unicité: s’il existe deux nombres $b$ et $b'$ tels que $ab \equiv 1 \mod[p]$ et $ab' \equiv 1 \mod[p]$ , il s’agit de montrer que $b \equiv b' \mod[p]$ (ce qui montrera l’unicité modulo $p$ ). En multipliant la deuxième relation par $b$ , on obtient $bab' \equiv b \mod[p]$ et comme $ba =ab \equiv 1 \mod[p]$ , on a donc $1 \times b' \equiv b \mod[p]$ . CQFD.

Nous venons de prouver qu’on peut regrouper les nombres par paires, mais la propriété 1 n’est pas suffisante ! En effet, il se peut que certains nombres ne puissent être regroupés qu’avec eux-mêmes ! Par exemple, le seul nombre $b$ qui peut être regroupé avec le nombre 1 est le nombre 1 lui-même ( $1 \times b \equiv 1 \mod[p]$ implique $b\equiv 1 \mod[p]$ ). Pour compléter la propriété 1, il faut donc en plus étudier tous les nombres qu’on ne peut regrouper qu’avec eux-mêmes, autrement dit, tous les nombres $a$ tels que $a \times a \equiv 1 \mod[p]$

Propriété 2 ― Si $p$ est premier, alors $a \times a \equiv 1 \mod[p]$ si, et seulement si, $a \equiv 1 \mod[p]$ ou $a \equiv p-1 \mod[p]$ .

Preuve: On a les équivalences:

$a \times a \equiv 1 \mod[p] \Longleftrightarrow a^2 - 1 \equiv 0 \mod[p]\Longleftrightarrow (a-1)(a+1) \equiv 0 \mod[p]$

Cela signifie que $p$ divise le produit $(a-1)(a+1)$ . Comme $p$ est premier, le lemme d’Euclide dit que $p$ divise $a-1$ ou bien $p$ divise $a+1$ . Autrement dit,

$a \equiv 1 \mod[p] \text{ ou } a \equiv -1 \mod[p]$

ce qui prouve bien la propriété 2 car $-1 \equiv p-1 \mod[p]$ .

Nous pouvons donc démontrer le sens direct du théorème de Wilson: si $p$ est premier, alors on peut regrouper tous les facteurs de $(p-1)!$ deux à deux de sorte que le produit de chaque paire vaille 1 modulo $p$ (propriété 1) sauf 1 et p-1 (propriété 2). Ainsi,

$(p-1)! \equiv 1 \times (p-1) = (p-1) \equiv - 1 \mod[p]$

La raie si propre

Passons maintenant à la deuxième implication du théorème de Wilson. Mais plutôt que de prouver cette réciproque, à savoir: « Si $(p-1)! \equiv -1 \mod[p]$ alors $p$ est premier », nous allons démontrer sa contraposée:

Si $p$ n’est pas premier, alors $(p-1)! \not\equiv -1 \mod[p]$

Commençons par le cas $p=4$ (que j’appelle personnellement, le-cas-qui-fait-chier-son-monde-à-ne-pas-vouloir-faire-comme-les-autres). Dans ce cas, $(p-1)! = 3! = 6$ et et il est facile de vérifier que $6 \equiv 2 \not\equiv -1 \mod[4]$ .

A présent, soit $p>4$ un nombre qui n’est pas premier. On sait dans ce cas que $p$ s’écrit comme le produit $p = a \times b$ de deux nombres tels que $1 < a, b < p-1$ . Il y a deux cas à distinguer:

■ 1er cas: Si on peut prendre $a$ et $b$ tels que $a \neq b$ alors, comme dans l’exemple avec $p=8$ du début de l’article, on peut regrouper $a$ et $b$ dans le produit de $(p-1)!$ de sorte que $p=ab$ divise $(p-1)!$ . Ainsi, $(p-1) ! \equiv 0 \mod[p]$ et donc n’est pas égal à -1.

■ 2ème cas: Si $a=b$ (autrement dit, $p$ est le carré d’un nombre premier, par exemple 25, 49 ou encore 121…) alors $p=a^2$ . Comme $p>4$ , alors $a>2$ et donc $p=a^2>2a$ (vous comprenez maintenant pourquoi j’ai écarté le cas $p=4$ ). Ainsi, les nombres $a$ et $2a$ apparaissent comme facteurs dans $(p-1)!$ qui est donc divisible par $a \times 2a$ . En particulier, $(p-1)!$ est divisible par $a \times a = a^2 = p$ ce qui montre que $(p-1)! \equiv 0 \mod[p]$ et qui est donc différent de -1.

Voilà, nous venons de prouver entièrement le théorème de Wilson. En fait, nous avons prouvé mieux:

$(p-1)! \equiv \begin{cases} -1 \mod[p] & \text{ si } p \text{ est premier} \\ 2 \mod[p] & \text{ si } p=4 \\ 0 \mod[p] & \text{ sinon } \end{cases}$

Wilson, en pratique

Le théorème de Wilson permet donc théoriquement de dire si un nombre est premier ou non. Mais en pratique, il ne sert à rien: essayez par exemple de montrer à la main que des nombres aussi petits que 41 ou 43 sont premiers à l’aide du théorème de Wilson et cela vous prendra déjà un certain temps. Même avec un ordinateur, ce théorème prendra toujours plus de temps que la méthode naïve des divisions successives.

Victoire par KO des divisions successives. Le code utilisé pour ces fonctions est disponible ici

Le théorème de Wilson a donc surtout un intérêt théorique; il permet notamment de montrer que -1 est un carré modulo $p$ si $p$ est congru à un 1 modulo 4 (propriété que nous avions utilisée dans cet article sur la décomposition en somme de deux carrés). Mais en fait, j’ai envie de dire que même s’il n’avait aucun intérêt du tout, ce théorème mérite d’être étudié pour lui-même, ne serait-ce que pour le plaisir de faire de l’arithmétique !

Publicités

8 commentaires pour Le théorème de Wilson

Ping : Le cadeau de Noël de Fermat | Blogdemaths
Anonyme dit :

26 octobre 2015 à 20 h 21 min

Toujours aussi bien écrit avec d’excellentes références musicales (cherchez l’erreur). Merci !

Réponse
- blogdemaths dit :
  
  26 octobre 2015 à 21 h 26 min
  
  Merci 😉 Je compte faire encore mieux pour les prochains articles (je veux dire musicalement, bien sûr !)
  
  Réponse
Anonyme dit :

29 novembre 2015 à 14 h 45 min

Bonjour,
Il me semble qu’on peut faire plus simple pour le sens (p-1)! = -1 [p] => p premier.
Supposons (p-1)! = -1 [p] ie p divise (p-1)!+1. Soit x un diviseur de p strictement plus petit que p.
x divise p qui divise (p-1)!+1 mais aussi x divise (p-1)! car x <= p-1 donc x divise ((p+1)! + 1 – (p+1)!) et x = 1 ce qui prouve que p est premier

Réponse
- blogdemaths dit :
  
  29 novembre 2015 à 21 h 36 min
  
  Tout à fait ! Bien vu 🙂
  
  Réponse
Maths dit :

14 juin 2016 à 13 h 31 min

Efficace et simple

Réponse
Ping : Comment reconnaître deux nombres premiers jumeaux ? | Blogdemaths
César dit :

24 février 2017 à 15 h 30 min

Près de la fin de la preuve, 2ème cas, il a écrit que p est le carré d’un nombre premier. Je ne comprends pas pourquoi premier et non un entier quelconque.

Réponse

Laisser un commentaire Annuler la réponse.

Entrez votre commentaire...

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

E-mail (adresse strictement confidentielle)

Nom

Site web

Vous commentez à l'aide de votre compte WordPress.com. ( Déconnexion / Changer )

Vous commentez à l'aide de votre compte Twitter. ( Déconnexion / Changer )

Vous commentez à l'aide de votre compte Facebook. ( Déconnexion / Changer )

Vous commentez à l'aide de votre compte Google+. ( Déconnexion / Changer )

Annuler

Connexion à %s