Euclid's theorem
Le théorème d'Euclide est un résultat fondamental d'arithmétique qui affirme qu'il existe une infinité de nombres premiers. Ce théorème figure dans les Éléments d'Euclide, à la proposition 20 du livre IX. La démonstration classique procède par l'absurde : en supposant que la liste des nombres premiers est finie, on construit un entier qui n'est divisible par aucun d'eux, aboutissant à une contradiction. La preuve repose sur le fait que tout entier naturel supérieur à 1 admet au moins un diviseur premier, résultat établi aux propositions 31 et 32 du livre VII des Éléments.
Contents
What you will learn
- Énoncer précisément l’infinité des nombres premiers.
- Refaire la construction du produit augmenté de 1 sur l’exemple 2, 3, 5 et 7.
- Expliquer pourquoi le nouvel entier n’est divisible par aucun nombre de la liste.
- Éviter de croire que le produit augmenté de 1 est toujours premier.
In plain terms
Écrivez une liste de nombres premiers, par exemple 2, 3, 5 et 7. Multipliez-les, puis ajoutez 1 : vous obtenez 211. Aucun nombre de la liste ne divise 211, car la division laisse toujours un reste de 1.
Si cette liste avait contenu tous les nombres premiers, 211 devrait pourtant posséder un diviseur premier pris dans la liste. Cette impossibilité révèle l’idée du théorème d’Euclide : une liste finie de nombres premiers ne peut jamais être complète.
Definition
Le théorème d’Euclide est le résultat d’arithmétique selon lequel il existe une infinité de nombres premiers. Autrement dit, quel que soit le nombre de nombres premiers déjà réunis, il en existe au moins un autre qui n’appartient pas à cette liste.
La preuve classique suppose au contraire qu’il existe une liste finie complète. On note ses nombres premiers , puis on forme l’entier . Pour chaque nombre de la liste, la division de par laisse un reste égal à 1. Aucun nombre premier annoncé ne divise donc .
Or est supérieur à 1 et admet au moins un diviseur premier. Ce diviseur manque à la liste supposée complète : la contradiction établit que les nombres premiers sont en quantité infinie.
The principle
Si l’on considère n’importe quelle liste finie de nombres premiers, alors il existe un nombre premier qui ne figure pas dans cette liste. En effet, si les nombres de la liste sont notés , l’entier suivant n’est divisible par aucun d’eux :
Comme cet entier supérieur à 1 possède un diviseur premier, ce diviseur est un nombre premier absent de la liste. Il n’existe donc aucune liste finie complète des nombres premiers.
When to use it
Le raisonnement porte sur une liste finie de nombres qui sont tous premiers. Pour obtenir la contradiction, on suppose en plus que cette liste contient tous les nombres premiers. Le produit de ses termes, augmenté de 1, est alors supérieur à 1 ; il possède donc au moins un diviseur premier.
Si la liste 2, 3, 5 et 7 est présentée comme une simple sélection, trouver un diviseur premier absent ne crée aucune contradiction : personne n’a affirmé que la sélection était complète. Il faut alors conclure seulement qu’un nouveau nombre premier a été trouvé, et non que l’hypothèse d’une liste finie complète a déjà été réfutée.
A step-by-step example
Supposons, pour mener le raisonnement par l’absurde, que 2, 3, 5 et 7 forment la liste complète des nombres premiers. Les données sont donc les quatre nombres premiers 2, 3, 5 et 7.
1. Multiplier les nombres de la liste : 2 × 3 × 5 × 7 = 210.
2. Ajouter 1 au produit : 210 + 1 = 211.
3. Diviser 211 par chaque nombre de la liste : chaque division laisse un reste de 1.
2. Ajouter 1 au produit : 210 + 1 = 211.
3. Diviser 211 par chaque nombre de la liste : chaque division laisse un reste de 1.
Le calcul qui concentre la construction est : . La figure rend visibles le produit, l’ajout de 1 et les quatre restes.
4. Puisque 211 est supérieur à 1, il admet un diviseur premier. Ce diviseur ne peut être ni 2, ni 3, ni 5, ni 7. Il manque donc au moins un nombre premier à la liste prétendument complète, ce qui contredit l’hypothèse de départ.
Le contrôle est refaisable directement : 211 = 2 × 105 + 1, 211 = 3 × 70 + 1, 211 = 5 × 42 + 1 et 211 = 7 × 30 + 1.
In practice
Pour réfuter une prétendue liste complète de nombres premiers, on multiplie tous ses termes et on ajoute 1. Le reste égal à 1 suffit à montrer qu’aucun terme de la liste ne divise le nouvel entier.
Pour produire un nombre ayant un facteur premier encore absent d’une liste finie, la même construction convient. Si le but est de trouver explicitement ce facteur, il faut ensuite décomposer le nouvel entier ; la construction seule garantit son existence.
Pour reconnaître une démonstration par l’absurde, on repère l’hypothèse opposée au résultat, puis la contradiction finale. Ici, l’hypothèse est l’existence d’une liste finie complète ; la contradiction est l’existence nécessaire d’un diviseur premier absent.
Not to be confused with
Avec un théorème d’Euclide en géométrie. Le critère est le domaine : la fiche traite de divisibilité et de nombres premiers, non d’un triangle rectangle. Le calcul 2 × 3 × 5 × 7 + 1 relève donc de l’arithmétique.
Avec l’algorithme d’Euclide. Le théorème présenté affirme l’infinité des nombres premiers. Un procédé visant à calculer un plus grand commun diviseur répond à une autre question, même si les deux sujets appartiennent à l’arithmétique et portent le nom d’Euclide.
Limits and pitfalls
Le produit augmenté de 1 n’est pas toujours premier. Le signe trompeur serait de conclure automatiquement que est le prochain nombre premier. Il suffit qu’un de ses diviseurs premiers soit absent de la liste.
La construction ne donne pas une énumération dans l’ordre. À partir de 2, 3, 5 et 7, elle produit 211, alors que l’objectif logique est seulement de faire apparaître un diviseur premier nouveau. Pour classer les nombres premiers, il faut employer une procédure d’énumération distincte.
L’entier construit doit être supérieur à 1. C’est précisément ce seuil qui autorise l’emploi du fait qu’un entier possède un diviseur premier. Une construction donnant 1 ne fournirait aucun tel diviseur et bloquerait la preuve.
Further reading
nombre premier — Revoir la définition du diviseur premier sur lequel repose la contradiction.
Raisonnement par l'absurde — Isoler la structure logique utilisée pour réfuter l’existence d’une liste finie complète.
L'inépuisable théorème des nombres premiers — Prolonger l’étude vers la répartition des nombres premiers au-delà de leur infinité.
Explore mathematics differently
Discover our magazines, podcasts and games to explore mathematics differently.
See our offers