L'essence des mathématiques, c'est la liberté.
Georg Cantor
Un nombre premier est un entier naturel qui admet seulement deux diviseurs distincts entiers et positifs : 1 et lui-même. Selon cette définition, 0 et 1 ne sont pas des nombres premiers puisque 0 est divisible par tous les entiers positifs et 1 n'est divisible que par un seul entier positif.
A titre d'exemple, 2, 7, 11 et 29 sont des nombres premiers car ils sont strictement supérieurs à 1 et ne sont divisibles que par 1 et par eux-mêmes. En revanche, 4 et 6, par exemple, ne sont pas des nombres premiers car 4 est à la fois divisible par 1, par 2 et par lui-même, tout comme 6 est à la fois divisible par 1, par 2, par 3 et par lui-même.
Certains mathématiciens admettaient 1 comme un nombre premier, cependant cette théorie a été abandonnée au début du XXᵉ siècle.
Les nombres premiers sont des entiers fondamentaux en mathématiques. Bien qu'ils ne soient pas si peu nombreux qu'on le pense, il faut indiquer dès à présent que plus les nombres sont grands, moins l'on trouve de nombres premiers, sans surprise.
Etudiés dès l'école secondaire en Suisse, les nombres premiers sont utilisés dans des domaines très larges et variés, tels que l'arithmétique, la cryptographie et l'informatique.
1 : ni nombre premier ni nombre composé
2 : nombre premier (divisible par 1 et par lui-même)
3 : nombre premier (divisible par 1 et par lui-même)
4 : nombre composé (divisible par 1, par 2 et par lui-même)
5 : nombre premier (divisible par 1 et par lui-même)
6 : nombre composé (divisible par 1, par 2, par 3 et par lui-même)
7 : nombre premier (divisible par 1 et par lui-même)
8 : nombre composé (divisible par 1, par 2, par 4 et par lui-même)
9 : nombre composé (divisible par 1, par 3 et par lui-même)
...
17 : nombre premier (divisible par 1 et par lui-même)
...
Définition d’un nombre premier
Un nombre est dit "nombre premier" lorsqu'il est un entier naturel qui n'admet que deux diviseurs distincts entiers et positifs, à savoir le nombre 1 et lui-même. Ainsi, tout nombre qui est divisible par plus de 2 diviseurs entiers et positifs est nécessairement un nombre composé, et non pas un nombre premier !
Un nombre premier n'est donc divisible que par lui-même et par 1. La différence entre un nombre premier et un nombre composé tient justement dans cette distinction, voire même cette opposition :
- Le nombre premier ne dispose que de 2 diviseurs possibles, 1 et lui-même
- Le nombre composé dispose d'au moins trois diviseurs distincts et est strictement supérieur à 1
Les nombres premiers sont des entiers naturels supérieurs à 1.
Pourquoi 1 n’est-il pas un nombre premier ?
Le chiffre 1 n'est pas un nombre premier car il ne dispose que d'un seul diviseur strictement positif, à savoir lui-même, le 1. Il ne peut donc disposer de deux divisiteurs distincts !
Pourquoi 2 est-il le seul nombre premier pair ?
En réalité, la réponse est très simple : tout nombre pair supérieur à 2 est nécessairement divisible par 2 ! Donc, cela fait déjà un diviseur en trop : 1, 2 et le nombre pair lui-même. Par exemple :
- 4 est divisible par 1, par 2 et par lui-même
- 6 est divisible par 1, par 2, par 3 et par lui-même
- 8 est divisible par 1, par 2, par 4 et par lui-même
- 10 est divisible par 1, par 2, par 5 et par lui-même
- 12 est divisible par 1, par 2, par 3, par 4, par 6 et par lui-même
- ...
| Nombre | Diviseurs positifs | Premier ou composé ? |
|---|---|---|
| 1 | 1 | Ni premier ni composé |
| 2 | 1, 2 | Premier |
| 6 | 1, 2, 3, 6 | Composé |
| 13 | 1, 13 | Premier |
| 18 | 1, 2, 3, 6, 9, 18 | Composé |
| 29 | 1, 29 | Premier |
| 30 | 1, 2, 3, 5, 6, 10, 15, 30 | Composé |
Comment savoir si un nombre est premier ?
Il existe de nombreuses applications industrielles de l'arithmétique et notamment des nombres premiers.
Alors, tout au long de votre vie, selon votre métier, vous serez confronté à cette notion mathématique !
La question "comment savoir si un nombre est premier ?" n'a pas de réponse fermée puisqu'il n'existe pas de liste exhaustive finie des nombres premiers.
On sait qu'il en existe une infinité, et ce depuis l'Antiquité grâce au théorème d'Euclide sur les nombres premiers.
En revanche, il est possible de connaître les nombres premiers en délimitant une borne d'ouverture et une borne de fermeture. De 0 à 100 par exemple, les nombres premiers sont au nombre de 25 : 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.
Méthode simple : chercher les diviseurs du nombre
La méthode la plus simple et qui vient directement à l'esprit est de chercher les diviseurs du nombre en question. Si aucun entier positif autre que 1 et le nombre lui-même ne le divise sans partie décimale (exemple : 1,5 ou 3,2...), alors le nombre est un nombre entier. Par exemple, le nombre 17 n'est pas divisible par 2 ni par 3, 5 ni aucun autre entier inférieur à 17 ! Il n'est divisible que par 1 et par lui-même, ce qui en fait un nombre premier.
Méthode rapide : tester les diviseurs jusqu’à la racine carrée
La méthode mathématique la plus efficace cependant demeure la suivante : pour savoir si un nombre n est un nombre premier, il faut vérifier s'il est divisible ou non par un nombre premier inférieur ou égal à :
S'il est divisible par l'un d'eux, il s'agit d'un nombre composé. S'il n'est divisible par aucun d'entre eux, alors il s'agit d'un nombre premier.
Exemple avec le nombre 97 :
- √97 est inférieure à 10 (environ 9,84)
- Testez avec 2, 3, 5 et 7, les seuls nombres premiers inférieurs à 10
- 97 n'est divisible par aucun de ces nombres
- 97 est donc un nombre premier !
Exemple avec le nombre 57 :
- √57 est inférieure à 8 (environ 7,55)
- Testez avec 2, 3, 5 et 7, les seuls nombres premiers inférieurs à 8
- 57 est divisible par 3 (3 x 19 = 57)
- 57 n'est donc pas un nombre premier car il possède 4 diviseurs : 1, 3, 19 et 57 (lui-même)
Maintenant, vous savez comment calculer les nombres premiers !
Seuls les diviseurs jusqu’à 9 suffisent !
Le crible d’Ératosthène pour trouver plusieurs nombres premiers
Reposant sur la méthode des essais de division, le crible d'Eratosthène fournit la liste des nombres premiers inférieurs à une valeur donnée. Voici comment faire :
Etape n°1
On commence par former la liste des entiers de 2 à n (120 dans l'exemple)
Etape n°2
Il faut ensuite barrer tous les entiers multiples du nombre 2, en commençant par son carré (4)
Etape n°3
Il faut ensuite barrer tous les entiers multiples du nombre 3, en commençant par son carré (9)
Etape n°4
Il faut ensuite barrer tous les entiers multiples du nombre 5, en commençant par son carré (25)
Etape n°5
Il faut ensuite barrer tous les entiers multiples du nombre 7, en commençant par son carré (49)
Les nombres restants sont des nombres premiers ! La racine carrée de 120 équivaut environ à 10,9. Et comme une démonstration vaut mieux que mille phrases, voici ce que cela donne de 2 à 120 :
Autres algorithmes pour les grands nombres premiers
Il existe d'autres possibilités de reconnaître un nombre premier, à commencer par une variante du crible d'Eratosthène, appelée crible de Sundaram. Le crible de Sundaram consiste à lister les entiers naturels impairs composés grâce à des suites arithmétiques placées en colonne. Par complémentarité, il est ensuite possible de déduire les nombres premiers. Mais il existe encore d'autres méthodes :
- Le crible général des corps de nombres
- Le test de primalité de Solovay-Strassen
- Le test de primalité de Miller-Rabin
- L'algorithme AKS
- Les premiers de Proth
- Les premiers de Woodall
- Les premiers de Cullen
- Le test de Fermat
Règles de divisibilité utiles pour reconnaître un nombre premier
L’une des méthodes pour savoir si un nombre à plusieurs chiffres est premier ou non est de savoir si ce nombre est divisible par deux, trois, quatre ou encore cinq.
Un nombre est-il divisible par 2 ?
Il est nécessaire de regarder le dernier chiffre du nombre. Si ce dernier chiffre est 0, 2, 4, 6 ou 8, alors le nombre est divisible par deux et n'est donc pas un nombre premier. Exemples :
- 23 938 : le dernier chiffre est 8, alors le nombre est divisible par deux (23 938 / 2 = 11 969)
- 347 : le dernier chiffre est 7, alors le nombre n'est pas divisible par deux (347 / 2 = 173,5)
Cela vaut pour tous les nombres. Même si ces derniers ont beaucoup de chiffres, on peut toujours déduire s'il est divisible par deux ou non !
Un nombre est-il divisible par 3 ?
Cela ne fonctionne pas comme pour la division de deux. Pour savoir si un grand nombre est divisible par trois, il est nécessaire de calculer la somme des chiffres du nombre !
Si la somme de tous les chiffres est divisible par trois, alors le nombre d’origine est divisible par trois et n’est donc pas un nombre entier. Exemples :
- 333 : la somme est 9. Le chiffre 9 est divisible par 3, alors le nombre 333 est divisible par 3 (111 x 3 = 333). Même si cela paraît évident pour un tel chiffre, cette méthode est très pratique pour des nombres plus complexes
- 34 567 : la somme de tous les chiffres est 25. Le nombre 25 n’est pas divisible par 3, alors 34 567 n’est pas non plus divisible par 3
Un nombre est-il divisible par 4 ?
Dans ce cas, il faut partir de l’astuce utilisée pour la division par deux. Mais au lieu de prendre le dernier chiffre, il s’agit de regarder les deux derniers chiffres. Si le nombre composé de ces deux chiffres est divisible par 4, alors le nombre d’origine est divisible par 4.
Cependant, cette astuce est bonne à savoir mais peu utile pour les nombres premiers puisqu’il suffit de se servir de l’astuce de la division par deux pour savoir si le nombre est entier !
Un nombre est-il divisible par 5 ?
Pour savoir si un nombre est divisible par 5, rien de plus simple : le dernier chiffre doit être 0 ou 5. Si ce n’est pas le cas, alors le nombre n’est pas divisible par 5 !
Règles utiles supplémentaires : divisibilité par 9, 10 et 11
Pour savoir si un nombre est divisible par 9, il faut vérifier si la somme de ses chiffres est un multiple de 9 (9, 18, 27, 36, 45, 54, 63, 72, 81, 90...). Si c'est le cas, alors le nombre est un nombre entier ! Si ce n'est pas le cas, inversement, alors ce n'est pas un nombre entier.
Reconnaître un nombre divisible par 10 est la chose la plus aisée à réaliser ici : il suffit de vérifier si le nombre en question se termine ou non par 0 !
Si oui, il s'agit alors d'un nombre composé car divisible par zéro, et si non, alors il s'agit d'un nombre qui n'est pas divisible par 10.
En ce qui concerne les nombres divisibles par 11, il faut préciser que la règle est nettement plus complexe, mais qu'une fois celle-ci apprise, il est difficile de l'oublier.
Faites la somme des chiffres de rang impair (1er chiffre, 3e, 5e chiffres...) puis, seulement ensuite, soustrayez la somme des chiffres de rang pair (2e, 4e, 6e chiffres...) en partant de la gauche : si le résultat est 0 ou un multiple de 11, alors le nombre en question est divisible par 11. Si non, alors il n'est pas divisible par 11 !
| Diviseur | Règle rapide | Exemple |
|---|---|---|
| 2 | Se termine par 0, 2, 4, 6 ou 8 | 48 |
| 3 | Somme des chiffres multiple de 3 | 123 (la somme est égale à 6, qui est divisible par 3 car 3x2) |
| 4 | Les deux derniers chiffres forment un nombre divisible par 4 | 316 (16 est divisible par 4, 4x4) |
| 5 | Se termine par 0 ou 5 | 75 |
| 9 | Somme des chiffres multiple de 9 | 729 (729 avec la somme donne 18, soit 9x2) |
| 10 | Se termine par 0 | 120 |
| 11 | Faire la somme des chiffres de rang impair (exemple, dans 7082, additionner 7 et 8 car 1ère et 3ème positions dans le nombre total), puis soustrayez la somme des chiffres de rang impair (ici, 0 et 2 car ils occupent la 2e et la 4e places dans le nombre total). Si le résultat total vaut 0 ou un multiple de 11, alors le nombre est premier | 264 (2+4 = 6 ; 6 - 6 = 0) |
Liste des nombres premiers de 1 à 100
nombres premiers inférieurs à 100.
Voici la liste exhaustive des 25 nombres premiers compris entre 1 et 100 : 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. 2 est le seul et unique nombre premier pair !
Les nombres premiers particuliers
Il existe des nombres premiers particuliers, définis par des contraintes particulières !
Les nombres premiers jumeaux
Les nombres premiers jumeaux sont appelés ainsi en raison de leur proximité mathématique : seul un nombre pair les sépare ! Ainsi, 3 et 5 sont des nombres jumeaux, tout comme 5 et 7, 11 et 13 ou encore 17 et 19.
2 est le seul nombre pair qui est également un nombre entier, ce qui en fait l'exception car 2 et 3 n'ont donc aucun nombre pair entre eux.
Les nombres premiers de Mersenne
Les nombres premiers de la forme :
où p est un entier naturel premier sont appelés "nombres premiers de Mersenne".
nombres premiers de Mersenne, cependant, d'autres sont encore recherchés à l'aide du test de primalité de Lucas-Lehmer.
Par exemple :
- Pour p = 2, nous avons donc : M₂ = 2² - 1 = 3 (3 est un nombre premier)
- Pour p = 3 : M₃ = 2³ - 1 = 7 (7 est un nombre premier)
- Pour p = 5 : M₅ = 2⁵ - 1 = 31 (31 est un nombre premier)
- Pour p = 7 : M₇ = 2⁷ - 1 = 127 (127 est un nombre premier)
Attention : le nombre premier de départ n'assure pas que le résultat donnera nécessairement un nombre premier !
C'est par exemple le cas pour :
- Pour p = 11 : M₁₁ = 2¹¹ - 1 = 2 047 (2 047 n'est pas un nombre premier car il est divisible par 1, par 23, par 89 ainsi que par lui-même)
- Pour p = 29 : M₂₉ = 2²⁹ - 1 = 536 870 911 (536 870 911 n'est pas un nombre premier car il est divisible par 1, par 233, par 2 304 167 et par lui-même)
Les nombres premiers de Fermat
Les nombres de la forme :
sont considérés comme des "nombres de Fermat". Le mathématicien français du XVIIe siècle Pierre de Fermat pensait que tous les nombres correspondant à Fn selon la formule mathématique étaient nécessairement des nombres premiers, or, Leonhard Euler prouva le contraire en 1732 ! Pourquoi ?
!
Il s'agit cependant de l'exception confirmant la règle, jusqu'ici... A part pour le nombre 5, la formule de Fermat fonctionne bien, malgré le fait qu'à ce jour, seuls 5 exemples sont connus et validés. Ainsi, nous avons :
- 3 (pour n = 0)
- 5 (pour n = 1)
- 17 (pour n = 2)
- 257 (pour n = 3)
- 65 537 (pour n = 4)
À quoi servent les nombres premiers ?
Les nombres premiers ont permis de résoudre des problèmes arithmétiques comme le théorème des deux carrés, le théorème des quatre carrés, ou encore la loi de réciprocité quadratique. De plus, on les retrouve dans les entiers de Gauss et les entiers d'Eisenstein ! Il a aussi été vérifié que les nombres premiers ont joué un rôle dans la construction de tables de hachage, mais aussi pour constituer des générateurs de nombres pseudo-aléatoires.
Les nombres premiers en mathématiques
Tout d’abord, le calcul des nombres premiers fait partie des bases de l’arithmétique élémentaire. Ainsi, on a pu dégager le théorème par lequel un nombre composé est divisible en un produit de nombres premiers, et que cette division est unique à l'ordre des facteurs près. Dans un calcul fractionnaire, la décomposition en facteurs premiers facilite la tâche et peut aider à simplifier une formule mathématique.
Ainsi, tout entier supérieur à 1 peut être décomposé de manière unique en produit de nombres premiers, ce qui facillite beaucoup les choses !
Par exemple, on peut décomposer 60 de cette manière : 60 = 2² × 3 × 5. Ou encore 128 de cette manière : 128 = 2⁷. De même, 798 : 2 × 3 × 7 × 19. Et ainsi de suite...
Les nombres premiers en cryptographie
Les nombres premiers ont longtemps été vus comme un sujet purement mathématique, mais ce théorème a par la suite servi pour de nombreuses applications industrielles !
C’est alors qu’entrent en jeu les systèmes cryptographiques et certaines méthodes de transmission de l'information. Cela a donc changé dans les années 1970 avec l'arrivée de nouveaux systèmes de cryptographie. Jusque là, la cryptographie était basée sur une même clé pour chiffrer et déchiffrer un message. Cela s'appelait la cryptographie symétrique.
un système de cryptographie asymétrique est mis au point grâce aux propriétés des nombres premiers et de la factorisation.
Deux clés sont alors utilisées : l'une pour chiffrer, l'autre pour déchiffrer. Le produit de deux grands nombres entiers (200 chiffres) sert pour la clé qui chiffre. Et pour calculer la clé de déchiffrement, il faut connaître ses deux facteurs premiers. Et devinez quoi ? C'est le système utilisé encore aujourd'hui pour créer des signatures numériques !
Bien que nous ne nous en servions pas réellement au quotidien lorsque nous ne travaillons pas dans le domaine, il faut bien garder en tête que les systèmes modernes utilisent de très grands nombres premiers au sein de problèmes mathématiques ultra-difficiles et complexes.
En mathématiques
Décomposition en facteurs premiers
En informatique
Cryptographie et sécurité
En recherche
Etude de leur répartition
Parmi ces nombres, lequel est premier ?
Résumer via IA :
Vous avez aimé l'article ? Notez-le !
Loading...
