Comprendre les nombres premiers - Guide complet
Decouvrez ce que sont les nombres premiers, comment les identifier, la decomposition en facteurs premiers, le crible d'Eratosthene et pourquoi les nombres premiers sont importants.
Qu'est-ce qu'un nombre premier ?
Un nombre premier est un nombre naturel superieur a 1 qui possede exactement deux diviseurs positifs distincts : 1 et lui-meme. Les premiers nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29. Le nombre 2 est le seul nombre premier pair, car tout autre nombre pair est divisible par 2. Le nombre 1 n'est pas considere comme premier car il n'a qu'un seul diviseur (lui-meme), et la definition exige exactement deux. Les nombres premiers sont les briques fondamentales de l'arithmetique, et ils fascinent les mathematiciens depuis plus de deux mille ans en raison de leur distribution apparemment irreguliere parmi les nombres naturels.
Comment tester si un nombre est premier
La methode la plus simple pour verifier si un nombre n est premier est la division par essai : testez si n est divisible par tout entier de 2 jusqu'a la racine carree de n. Si aucun de ces entiers ne divise n de maniere exacte, alors n est premier. Vous n'avez besoin de verifier que jusqu'a sqrt(n) car si n = a x b et que a et b sont tous deux superieurs a sqrt(n), alors a x b > n, ce qui est une contradiction. Par exemple, pour tester si 97 est premier, verifiez la divisibilite par 2, 3, 5 et 7 (puisque sqrt(97) est environ 9,85). Aucun ne divise exactement, donc 97 est premier. Pour les nombres plus grands, des algorithmes plus sophistiques comme le test de Miller-Rabin ou le test de primalite AKS sont utilises.
Le crible d'Eratosthene
Le crible d'Eratosthene est un algorithme ancien et efficace pour trouver tous les nombres premiers jusqu'a une limite donnee. Commencez par lister tous les entiers de 2 a n. Commencez avec le premier nombre (2) et marquez tous ses multiples comme composites (non premiers). Passez au prochain nombre non marque (3) et marquez tous ses multiples. Continuez ce processus. Chaque nombre non marque que vous rencontrez est premier. Vous n'avez besoin de cribler que jusqu'a sqrt(n), car tout nombre compose jusqu'a n doit avoir un facteur ne depassant pas sqrt(n). Par exemple, pour trouver tous les premiers jusqu'a 30, cribler les multiples de 2, 3 et 5 (puisque sqrt(30) est environ 5,5), laissant 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Le theoreme fondamental de l'arithmetique
Le theoreme fondamental de l'arithmetique stipule que tout entier superieur a 1 peut etre exprime comme un produit de nombres premiers d'une seule maniere (a l'ordre des facteurs pres). Cela signifie que les nombres premiers sont veritablement les « atomes » du systeme numerique. Par exemple, 60 = 2^2 x 3 x 5, et aucune autre combinaison de nombres premiers ne produit 60. Cette unicite de la decomposition en facteurs premiers est le fondement de nombreux resultats en theorie des nombres, et c'est la raison pour laquelle trouver la decomposition en facteurs premiers d'un grand nombre est computationnellement difficile, un fait qui sous-tend la securite cryptographique moderne.
Decomposition en facteurs premiers
La decomposition en facteurs premiers est le processus de decomposition d'un nombre compose en ses facteurs premiers. La methode standard est la division repetee : divisez le nombre par le plus petit nombre premier qui le divise exactement, puis divisez le quotient par le plus petit premier, et repetez jusqu'a ce que le quotient soit 1. Par exemple, 360 / 2 = 180, 180 / 2 = 90, 90 / 2 = 45, 45 / 3 = 15, 15 / 3 = 5, 5 / 5 = 1, donnant 360 = 2^3 x 3^2 x 5. La decomposition en facteurs premiers est utilisee pour trouver le plus grand commun diviseur (PGCD) et le plus petit commun multiple (PPCM) de deux nombres, simplifier les fractions et resoudre des problemes en theorie des nombres.
L'infinite des nombres premiers
L'un des plus beaux resultats en mathematiques, demontre par Euclide vers 300 av. J.-C., est qu'il existe une infinite de nombres premiers. La demonstration est elegante : supposons qu'il n'y ait qu'un nombre fini de nombres premiers, listons-les comme p1, p2, ..., pn, et considerons le nombre N = (p1 x p2 x ... x pn) + 1. N n'est divisible par aucun nombre premier de la liste (il laisse un reste de 1 quand on le divise par chacun), donc soit N est premier lui-meme, soit il a un facteur premier qui n'est pas dans la liste. Dans les deux cas, l'hypothese d'un nombre fini de premiers mene a une contradiction. Cette demonstration est un chef-d'oeuvre de raisonnement mathematique.
Distribution des nombres premiers
Bien que les nombres premiers deviennent moins frequents a mesure que les nombres grandissent, ils ne « s'epuisent » jamais. Le theoreme des nombres premiers, demontre en 1896, stipule que le nombre de premiers inferieurs ou egaux a n est approximativement n / ln(n). Cela signifie, par exemple, que parmi les premiers un million d'entiers, environ 1 000 000 / ln(1 000 000) = approximativement 72 382 sont premiers (le compte reel est 78 498, l'approximation est donc assez bonne). L'hypothese de Riemann, l'un des plus grands problemes non resolus en mathematiques, concerne la distribution exacte des nombres premiers et comporte un prix d'un million de dollars du Clay Mathematics Institute.
Les nombres premiers en cryptographie
Les nombres premiers sont l'epine dorsale des systemes cryptographiques modernes qui securisent les communications sur Internet, les transactions bancaires et les signatures numeriques. L'algorithme de chiffrement RSA repose sur le fait que multiplier deux grands nombres premiers est facile, mais que factoriser le produit en ses composantes premieres est extraordinairement difficile pour de grands nombres. Une cle RSA typique utilise des nombres premiers de centaines de chiffres, et la securite de tout le systeme repose sur l'infaisabilite computationnelle de la factorisation de leur produit. Cette importance pratique a fait de l'etude des nombres premiers non seulement une poursuite theorique mais une question de securite et de commerce mondial.