Wilson's test

Prenons le nombre 5. Multiplions tous les entiers positifs qui le précèdent : 1 × 2 × 3 × 4 donne 24. En ajoutant 1, on obtient 25, qui se partage exactement en cinq groupes de 5.

Le test de Wilson transforme cette observation en critère : pour un entier supérieur à 1, l'absence de reste indique un nombre premier. Le critère est exact, mais la longue multiplication le rend peu commode dès que le nombre grandit.

Le test de Wilson est un test de primalité déterministe fondé sur une caractérisation exacte. Soit n un entier strictement supérieur à 1. La factorielle de n − 1, notée (n − 1)!, est le produit de tous les entiers de 1 à n − 1. Le théorème de Wilson affirme l'équivalence suivante :

La congruence signifie que (n − 1)! + 1 est divisible par n, autrement dit que sa division par n laisse un reste nul. Le test consiste donc à calculer la factorielle, à ajouter 1, puis à examiner ce reste. Le verdict est sans ambiguïté dans le domaine n > 1 : un reste nul caractérise un nombre premier, et un reste non nul un nombre composé. Cette exactitude est surtout théorique, car le nombre de multiplications augmente avec n. Même en ne conservant que les restes successifs modulo n, la procédure demeure inefficace pour les grands entiers.

Nous voulons décider si 5 est premier. La chaîne de calcul rend visible le passage du candidat à un multiple exact de 5. Données.
Entier testé : n = 5.
Entiers à multiplier : 1, 2, 3 et 4.
Diviseur utilisé pour le contrôle : 5.

Étape 1. Multiplions les entiers positifs strictement inférieurs à 5 : 1 × 2 × 3 × 4 = 24. Ainsi, 4! = 24.

Étape 2. Ajoutons 1 au produit obtenu : 24 + 1 = 25.

Étape 3. Divisons ce résultat par l'entier testé : 25 ÷ 5 = 5, avec un reste égal à 0. Le critère de Wilson est donc satisfait, et 5 est premier.

Contrôle. Reprenons la même procédure avec 4 : 3! + 1 = 1 × 2 × 3 + 1 = 7. La division de 7 par 4 laisse un reste de 3 ; le critère échoue bien pour ce nombre composé.

À la main, le test illustre la primalité de petits entiers. Pour 5, on forme 4! + 1 puis on contrôle le reste modulo 5. Si une division directe par les petits diviseurs possibles demande moins d'opérations, elle constitue une vérification plus courte.

Dans un programme pédagogique, on peut multiplier successivement en ne gardant que le reste modulo n. Ce geste évite de stocker l'immense valeur de la factorielle, mais il exige toujours une succession de multiplications dont le nombre croît avec n.

Pour tester de grands entiers, on préfère un test de primalité conçu pour le calcul efficace. Le critère observable est le coût : lorsque parcourir presque tous les entiers jusqu'à n devient trop long, Wilson garde son rôle de caractérisation théorique plutôt que d'outil pratique.

Théorème de Wilson et test de Wilson. Le théorème est l'équivalence mathématique entre primalité et congruence factorielle. Le test est la procédure qui applique cette équivalence à un entier donné. Pour 5, l'égalité 4! + 1 = 25 relève du calcul du test ; la garantie que ce reste nul caractérise un nombre premier vient du théorème.

Test de Wilson et test de primalité. Un test de primalité est une catégorie de méthodes ; Wilson en est un cas particulier fondé sur la factorielle. Une procédure qui décide si 5 est premier sans calculer 4! reste un test de primalité, mais ce n'est pas le test de Wilson.

Le domaine commence à 2. La condition n > 1 est indispensable. Pour n = 1, toute division laisse formellement un reste nul, alors que 1 n'est pas premier. Il faut donc écarter ce cas avant d'appliquer le critère.

La valeur complète de la factorielle n'est pas nécessaire. Calculer les restes après chaque multiplication évite de manipuler (n − 1)! en entier gigantesque. Cette amélioration de stockage ne rend toutefois pas le test compétitif : il faut encore effectuer une longue suite de produits lorsque n est grand.

Le reste doit être celui de (n − 1)! + 1. Tester seulement si (n − 1)! est divisible par n change le critère. Pour n = 5, 4! laisse le reste 4, c'est-à-dire −1 modulo 5 ; c'est l'ajout de 1 qui produit le reste nul attendu.

nombre premier — Revenir à la propriété que le test de Wilson cherche à décider.

test de primalité — Situer le test de Wilson dans la famille des procédures qui décident la primalité.

arithmétique modulaire — Approfondir le calcul des restes qui formule et exécute le critère de Wilson.