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.

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.

Pour tester la primalité d'un nombre

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
Cet article, publié dans Arithmétique, est tagué , , , , . Ajoutez ce permalien à vos favoris.

8 commentaires pour Le théorème de Wilson

  1. Ping : Le cadeau de Noël de Fermat | Blogdemaths

  2. Anonyme dit :

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

  3. Anonyme dit :

    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

  4. Maths dit :

    Efficace et simple

  5. Ping : Comment reconnaître deux nombres premiers jumeaux ? | Blogdemaths

  6. César dit :

    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.

Laisser un commentaire

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

Logo WordPress.com

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

Image Twitter

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

Photo Facebook

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

Photo Google+

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

Connexion à %s