Comprendre les résultats
Le tableau ci-dessous présente les trois sorties pour quelques entrées types.
| Entrée | Premier ? | Décomposition | Premier suivant |
|---|---|---|---|
| 97 | Oui | 97 | 101 |
| 84 | Non | 2 x 2 x 3 x 7 | 89 |
| 100 | Non | 2 x 2 x 5 x 5 | 101 |
| 2 | Oui (seul premier pair) | 2 | 3 |
| 1 | Non (ni premier ni composé) | - | 2 |
- Le nombre 1 n'est pas premier : un premier doit posséder exactement deux diviseurs distincts, or 1 n'en a qu'un. L'exclure préserve l'unicité de la décomposition en facteurs premiers.
- La division d'essai est exacte mais ralentit sur de très grandes entrées ; ce calculateur accepte des nombres jusqu'à 10^12, la recherche testant alors les diviseurs jusqu'à un million.
- Dans cette plage, la recherche du premier suivant s'achève rapidement de façon garantie : d'après le postulat de Bertrand, il existe toujours un nombre premier entre n et 2n.
Qu'est-ce qu'un nombre premier ?
Un nombre premier est un entier naturel supérieur à 1 possédant exactement deux diviseurs positifs : 1 et lui-même. Les premiers de la liste sont 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29. Le nombre 2 est le seul premier pair, puisque tout autre nombre pair est divisible par 2. Les entiers supérieurs à 1 qui ne sont pas premiers sont dits composés ; quant à 1, il n'est par définition ni premier ni composé.
Le théorème fondamental de l'arithmétique établit que tout entier supérieur à 1 s'écrit comme produit de nombres premiers d'une seule manière, à l'ordre des facteurs près. C'est cette unicité de la décomposition qui vaut aux premiers leur statut de briques élémentaires des entiers : 84 = 2^2 x 3 x 7, et aucune autre combinaison de premiers ne donne 84.
Les nombres premiers sont en quantité infinie, résultat démontré par Euclide vers 300 av. J.-C., et ils se raréfient à mesure que les nombres grandissent, sans pour autant suivre de schéma simple. Les grands premiers fondent la cryptographie moderne à clé publique, RSA notamment, laquelle repose sur la difficulté pratique de factoriser le produit de deux très grands nombres premiers.
Comment utiliser ce calculateur de nombres premiers
- Saisissez un entier n supérieur ou égal à 1. Les décimales sont tronquées à l'entier inférieur.
- Lisez le verdict de primalité : une coche signale un nombre premier, une croix un nombre composé (ou 1, qui n'est ni l'un ni l'autre).
- Consultez la décomposition en facteurs premiers, ce produit unique de nombres premiers égal à votre nombre. Pour une entrée première, la décomposition se réduit au nombre lui-même.
- Lisez le nombre premier suivant, c'est-à-dire le plus petit premier strictement supérieur à votre nombre.
Comment se teste la primalité : la division d'essai
Un nombre n est composé si et seulement s'il admet un diviseur supérieur à 1 et inférieur ou égal à sa racine carrée. Les diviseurs vont en effet par paires : si n = a x b avec a inférieur ou égal à b, alors a ne dépasse pas √n. La division d'essai n'a donc besoin de tester les diviseurs candidats que jusqu'à √n, et, une fois 2 écarté, seuls les candidats impairs restent à examiner.
Exemple détaillé pour un premier, n = 97. La racine carrée de 97 vaut environ 9,85 : il suffit donc de tester 2, 3, 5, 7 et 9. Or 97 est impair ; 9 + 7 = 16 n'est pas divisible par 3 ; le nombre ne se termine ni par 0 ni par 5 ; 97 / 7 = 13,857… ; et 97 / 9 ne tombe pas juste. Aucun diviseur n'existe, donc 97 est premier.
Exemple détaillé de décomposition, n = 84. On divise successivement par les premiers, du plus petit au plus grand : 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7, et 7 est premier. Ainsi 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. Le premier suivant 84 est 89, puisque 85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29 et 88 = 2^3 x 11.
Erreurs fréquentes
- Compter 1 parmi les nombres premiers : par définition, un premier possède exactement deux diviseurs distincts, et 1 n'en a qu'un.
- Supposer que tous les premiers sont impairs : 2 est premier, et c'est même le seul premier pair.
- Tester les diviseurs jusqu'à n au lieu de s'arrêter à √n : tout nombre composé possède un facteur inférieur ou égal à sa racine carrée.
- Croire que tous les nombres impairs sont premiers : 9 = 3 x 3, 15 = 3 x 5 et 21 = 3 x 7 sont des composés impairs.
- Confondre la décomposition en facteurs premiers et une factorisation quelconque : 84 = 4 x 21 est une factorisation, mais la décomposition en facteurs premiers s'écrit 2 x 2 x 3 x 7.
Questions fréquentes
Comment vérifier qu'un nombre est premier ?
Testez si un entier compris entre 2 et la racine carrée du nombre le divise exactement. Si aucun n'y parvient, le nombre est premier. Pour 97, la racine carrée vaut environ 9,85, et ni 2, ni 3, ni 5, ni 7, ni 9 ne divise 97 : 97 est donc premier. L'appariement des diviseurs garantit que tout nombre composé possède un facteur inférieur ou égal à sa racine carrée.
Pourquoi 1 n'est-il pas un nombre premier ?
Un premier se définit par la possession d'exactement deux diviseurs positifs distincts, 1 et lui-même ; or le nombre 1 n'en compte qu'un seul. Cette définition protège également le théorème fondamental de l'arithmétique : si 1 était premier, les décompositions perdraient leur unicité (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3, et ainsi de suite).
Qu'est-ce qu'une décomposition en facteurs premiers ?
C'est l'écriture d'un nombre sous forme de produit de nombres premiers, que le théorème fondamental de l'arithmétique garantit unique à l'ordre près. Ainsi, 84 = 2 x 2 x 3 x 7. Pour l'obtenir, divisez à répétition par le plus petit premier qui tombe juste, jusqu'à ce que le quotient restant vaille 1 ou soit lui-même premier.
Le nombre 2 est-il premier ?
Oui : 2 est premier, ses seuls diviseurs étant 1 et 2, et il constitue même le seul premier pair. Tout autre nombre pair est divisible par 2 et donc composé. C'est pourquoi les tests de primalité traitent 2 à part avant de n'examiner que les candidats impairs.
Combien existe-t-il de nombres premiers ?
Une infinité, comme Euclide l'a démontré vers 300 av. J.-C. : partant d'une liste finie de premiers, le nombre obtenu en les multipliant tous puis en ajoutant 1 n'est divisible par aucun d'eux, ce qui prouve qu'un premier manque à la liste. Les premiers se raréfient à mesure que les nombres grandissent — d'après le théorème des nombres premiers, leur densité au voisinage de n avoisine 1 / ln(n) — mais ils ne s'arrêtent jamais.
Pourquoi les nombres premiers comptent-ils en cryptographie ?
Les systèmes à clé publique tels que RSA reposent sur une asymétrie : multiplier deux grands nombres premiers est facile, tandis que retrouver ces premiers à partir de leur produit devient calculatoirement hors de portée aux tailles employées en pratique, de l'ordre de plusieurs centaines de chiffres. Les clés de sécurité se construisent sur de tels produits, ce qui fait de la génération de premiers et des tests de primalité des opérations cryptographiques centrales.
Références
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).