Théorie > Théorie des nombres > Arithmétique modulaire


Général

Introduction Chapitre entier

Points théoriques

Définition Propriétés Exemple d'utilisation Critères de divisibilité Théorème de Wilson

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6 Exercice 7

Théorème de Wilson

Pour conclure ce chapitre, énonçons le théorème de Wilson :

Un nombre $p \geq 2$ est premier si et seulement si
$$(p-1)! \equiv -1 \pmod {p}.$$

Ce théorème est en fait un critère permettant de déterminer si un nombre est premier ou non. Cela peut paraître exceptionnel (on dit généralement qu'il est très difficile de déterminer si un nombre est premier), mais ce critère n'est en fait pas miraculeux. En effet, pour savoir si le nombre $101$ est premier, il faudrait calculer $100!$ et le diviser par $101$ pour voir si le reste obtenu est $-1$ ou non. On ne peut pas dire que cela soit très efficace, il est encore plus court de tester les différents diviseurs possibles de $101$.

Si ce théorème n'est pas utile d'un point de vue algorithmique, il arrive cependant qu'il permette de résoudre des problèmes d'olympiades, et il ne faut dès lors pas le perdre de vue.

Démonstration :
Nous n'allons pas démontrer ce théorème entièrement : cela nécessite la connaissance des inverses modulo $p$ (que l'on introduira un peu plus tard). Un des sens de l'équivalence est cependant facile à prouver : si $(p-1)! \equiv -1 \pmod p$, alors $p$ est forcément premier. En effet, si $p$ n'était pas premier, il aurait un diviseur $q < p$. Le nombre $q$ apparaitrait alors dans la factorielle $(p-1)! = 1 \cdot \ldots \cdot (p-1)$, et celle-ci serait donc divisible par $q$. Cela contredit l'hypothèse, puisqu'on a supposé que $p$ (et donc $q$) divisait $(p-1)! + 1$.