Les nombres sont différents : naturels, rationnels, rationnels, entiers et fractionnaires, positifs et négatifs, complexes et premiers, impairs et pairs, réels, etc. À partir de cet article, vous pourrez découvrir ce que sont les nombres premiers.
Quels nombres sont appelés « simples » en anglais ?
Très souvent, les écoliers ne savent pas à première vue comment répondre à l'une des questions les plus simples en mathématiques, à savoir ce qu'est un nombre premier. Ils confondent souvent les nombres premiers avec les nombres naturels (c'est-à-dire les nombres que les gens utilisent pour compter des objets, alors que dans certaines sources, ils commencent par zéro et dans d'autres par un). Mais ce sont deux concepts complètement différents. Les nombres premiers sont des nombres naturels, c'est-à-dire des nombres entiers et positifs supérieurs à un et qui n'ont que 2 diviseurs naturels. De plus, l'un de ces diviseurs est le nombre donné et le second est un. Par exemple, trois est un nombre premier car il ne peut être divisé sans reste par un nombre autre que lui-même et un.
Nombres composés
Le contraire des nombres premiers sont les nombres composés. Ils sont aussi naturels, également supérieurs à un, mais n'ont pas deux, mais un plus grand nombre de diviseurs. Ainsi, par exemple, les nombres 4, 6, 8, 9, etc. sont des nombres naturels, composés, mais non premiers. Comme vous pouvez le constater, ce sont pour la plupart des nombres pairs, mais pas tous. Mais « deux » est un nombre pair et le « premier nombre » d’une série de nombres premiers.
Sous-séquence
Pour construire une série de nombres premiers, il faut choisir parmi tous les nombres naturels, en tenant compte de leur définition, c'est-à-dire qu'il faut agir par contradiction. Il est nécessaire d’examiner chacun des nombres naturels positifs pour voir s’il a plus de deux diviseurs. Essayons de construire une série (séquence) composée de nombres premiers. La liste commence par deux, suivi de trois, puisqu'elle n'est divisible que par elle-même et par un. Considérez le chiffre quatre. A-t-il des diviseurs autres que quatre et un ? Oui, ce nombre est 2. Donc quatre n’est pas un nombre premier. Cinq est également premier (il n'est divisible par aucun autre nombre, sauf 1 et 5), mais six est divisible. Et en général, si vous suivez tous les nombres pairs, vous remarquerez qu’à l’exception de « deux », aucun d’entre eux n’est premier. On en conclut que les nombres pairs, sauf deux, ne sont pas premiers. Autre découverte : tous les nombres divisibles par trois, sauf le trois lui-même, qu'ils soient pairs ou impairs, ne sont pas non plus premiers (6, 9, 12, 15, 18, 21, 24, 27, etc.). Il en va de même pour les nombres divisibles par cinq et sept. Toute leur multitude n’est pas non plus simple. Résumons. Ainsi, les nombres simples à un chiffre incluent tous les nombres impairs sauf un et neuf, et même « deux » sont des nombres pairs. Les dizaines elles-mêmes (10, 20,... 40, etc.) ne sont pas simples. Les nombres premiers à deux chiffres, à trois chiffres, etc. peuvent être déterminés sur la base des principes ci-dessus : s'ils n'ont pas d'autres diviseurs qu'eux-mêmes et un.
Théories sur les propriétés des nombres premiers
Il existe une science qui étudie les propriétés des nombres entiers, y compris les nombres premiers. Il s'agit d'une branche des mathématiques appelée supérieure. Outre les propriétés des nombres entiers, elle traite également des nombres algébriques et transcendantaux, ainsi que des fonctions d'origines diverses liées à l'arithmétique de ces nombres. Dans ces études, outre les méthodes élémentaires et algébriques, des méthodes analytiques et géométriques sont également utilisées. Plus précisément, la « Théorie des nombres » traite de l’étude des nombres premiers.
Les nombres premiers sont les « éléments constitutifs » des nombres naturels
En arithmétique, il existe un théorème appelé théorème fondamental. Selon lui, tout nombre naturel, sauf un, peut être représenté comme un produit dont les facteurs sont des nombres premiers, et l'ordre des facteurs est unique, ce qui signifie que la méthode de représentation est unique. C’est ce qu’on appelle factoriser un nombre naturel en facteurs premiers. Il existe un autre nom pour ce processus : la factorisation des nombres. Sur cette base, les nombres premiers peuvent être appelés « matériaux de construction », « blocs » pour construire des nombres naturels.
Recherchez des nombres premiers. Tests de simplicité
De nombreux scientifiques de différentes époques ont essayé de trouver des principes (systèmes) permettant de trouver une liste de nombres premiers. La science connaît des systèmes appelés tamis Atkin, tamis Sundartham et tamis Eratosthène. Cependant, ils ne produisent aucun résultat significatif et un simple test est utilisé pour trouver les nombres premiers. Les mathématiciens ont également créé des algorithmes. Ils sont généralement appelés tests de primalité. Par exemple, il existe un test développé par Rabin et Miller. Il est utilisé par les cryptographes. Il existe également le test Kayal-Agrawal-Sasquena. Cependant, malgré une précision suffisante, son calcul est très difficile, ce qui réduit son importance pratique.
L’ensemble des nombres premiers a-t-il une limite ?
Le scientifique grec Euclide a écrit dans son livre « Éléments » que l’ensemble des nombres premiers est l’infini. Il a dit ceci : « Imaginons un instant que les nombres premiers aient une limite. Ensuite, multiplions-les entre eux et ajoutons-en un au produit. Le nombre obtenu à la suite de ces actions simples ne peut être divisé par aucune des séries de nombres premiers, car le reste sera toujours un. Cela signifie qu'il existe un autre nombre qui n'est pas encore inclus dans la liste des nombres premiers. Par conséquent, notre hypothèse n’est pas vraie et cet ensemble ne peut pas avoir de limite. Outre la preuve d'Euclide, il existe une formule plus moderne donnée par le mathématicien suisse du XVIIIe siècle Leonhard Euler. Selon lui, la somme réciproque de la somme des n premiers nombres croît de manière illimitée à mesure que le nombre n augmente. Et voici la formule du théorème concernant la distribution des nombres premiers : (n) croît comme n/ln (n).
Quel est le plus grand nombre premier ?
Le même Leonard Euler a pu trouver le plus grand nombre premier de son époque. Il s'agit de 2 31 - 1 = 2147483647. Cependant, en 2013, un autre nombre premier le plus précis de la liste des nombres premiers a été calculé - 2 57885161 - 1. Il s'appelle le nombre de Mersenne. Il contient environ 17 millions de chiffres décimaux. Comme vous pouvez le constater, le nombre trouvé par un scientifique du XVIIIe siècle est plusieurs fois inférieur à celui-ci. Cela était normal, car Euler effectuait ce calcul manuellement, alors que notre contemporain était probablement aidé par un ordinateur. De plus, ce numéro a été obtenu à la Faculté de mathématiques d'une des facultés américaines. Les nombres portant le nom de ce scientifique réussissent le test de primalité de Luc-Lemaire. Mais la science ne veut pas s’arrêter là. L'Electronic Frontier Foundation, fondée en 1990 aux États-Unis d'Amérique (EFF), offre une récompense monétaire pour la découverte de grands nombres premiers. Et si jusqu'en 2013 le prix était décerné aux scientifiques qui les trouveraient entre 1 et 10 millions de nombres décimaux, aujourd'hui ce chiffre atteint entre 100 millions et 1 milliard. Les prix varient de 150 à 250 000 dollars américains.
Noms de nombres premiers spéciaux
Les nombres qui ont été trouvés grâce à des algorithmes créés par certains scientifiques et qui ont réussi le test de simplicité sont appelés spéciaux. En voici quelques uns:
1. Merssen.
4. Cullen.
6. Mills et coll.
La simplicité de ces nombres, nommés d'après les scientifiques ci-dessus, est établie à l'aide des tests suivants :
1. Luc-Lemaire.
2. Pépina.
3. Riesel.
4. Billhart - Lemaire - Selfridge et autres.
La science moderne ne s’arrête pas là et, probablement, dans un avenir proche, le monde connaîtra les noms de ceux qui ont pu remporter le prix de 250 000 $ en trouvant le plus grand nombre premier.
Dans cet article, nous explorerons nombres premiers et composés. Tout d’abord, nous donnerons des définitions des nombres premiers et composés, ainsi que des exemples. Nous prouverons ensuite qu’il existe une infinité de nombres premiers. Ensuite, nous rédigerons un tableau de nombres premiers et examinerons les méthodes permettant de compiler un tableau de nombres premiers, en accordant une attention particulière à la méthode appelée le tamis d'Ératosthène. En conclusion, nous soulignerons les principaux points à prendre en compte pour prouver qu'un nombre donné est premier ou composé.
Navigation dans les pages.
Nombres premiers et composés - Définitions et exemples
Les notions de nombres premiers et de nombres composés font référence à des nombres supérieurs à un. Ces entiers, en fonction du nombre de leurs diviseurs positifs, sont divisés en nombres premiers et composés. Alors pour comprendre définitions des nombres premiers et composés, vous devez bien comprendre ce que sont les diviseurs et les multiples.
Définition.
nombres premiers sont des entiers, de grandes unités, qui n'ont que deux diviseurs positifs, à savoir eux-mêmes et 1.
Définition.
Nombres composés sont des nombres entiers, grands, qui ont au moins trois diviseurs positifs.
Par ailleurs, notons que le chiffre 1 ne s'applique ni aux nombres premiers ni aux nombres composés. L’unité n’a qu’un seul diviseur positif, qui est le chiffre 1 lui-même. Cela distingue le nombre 1 de tous les autres entiers positifs possédant au moins deux diviseurs positifs.
Considérant que les entiers positifs sont , et qu’il n’y a qu’un seul diviseur positif, nous pouvons donner d’autres formulations des définitions énoncées des nombres premiers et composés.
Définition.
nombres premiers sont des nombres naturels qui n'ont que deux diviseurs positifs.
Définition.
Nombres composés sont des nombres naturels qui ont plus de deux diviseurs positifs.
Notez que tout entier positif supérieur à un est soit un nombre premier, soit un nombre composé. En d’autres termes, il n’existe pas un seul entier qui ne soit ni premier ni composé. Cela découle de la propriété de divisibilité, qui stipule que les nombres 1 et a sont toujours des diviseurs de tout entier a.
Sur la base des informations du paragraphe précédent, nous pouvons donner la définition suivante des nombres composés.
Définition.
Les nombres naturels qui ne sont pas premiers sont appelés composite.
Donne moi exemples de nombres premiers et composés.
Des exemples de nombres composés incluent 6, 63, 121 et 6 697. Cette affirmation mérite également d'être clarifiée. Le nombre 6, en plus des diviseurs positifs 1 et 6, possède également les diviseurs 2 et 3, puisque 6 = 2 3, donc 6 est véritablement un nombre composé. Les facteurs positifs de 63 sont les nombres 1, 3, 7, 9, 21 et 63. Le nombre 121 est égal au produit 11·11, donc ses diviseurs positifs sont 1, 11 et 121. Et le nombre 6 697 est composite, puisque ses diviseurs positifs, en plus de 1 et 6 697, sont aussi les nombres 37 et 181.
En conclusion de ce point, je voudrais également attirer l’attention sur le fait que les nombres premiers et les nombres premiers entre eux sont loin d’être la même chose.
Tableau des nombres premiers
Les nombres premiers, pour faciliter leur utilisation ultérieure, sont enregistrés dans un tableau appelé tableau des nombres premiers. Ci-dessous se trouve tableau des nombres premiers jusqu'à 1 000.
Une question logique se pose : « Pourquoi avons-nous rempli le tableau des nombres premiers jusqu'à 1 000 seulement, n'est-il pas possible de créer un tableau de tous les nombres premiers existants » ?
Répondons d'abord à la première partie de cette question. Pour la plupart des problèmes nécessitant l’utilisation de nombres premiers, des nombres premiers inférieurs à mille seront suffisants. Dans d'autres cas, vous devrez probablement recourir à des solutions spéciales. Bien que nous puissions certainement créer un tableau de nombres premiers jusqu'à un entier positif fini arbitrairement grand, que ce soit 10 000 ou 1 000 000 000, dans le paragraphe suivant, nous parlerons des méthodes de création de tableaux de nombres premiers, en particulier, nous examinerons une méthode appelé.
Examinons maintenant la possibilité (ou plutôt l'impossibilité) de dresser un tableau de tous les nombres premiers existants. Nous ne pouvons pas dresser un tableau de tous les nombres premiers car il existe une infinité de nombres premiers. Le dernier énoncé est un théorème que nous démontrerons après le théorème auxiliaire suivant.
Théorème.
Le plus petit diviseur positif autre que 1 d'un nombre naturel supérieur à un est un nombre premier.
Preuve.
Laisser a est un nombre naturel supérieur à un et b est le plus petit diviseur positif de a autre qu'un. Montrons que b est un nombre premier par contradiction.
Supposons que b soit un nombre composé. Ensuite, il existe un diviseur du nombre b (notons-le b 1), qui est différent à la fois de 1 et de b. Si l'on tient également compte du fait que la valeur absolue du diviseur ne dépasse pas la valeur absolue du dividende (nous le savons grâce aux propriétés de divisibilité), alors la condition 1 doit être remplie
Puisque le nombre a est divisible par b selon la condition, et que l'on a dit que b est divisible par b 1, la notion de divisibilité permet de parler de l'existence d'entiers q et q 1 tels que a=b q et b=b 1 q 1 , d'où a= b 1 ·(q 1 ·q) . Il s'ensuit que le produit de deux entiers est un entier, alors l'égalité a=b 1 ·(q 1 ·q) indique que b 1 est un diviseur du nombre a. Compte tenu des inégalités ci-dessus 1
Nous pouvons maintenant prouver qu’il existe une infinité de nombres premiers.
Théorème.
Il existe un nombre infini de nombres premiers.
Preuve.
Supposons que ce ne soit pas le cas. Autrement dit, supposons qu'il n'y ait que n nombres premiers et que ces nombres premiers soient p 1, p 2, ..., p n. Montrons qu'on peut toujours trouver un nombre premier différent de ceux indiqués.
Considérons le nombre p égal à p 1 ·p 2 ·…·p n +1. Il est clair que ce nombre est différent de chacun des nombres premiers p 1, p 2, ..., p n. Si le nombre p est premier, alors le théorème est prouvé. Si ce nombre est composé, alors en vertu du théorème précédent il existe un diviseur premier de ce nombre (on le note p n+1). Montrons que ce diviseur ne coïncide avec aucun des nombres p 1, p 2, ..., p n.
Si tel n'était pas le cas, alors, selon les propriétés de divisibilité, le produit p 1 ·p 2 ·…·p n serait divisé par p n+1. Mais le nombre p est aussi divisible par p n+1, égal à la somme p 1 ·p 2 ·…·p n +1. Il s'ensuit que p n+1 doit diviser le deuxième terme de cette somme, qui est égal à un, mais cela est impossible.
Ainsi, il a été prouvé qu'il est toujours possible de trouver un nouveau nombre premier qui n'est inclus parmi aucun nombre de nombres premiers prédéterminés. Il existe donc une infinité de nombres premiers.
Ainsi, étant donné qu'il existe un nombre infini de nombres premiers, lors de l'élaboration de tableaux de nombres premiers, vous vous limitez toujours d'en haut à un nombre, généralement 100, 1 000, 10 000, etc.
Tamis d'Ératosthène
Nous allons maintenant discuter des façons de créer des tableaux de nombres premiers. Supposons que nous devions créer un tableau de nombres premiers jusqu'à 100.
La méthode la plus évidente pour résoudre ce problème consiste à vérifier séquentiellement sur les entiers positifs, commençant par 2 et se terminant par 100, la présence d'un diviseur positif supérieur à 1 et inférieur au nombre testé (d'après les propriétés de divisibilité que nous connaissons que la valeur absolue du diviseur n'excède pas la valeur absolue du dividende, non nulle). Si un tel diviseur n'est pas trouvé, alors le nombre testé est premier et il est inscrit dans la table des nombres premiers. Si un tel diviseur est trouvé, alors le nombre testé est composé ; il n'est PAS inscrit dans le tableau des nombres premiers. Après cela, il y a une transition vers le numéro suivant, qui est également vérifié pour la présence d'un diviseur.
Décrivons les premières étapes.
Nous commençons par le chiffre 2. Le nombre 2 n’a pas de diviseurs positifs autres que 1 et 2. C'est donc simple, donc on l'inscrit dans le tableau des nombres premiers. Ici, il faut dire que 2 est le plus petit nombre premier. Passons au numéro 3. Son éventuel diviseur positif autre que 1 et 3 est le nombre 2. Mais 3 n'est pas divisible par 2, donc 3 est un nombre premier et doit également être inclus dans le tableau des nombres premiers. Passons au numéro 4. Ses diviseurs positifs autres que 1 et 4 peuvent être les nombres 2 et 3, vérifions-les. Le nombre 4 est divisible par 2, donc 4 est un nombre composé et n'a pas besoin d'être inclus dans le tableau des nombres premiers. Veuillez noter que 4 est le plus petit nombre composé. Passons au numéro 5. On vérifie si au moins un des nombres 2, 3, 4 est son diviseur. Puisque 5 n’est pas divisible par 2, 3 ou 4, alors il est premier et doit être écrit dans le tableau des nombres premiers. Ensuite, il y a une transition vers les nombres 6, 7, et ainsi de suite jusqu'à 100.
Cette approche pour compiler un tableau de nombres premiers est loin d’être idéale. D'une manière ou d'une autre, il a le droit d'exister. Notez qu'avec cette méthode de construction d'un tableau d'entiers, vous pouvez utiliser des critères de divisibilité, ce qui accélérera légèrement le processus de recherche de diviseurs.
Il existe un moyen plus pratique de créer un tableau de nombres premiers, appelé. Le mot « tamis » présent dans le nom n'est pas accidentel, puisque les actions de cette méthode aident, pour ainsi dire, à « passer au crible » les nombres entiers et les grandes unités à travers le tamis d'Eratosthène afin de séparer les simples des composés.
Montrons le tamis d'Ératosthène en action lors de la compilation d'un tableau de nombres premiers jusqu'à 50.
Tout d'abord, notez les nombres 2, 3, 4, ..., 50 dans l'ordre.
Le premier nombre écrit, 2, est premier. Maintenant, à partir du numéro 2, nous nous déplaçons séquentiellement vers la droite de deux nombres et barrons ces nombres jusqu'à atteindre la fin du tableau des nombres en cours de compilation. Cela rayera tous les nombres multiples de deux.
Le premier chiffre qui n’est pas barré après 2 est 3. Ce nombre est premier. Maintenant, à partir du numéro 3, nous nous déplaçons séquentiellement vers la droite de trois chiffres (en tenant compte des chiffres déjà barrés) et les biffons. Cela rayera tous les nombres multiples de trois.
Le premier chiffre qui n’est pas barré après 3 est 5. Ce nombre est premier. Maintenant, à partir du chiffre 5, nous nous déplaçons systématiquement vers la droite de 5 chiffres (nous prenons également en compte les chiffres barrés plus tôt) et les biffons. Cela rayera tous les nombres multiples de cinq.
Ensuite, on raye les nombres multiples de 7, puis multiples de 11, et ainsi de suite. Le processus se termine lorsqu’il n’y a plus de chiffres à rayer. Ci-dessous le tableau complété des nombres premiers jusqu'à 50, obtenu à l'aide du tamis d'Eratosthène. Tous les nombres non croisés sont premiers et tous les nombres barrés sont composés.
Formulons et prouvons également un théorème qui accélérera le processus d'élaboration d'un tableau de nombres premiers à l'aide du tamis d'Eratosthène.
Théorème.
Le plus petit diviseur positif d'un nombre composé a différent de un ne dépasse pas , où provient de a .
Preuve.
Notons par la lettre b le plus petit diviseur d'un nombre composé a différent de un (le nombre b est premier, comme il ressort du théorème prouvé au tout début du paragraphe précédent). Alors il existe un entier q tel que a=b·q (ici q est un entier positif, qui découle des règles de multiplication des entiers), et (pour b>q la condition selon laquelle b est le plus petit diviseur de a est violée , puisque q est aussi un diviseur du nombre a en raison de l'égalité a=q·b ). En multipliant les deux côtés de l'inégalité par un positif et un entier supérieur à un (nous avons le droit de le faire), nous obtenons , d'où et .
Que nous donne le théorème prouvé concernant le tamis d'Ératosthène ?
Premièrement, la suppression des nombres composés multiples d'un nombre premier b doit commencer par un nombre égal à (cela découle de l'inégalité). Par exemple, barrer les nombres multiples de deux doit commencer par le chiffre 4, les multiples de trois par le chiffre 9, les multiples de cinq par le chiffre 25, et ainsi de suite.
Deuxièmement, l'établissement d'un tableau de nombres premiers jusqu'au nombre n à l'aide du tamis d'Ératosthène peut être considéré comme complet lorsque tous les nombres composés qui sont des multiples de nombres premiers ne dépassent pas . Dans notre exemple, n=50 (puisque nous faisons un tableau de nombres premiers jusqu'à 50) et, par conséquent, le tamis d'Ératosthène devrait éliminer tous les nombres composés qui sont des multiples des nombres premiers 2, 3, 5 et 7 qui font ne dépasse pas la racine carrée arithmétique de 50. C'est-à-dire que nous n'avons plus besoin de rechercher et de rayer des nombres multiples de nombres premiers 11, 13, 17, 19, 23 et ainsi de suite jusqu'à 47, puisqu'ils seront déjà barrés comme des multiples de nombres premiers plus petits 2 , 3, 5 et 7 .
Ce nombre est-il premier ou composé ?
Certaines tâches nécessitent de déterminer si un nombre donné est premier ou composé. Dans le cas général, cette tâche est loin d'être simple, surtout pour les nombres dont l'écriture est constituée d'un nombre important de caractères. Dans la plupart des cas, vous devez rechercher un moyen spécifique pour le résoudre. Nous essaierons cependant d’orienter la réflexion pour des cas simples.
Bien entendu, vous pouvez essayer d’utiliser des tests de divisibilité pour prouver qu’un nombre donné est composé. Si, par exemple, un test de divisibilité montre qu'un nombre donné est divisible par un entier positif supérieur à un, alors le nombre original est composé.
Exemple.
Montrer que 898 989 898 989 898 989 est un nombre composé.
Solution.
La somme des chiffres de ce nombre est 9·8+9·9=9·17. Puisque le nombre égal à 9·17 est divisible par 9, alors selon le critère de divisibilité par 9, on peut affirmer que le nombre original est également divisible par 9. Il est donc composite.
Un inconvénient majeur de cette approche est que les critères de divisibilité ne permettent pas de prouver le caractère premier d'un nombre. Par conséquent, lorsque vous vérifiez un nombre pour voir s’il est premier ou composé, vous devez procéder différemment.
L’approche la plus logique consiste à essayer tous les diviseurs possibles d’un nombre donné. Si aucun des diviseurs possibles n’est un vrai diviseur d’un nombre donné, alors ce nombre sera premier, sinon il sera composé. Des théorèmes démontrés dans le paragraphe précédent, il résulte que les diviseurs d'un nombre donné a doivent être recherchés parmi les nombres premiers n'excédant pas . Ainsi, un nombre donné a peut être divisé séquentiellement par des nombres premiers (qui sont commodément tirés du tableau des nombres premiers), en essayant de trouver le diviseur du nombre a. Si un diviseur est trouvé, alors le nombre a est composé. Si parmi les nombres premiers n’excédant pas , il n’y a pas de diviseur du nombre a, alors le nombre a est premier.
Exemple.
Nombre 11 723 simple ou composé ?
Solution.
Découvrons jusqu'à quel nombre premier peuvent être les diviseurs du nombre 11 723. Pour ce faire, évaluons.
C'est assez évident que 
, puisque 200 2 =40 000, et 11 723<40 000
(при необходимости смотрите статью comparaison de chiffres). Ainsi, les facteurs premiers possibles de 11 723 sont inférieurs à 200. Cela rend déjà notre tâche beaucoup plus facile. Si nous ne le savions pas, nous devrions alors parcourir tous les nombres premiers non pas jusqu’à 200, mais jusqu’au nombre 11 723.
Si vous le souhaitez, vous pouvez évaluer plus précisément. Puisque 108 2 =11 664 et 109 2 =11 881, alors 108 2<11 723<109 2
, следовательно, 
. Ainsi, tout nombre premier inférieur à 109 est potentiellement un facteur premier du nombre donné 11 723.
Nous allons maintenant diviser séquentiellement le nombre 11 723 en nombres premiers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71. , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Si le nombre 11 723 est divisé par l’un des nombres premiers écrits, alors il sera composé. S’il n’est divisible par aucun des nombres premiers écrits, alors le nombre original est premier.
Nous ne décrirons pas tout ce processus de division monotone et monotone. Disons tout de suite que 11 723
- Traduction
Les propriétés des nombres premiers ont été étudiées pour la première fois par les mathématiciens de la Grèce antique. Les mathématiciens de l'école pythagoricienne (500 - 300 avant JC) s'intéressaient principalement aux propriétés mystiques et numérologiques des nombres premiers. Ils ont été les premiers à proposer des idées de nombres parfaits et conviviaux.
Un nombre parfait possède une somme de ses propres diviseurs égale à lui-même. Par exemple, les diviseurs propres du nombre 6 sont 1, 2 et 3. 1 + 2 + 3 = 6. Les diviseurs du nombre 28 sont 1, 2, 4, 7 et 14. De plus, 1 + 2 + 4 + 7 + 14 = 28.
Les nombres sont dits amicaux si la somme des diviseurs propres d'un nombre est égale à un autre, et vice versa - par exemple, 220 et 284. On peut dire qu'un nombre parfait est amical avec lui-même.
À l'époque des Éléments d'Euclide en 300 av. Plusieurs faits importants sur les nombres premiers ont déjà été prouvés. Dans le livre IX des Éléments, Euclide démontre qu’il existe un nombre infini de nombres premiers. C’est d’ailleurs l’un des premiers exemples d’utilisation de la preuve par contradiction. Il prouve également le théorème fondamental de l'arithmétique : chaque nombre entier peut être représenté de manière unique comme un produit de nombres premiers.
Il a également montré que si le nombre 2n-1 est premier, alors le nombre 2n-1 * (2n-1) sera parfait. Un autre mathématicien, Euler, a pu montrer en 1747 que tous les nombres, même parfaits, peuvent s'écrire sous cette forme. À ce jour, on ne sait pas s’il existe des nombres parfaits impairs.
En l'an 200 avant JC. Le grec Eratosthène a mis au point un algorithme pour trouver les nombres premiers appelé le tamis d'Eratosthène.
Et puis il y a eu une grande rupture dans l’histoire de l’étude des nombres premiers, associée au Moyen Âge.
Les découvertes suivantes ont été faites dès le début du XVIIe siècle par le mathématicien Fermat. Il a prouvé la conjecture d'Albert Girard selon laquelle tout nombre premier de la forme 4n+1 peut être écrit de manière unique comme la somme de deux carrés, et a également formulé le théorème selon lequel tout nombre peut être écrit comme la somme de quatre carrés.
Il a développé une nouvelle méthode de factorisation des grands nombres et l'a démontrée sur le nombre 2027651281 = 44021 × 46061. Il a également prouvé le petit théorème de Fermat : si p est un nombre premier, alors pour tout entier a, il sera vrai que a p = a modulo p.
Cette affirmation prouve la moitié de ce que l'on appelait la « conjecture chinoise » et remonte à 2000 ans plus tôt : l'entier n est premier si et seulement si 2 n -2 est divisible par n. La deuxième partie de l'hypothèse s'est avérée fausse - par exemple, 2 341 - 2 est divisible par 341, bien que le nombre 341 soit composé : 341 = 31 × 11.
Le petit théorème de Fermat a servi de base à de nombreux autres résultats en théorie des nombres et à des méthodes permettant de vérifier si les nombres sont premiers - dont beaucoup sont encore utilisés aujourd'hui.
Fermat correspondait beaucoup avec ses contemporains, notamment avec une moine nommée Maren Mersenne. Dans l'une de ses lettres, il émet l'hypothèse que les nombres de la forme 2 n +1 seront toujours premiers si n est une puissance de deux. Il a testé cela pour n = 1, 2, 4, 8 et 16 et était convaincu que dans le cas où n n'était pas une puissance de deux, le nombre n'était pas nécessairement premier. Ces nombres sont appelés nombres de Fermat, et seulement 100 ans plus tard, Euler montra que le nombre suivant, 2 32 + 1 = 4294967297, est divisible par 641 et n'est donc pas premier.
Les nombres de la forme 2 n - 1 ont également fait l'objet de recherches, puisqu'il est facile de montrer que si n est composé, alors le nombre lui-même est également composé. Ces nombres sont appelés nombres de Mersenne car il les a étudiés de manière approfondie.
Mais tous les nombres de la forme 2 n - 1, où n est premier, ne sont pas premiers. Par exemple, 2 11 - 1 = 2047 = 23 * 89. Cela a été découvert pour la première fois en 1536.
Pendant de nombreuses années, ce type de nombres a fourni aux mathématiciens les plus grands nombres premiers connus. Ce M 19 a été prouvé par Cataldi en 1588 et a été pendant 200 ans le plus grand nombre premier connu, jusqu'à ce qu'Euler prouve que M 31 était également premier. Ce record a duré encore cent ans, puis Lucas a montré que M 127 est premier (et il s'agit déjà d'un nombre de 39 chiffres), et après cela, les recherches se sont poursuivies avec l'avènement des ordinateurs.
En 1952, la primauté des nombres M 521, M 607, M 1279, M 2203 et M 2281 est prouvée.
En 2005, 42 nombres premiers de Mersenne avaient été trouvés. Le plus grand d'entre eux, M 25964951, comprend 7816230 chiffres.
Les travaux d'Euler ont eu un impact énorme sur la théorie des nombres, y compris sur les nombres premiers. Il a étendu le petit théorème de Fermat et introduit la fonction φ. Factorisé le 5ème nombre de Fermat 2 32 +1, trouvé 60 paires de nombres amis et formulé (mais n'a pas pu prouver) la loi de réciprocité quadratique.
Il fut le premier à introduire des méthodes d'analyse mathématique et à développer la théorie analytique des nombres. Il a prouvé que non seulement la série harmonique ∑ (1/n), mais aussi une série de la forme
1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…
Le résultat obtenu par la somme des réciproques des nombres premiers diverge également. La somme des n termes de la série harmonique croît approximativement comme log(n), et la deuxième série diverge plus lentement comme log[ log(n) ]. Cela signifie que, par exemple, la somme des réciproques de tous les nombres premiers trouvés à ce jour ne donnera que 4, bien que la série diverge encore.
À première vue, il semble que les nombres premiers soient répartis de manière assez aléatoire parmi les nombres entiers. Par exemple, parmi les 100 nombres immédiatement avant 1 000 000, il y a 9 nombres premiers, et parmi les 100 nombres immédiatement après cette valeur, il n'y en a que 2. Mais sur de grands segments, les nombres premiers sont répartis assez uniformément. Legendre et Gauss ont traité des questions de leur répartition. Gauss a dit un jour à un ami que pendant 15 minutes libres, il comptait toujours le nombre de nombres premiers dans les 1 000 nombres suivants. À la fin de sa vie, il avait compté tous les nombres premiers jusqu'à 3 millions. Legendre et Gauss ont également calculé que pour n grand, la densité première est de 1/log(n). Legendre a estimé le nombre de nombres premiers compris entre 1 et n comme suit :
π(n) = n/(log(n) - 1,08366)
Et Gauss est comme une intégrale logarithmique
π(n) = ∫ 1/log(t)dt
Avec un intervalle d'intégration de 2 à n.
L'énoncé concernant la densité première 1/log(n) est connu sous le nom de théorème de distribution première. Ils ont tenté de le prouver tout au long du XIXe siècle, et des progrès ont été réalisés grâce à Chebyshev et Riemann. Ils l'ont relié à l'hypothèse de Riemann, une hypothèse encore non prouvée sur la distribution des zéros de la fonction zêta de Riemann. La densité des nombres premiers a été prouvée simultanément par Hadamard et Vallée-Poussin en 1896.
Il reste encore de nombreuses questions non résolues dans la théorie des nombres premiers, dont certaines datent de plusieurs centaines d’années :
- L’hypothèse des jumeaux premiers concerne un nombre infini de paires de nombres premiers qui diffèrent les uns des autres de 2.
- Conjecture de Goldbach : tout nombre pair, commençant par 4, peut être représenté comme la somme de deux nombres premiers
- Existe-t-il un nombre infini de nombres premiers de la forme n 2 + 1 ?
- Est-il toujours possible de trouver un nombre premier entre n 2 et (n + 1) 2 ? (le fait qu'il y ait toujours un nombre premier entre n et 2n a été prouvé par Chebyshev)
- Le nombre de Fermat premiers est-il infini ? Y a-t-il des nombres premiers de Fermat après 4 ?
- existe-t-il une progression arithmétique de nombres premiers consécutifs pour une longueur donnée ? par exemple, pour la longueur 4 : 251, 257, 263, 269. La longueur maximale trouvée est 26.
- Existe-t-il un nombre infini d’ensembles de trois nombres premiers consécutifs dans une progression arithmétique ?
- n 2 - n + 41 est un nombre premier pour 0 ≤ n ≤ 40. Existe-t-il un nombre infini de tels nombres premiers ? La même question pour la formule n 2 - 79 n + 1601. Ces nombres sont premiers pour 0 ≤ n ≤ 79.
- Existe-t-il un nombre infini de nombres premiers de la forme n# + 1 ? (n# est le résultat de la multiplication de tous les nombres premiers inférieurs à n)
- Existe-t-il un nombre infini de nombres premiers de la forme n# -1 ?
- Existe-t-il un nombre infini de nombres premiers de la forme n ? +1 ?
- Existe-t-il un nombre infini de nombres premiers de la forme n ? - 1?
- si p est premier, 2 p -1 ne contient-il pas toujours des carrés premiers parmi ses facteurs ?
- la suite de Fibonacci contient-elle un nombre infini de nombres premiers ?
Les plus grands nombres premiers jumeaux sont 2003663613 × 2 195 000 ± 1. Ils comprennent 58 711 chiffres et ont été découverts en 2007.
Le plus grand nombre premier factoriel (du type n! ± 1) est 147855 ! - 1. Il se compose de 142891 chiffres et a été trouvé en 2002.
Le plus grand nombre premier primitif (un nombre de la forme n# ± 1) est 1098133# + 1.
Balises : Ajouter des balises
Énumération des diviseurs. Par définition, le nombre n n'est premier que s'il n'est pas divisible également par 2 et d'autres entiers sauf 1 et lui-même. La formule ci-dessus supprime les étapes inutiles et fait gagner du temps : par exemple, après avoir vérifié si un nombre est divisible par 3, il n'est pas nécessaire de vérifier s'il est divisible par 9.
- La fonction floor(x) arrondit x à l'entier le plus proche inférieur ou égal à x.
Apprenez-en davantage sur l’arithmétique modulaire. L'opération « x mod y » (mod est une abréviation du mot latin « modulo », c'est-à-dire « module ») signifie « diviser x par y et trouver le reste ». En d’autres termes, en arithmétique modulaire, lorsqu’on atteint une certaine valeur, appelée module, les chiffres « reviennent » à nouveau à zéro. Par exemple, une horloge donne l'heure avec un module 12 : elle affiche 10, 11 et 12 heures puis revient à 1.
- De nombreuses calculatrices ont une touche mod. La fin de cette section montre comment évaluer manuellement cette fonction pour de grands nombres.
Découvrez les pièges du petit théorème de Fermat. Tous les nombres pour lesquels les conditions de test ne sont pas remplies sont composites, mais les nombres restants ne sont que probablement sont classés comme simples. Si vous souhaitez éviter des résultats incorrects, recherchez n dans la liste des « nombres de Carmichael » (nombres composés qui satisfont à ce test) et des « nombres de Fermat pseudo-premiers » (ces nombres ne répondent aux conditions du test que pour certaines valeurs un).
Si cela vous convient, utilisez le test de Miller-Rabin. Bien que cette méthode soit assez lourde à calculer manuellement, elle est souvent utilisée dans les programmes informatiques. Elle offre une vitesse acceptable et produit moins d'erreurs que la méthode de Fermat. Un nombre composé ne sera pas accepté comme nombre premier si les calculs sont effectués pour plus du quart des valeurs. un. Si vous sélectionnez différentes valeurs au hasard un et pour tous, le test donnera un résultat positif, nous pouvons supposer avec un degré de confiance assez élevé que n est un nombre premier.
Pour les grands nombres, utilisez l’arithmétique modulaire. Si vous n'avez pas de calculatrice avec mod sous la main, ou si votre calculatrice n'est pas conçue pour gérer des nombres aussi grands, utilisez les propriétés des puissances et de l'arithmétique modulaire pour faciliter les calculs. Ci-dessous un exemple pour 3 50 (\style d'affichage 3^(50)) module 50 :
- Réécrivez l'expression sous une forme plus pratique : mod 50. Lors de calculs manuels, des simplifications supplémentaires peuvent être nécessaires.
- (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Ici nous avons pris en compte la propriété de multiplication modulaire.
- 3 25 (\style d'affichage 3^(25)) module 50 = 43.
- (3 25 (\style d'affichage (3^(25)) module 50 * 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 * 43) (\displaystyle (43*43)) modèle 50.
- = 1849 (\ displaystyle = 1849) modèle 50.
- = 49 (\ displaystyle = 49).
Définition 1. nombre premier− est un nombre naturel supérieur à un qui n'est divisible que par lui-même et 1.
En d’autres termes, un nombre est premier s’il ne possède que deux facteurs naturels distincts.
Définition 2. Tout nombre naturel qui a d'autres diviseurs que lui-même et l'un d'entre eux est appelé un nombre composé.
En d’autres termes, les nombres naturels qui ne sont pas premiers sont appelés nombres composés. De la définition 1, il s'ensuit qu'un nombre composé a plus de deux facteurs naturels. Le nombre 1 n'est ni premier ni composé car n’a qu’un seul diviseur 1 et, de plus, de nombreux théorèmes concernant les nombres premiers ne valent pas pour l’unité.
Des définitions 1 et 2, il s'ensuit que tout entier positif supérieur à 1 est soit un nombre premier, soit un nombre composé.
Ci-dessous se trouve un programme pour afficher les nombres premiers jusqu'à 5000. Remplissez les cellules, cliquez sur le bouton "Créer" et attendez quelques secondes.
Tableau des nombres premiers
Déclaration 1. Si p- nombre premier et un n'importe quel entier, alors soit un divisé par p, ou p Et un nombres premiers entre eux.
Vraiment. Si p Un nombre premier n'est divisible que par lui-même et 1 si un non divisible par p, alors le plus grand commun diviseur un Et p est égal à 1. Alors p Et un nombres premiers entre eux.
Déclaration 2. Si le produit de plusieurs nombres de nombres un 1 , un 2 , un 3, ... est divisible par un nombre premier p, alors au moins un des nombres un 1 , un 2 , un 3, ...divisible par p.
Vraiment. Si aucun des nombres n'était divisible par p, puis les chiffres un 1 , un 2 , un 3, ... seraient des nombres premiers entre eux par rapport à p. Mais du corollaire 3 () il s'ensuit que leur produit un 1 , un 2 , un 3, ... est également relativement premier par rapport à p, ce qui contredit la condition de la déclaration. Donc au moins un des nombres est divisible par p.
Théorème 1. Tout nombre composé peut toujours être représenté, et de manière unique, comme le produit d'un nombre fini de nombres premiers.
Preuve. Laisser k nombre composé, et laissez un 1 est un de ses diviseurs différent de 1 et de lui-même. Si un 1 est composite, alors a en plus de 1 et un 1 et un autre diviseur un 2. Si un 2 est un nombre composé, alors il a, en plus de 1 et un 2 et un autre diviseur un 3. En raisonnant ainsi et en tenant compte du fait que les chiffres un 1 , un 2 , un 3 , ... diminue et cette série contient un nombre fini de termes, nous atteindrons un nombre premier p 1 . Alors k peut être représenté sous la forme
Supposons qu'il y ait deux décompositions d'un nombre k:
Parce que k=p 1 p 2 p 3...divisible par un nombre premier q 1, alors au moins un des facteurs, par exemple p 1 est divisible par q 1 . Mais p 1 est un nombre premier et n'est divisible que par 1 et lui-même. Ainsi p 1 =q 1 (parce que q 1 ≠1)
Alors de (2) on peut exclure p 1 et q 1:
Ainsi, nous sommes convaincus que tout nombre premier qui apparaît comme facteur dans le premier développement une ou plusieurs fois apparaît également dans le deuxième développement au moins autant de fois, et vice versa, tout nombre premier qui apparaît comme facteur dans le deuxième développement. une ou plusieurs fois apparaît également dans la première extension au moins le même nombre de fois. Par conséquent, tout nombre premier apparaît comme facteur dans les deux développements le même nombre de fois et, par conséquent, ces deux développements sont identiques.
Expansion d'un numéro composé k peut s'écrire sous la forme suivante
| (3) |
Où p 1 , p 2, ... divers nombres premiers, α, β, γ ... des entiers positifs.
L’expansion (3) est appelée expansion canonique Nombres.
Les nombres premiers apparaissent de manière inégale dans la série des nombres naturels. Dans certaines parties de la rangée, il y en a plus, dans d'autres, moins. Plus on avance dans la série de nombres, moins les nombres premiers sont courants. La question se pose : existe-t-il un plus grand nombre premier ? Le mathématicien grec Euclide a prouvé qu’il existe une infinité de nombres premiers. Nous présentons cette preuve ci-dessous.
Théorème 2. Le nombre de nombres premiers est infini.
Preuve. Supposons qu’il existe un nombre fini de nombres premiers et que le plus grand nombre premier soit p. Considérons tous les nombres plus grands p. Par hypothèse de l'énoncé, ces nombres doivent être composés et doivent être divisibles par au moins un des nombres premiers. Choisissons un nombre qui est le produit de tous ces nombres premiers plus 1 :
Nombre z plus p parce que 14h déjà plus p. p n'est divisible par aucun de ces nombres premiers, car lorsqu'il est divisé par chacun d'eux, cela donne un reste de 1. Nous arrivons ainsi à une contradiction. Il existe donc une infinité de nombres premiers.
Ce théorème est un cas particulier d'un théorème plus général :
Théorème 3. Soit une progression arithmétique
Alors tout nombre premier inclus dans n, devrait être inclus dans m, donc dans n d'autres facteurs premiers qui ne sont pas inclus dans m et, de plus, ces facteurs premiers dans n ne sont pas inclus plus de fois que dans m.
L'inverse est également vrai. Si chaque facteur premier d'un nombre n inclus au moins autant de fois dans le nombre m, Que m divisé par n.
Déclaration 3. Laisser un 1 ,un 2 ,un 3,... divers nombres premiers inclus dans m Donc
Où je=0,1,...α , j=0,1,...,β , k=0,1,..., γ . remarquerez que ai accepte α valeurs +1, β j accepte β valeurs +1, γ k accepte γ Valeurs +1, ... .
