Sommaire |
Liens connexes |
|---|
1. Histoire de la notion de nombre premier.
L'étude des nombres dit "premier" fait partie d'une branche des mathématiques que l'on nomme l'arithmétique.
L'arithmétique fut longtemps considérée comme la partie noble des mathématiques en ce sens qu'elle était la seule à n'avoir quasiment aucune application concrète. Jusqu'au 19ème siècle, elle reste une des uniques composantes des mathématiques développées par seule curiosité et défi intellectuel.
Ce n'est que depuis l'arrivée des ordinateurs au 20ème siècle, que les nombres premiers ont trouvé une utilisation pratique.
Ils sont en effet à la base de TOUS les systèmes de cryptographie actuels. Les codages militaires, bancaires et internet utilisent tous des propriétés des nombres premiers.La première trace incontestable de la présentation des nombres premiers se trouve dans les Éléments d’Euclide (tomes VII à IX).
Euclide (IIIe av. JC) donne la définition des nombres premiers, la preuve de leur infinitude dans une démonstration restée célèbre.
Il propose aussi une définition du pgcd et du ppcm, et les algorithmes pour les déterminer, aujourd’hui appelés algorithmes d’Euclide.
Il semble cependant avéré que les nombres premiers étaient déjà étudiés bien avant lui.
L'archéologue Jean de Heinzelin de Braucourt a découvert en 1950 un os, l'os d'Ishango, au bord du lac Édouard dans la région d'Ishango au Congo belge (maintenant République démocratique du Congo).
Sur cette os, daté de plus de 23 000 ans avant notre ère, sont gravées des représentation de nombres premiers, étonnant !
Source : Science Museum of Brussels.
2. Définitions
Précisons tout d'abord que pour les mathématiciens de l'antiquité, un nombre est un entier (de l'ensemble IN) ou une fraction.
En outre, les considérations géométriques étant reines à l'époque, un nombre est souvent le représentant de la longueur d'un segment (d'une droite pour Euclide, IIIe av. JC).Voici la définition mathématique actuelle d'un nombre premier.
Définition : Un nombre est dit premier lorsque ce nombre est un nombre entier supérieur ou égal à 2 et divisible uniquement par 1 et lui même.
De ce fait, 2 est le seul nombre premier pair.Le célèbre mathématicien grec Euclide ( IIIe av. JC), donne dans le livre VII de ses "Éléments" les définitions d'une unité, d'un nombre, d'un nombre pair et d'un nombre premier.
- Définition 1 : L'unité est ce selon quoi chacune des choses existantes est dite une.
- Définition 2 : Un nombre est un assemblage composé d'unités.
- [....]
- Définition 6 : Le nombre pair est celui qui peut se partager en deux parties égales.
- [...]
- Définition 12 : Le nombre premier est celui qui est mesuré par l'unité seule.
- Définition 14 : Le nombre composé est celui qui est mesuré par quelque nombre.
D'après "Les Éléments d'Euclide", traduites littéralement par F. Peyrard, Librairie scientifique et technique Albert Blanchard, 1993, page 180.
Notons de suite que pour Euclide ( IIIe av. JC), UN n'est pas un nombre, est UN ce qui est.
L'idée de nombre qu' Euclide présente dans son traité est donc géométrique. Pour lui, un nombre A est mesuré par un nombre B si l'on peut faire tenir A un nombre de fois donnée dans B.
Dans le langage moderne cela revient à dire que "A mesure B" si "B est un multiple de A".Par exemple le nombre 5 mesure 15 car 15 = 3 × 5.
Il sous entend que si "A mesure B", alors A est plus petit strictement que B, Il n'a donc pas besoin de préciser dans sa définition d'un nombre premier que ce nombre n'est pas divisible par lui-même.
3. Le crible d'Eratosthène (IIIe av. JC)
La façon la plus simple de trouver des nombre premiers est un algorithme appelé, crible d'Eratosthène (IIIe av. JC).
Astronome, géographe et mathématicien, nommé à la tête de la bibliothèque d'Alexandrie, il est resté célèbre pour son crible et pour avoir le premier mesuré le méridien terrestre.
Le crible.
L'idée est simple, pour obtenir les nombres premiers inférieurs à n.
- Écrire tous les entiers de 2 à n,
- Enlever (ou barrer) les multiples de 2 sauf 2,
- Récupérer le plus petit nombre nom barré, c'est à dire 3, et barrer les multiples de 3 sauf 3,
- etc...
- Test d'arrêt : On s'arrête dès q'on a atteint la racine carrée de n.
Voici une jolie animation du crible trouvée sur internet.
Image présentant la méthode du crible d'Eratosthène
Source: German Wikipedia, original upload 13. Okt 2004 by SKopp (selfmade) Modified by Emmanuel JARRI to cycle quicker.
La démonstration est assez simple, je vous la propose en annexe pour ne pas alourdir l'exposé.
4. Une infinité de nombres premiers.
Euclide ( IIIe av. JC) a démontré dans son traité qu'il existait une infinité de nombres premiers.
C'est dans Le livre IX des ses Eléments, que l' on trouve à la proposition 20, la démonstration par l'absurde de cette propiété.
- Théorème : Il existe une infinité de nombre premiers
Démonstration :
Supposons le contraire, c'est à dire qu'il existe un nombre fini de nombre premiers disons p1, p2,...., pk.
Alors considérons le nombre N = ( p1 × p2 × ... × pk ) + 1.
Si N est premier, alors on a trouvé un nombre premier plus grand que pk, ce qui contredit l'affirmation.Sinon, N est composé, alors N est divisible par un nombre premier p qui est forcement un des nombres p1, p2, ..., pk (puisque ce sont les seuls).
De ce fait, il existe un premier noté pi tel que pi divise N = ( p1 × p2 × ... × pk ) + 1.
Or cela implique que pi divise 1, et donc que pi = 1 ce qui est impossible.
Remarque : Pour être précis, le fait que pi divise N et le produit ( p1 × p2 × ... × pk ) implique que :
N= p1 × a et que ( p1 × p2 × ... × pk ) = p1 × b et donc que p1 × (a - b) = 1 soit p1 divise 1.Attention au piège suivant.
Si l'on note Mk = ( p1 × p2 × ... × pk ) + 1.
La démonstration précédente n'implique pas que Mk soit un nombre premier.En effet on a : M1 = 3 ; M2 = 7 ; M3 = 31 ; M4 = 211 ; M5 = 2 311 qui sont tous premiers,
mais les nombres M6 = 59 × 509 et M7 = 19 × 97 × 277 ne le sont pas.Actuellement (en 2007), on ne sait toujours pas si cette suite (Mk) contient une infinité de nombres premiers.
5. Les grands théorèmes .
5.a. Théorème des Nombres premiers.
Théorème.
En notant π(x), le nombre de nombres premiers inférieurs ou égaux à x : π(x) ~ x/ ln(x) , quand x → +∞Histoire.
Legendre (1752-1833) et Gauss ( 18e) conjecturent que π(x) ~ x/ ln(x).
Cependant leur démonstration reste empirique et il faut attendre J. Hadamard et C.J. de La Vallée-Poussin en 1896 pour en obtenir la première démonstration de ce théorème.
Le théorème de raréfaction de Legendre en est alors une conséquence.
Les premières démonstrations font intervenir des notions d'analyse complexe délicates. En 1948, P. Erdös et A. Selberg obtinrent des démonstrations ne faisant intervenir que de l'analyse réelle.
Références : [Delah1]p199 et [KoMe] p 95
5.b. Théorème de Brun (1885 - 1978)
P étant l'ensemble des nombres premiers p tels que p+2 est un nombres premiers (on dit qu'ils sont jumeaux), la série suivante est convergente. ([HaSu]p56)
Ce théorème est à rapprocher avec le théorème dit de raréfaction d'Euler (1707-1783) qui nous dit que la somme des inverse des nombres premiers tend vers l'infini.
5.c. Théorème de raréfaction d'Euler (1707-1783)
Théorème.
La somme des inverses des nombres premiers tend vers l'infini, (on dit qu'elle diverge).
Historique.
Euler (1707-1783) démontre ce théorème en 1737.
Le théorème de Legendre (1752-1833) prouve la raréfaction des nombres premiers mais ici Euler indique que cette raréfaction n'est pas très rapide. ([Delah1]p204)La démonstration de ce théorème d'Euler induit un encadrement de la somme des inverses des nombres premiers inférieurs à n entre ln( ln(n) ) et ln( ln(n) ) + 1.
5.d. Théorème de raréfaction de Legendre(1752-1833)
Théorème.
L'ensemble des nombres premiers admet une densité limite nule. Ce qui en termes mathématiques donne :
En notant π(m), le nombre de nombres premiers inférieurs ou égaux à m, π(m)/m → 0 quand m → +∞Histoire.
Ce théorème est démontré par Legendre en 1808.
Ce dernier conjecture que π(x) ~ x/ ln(x) mais sa démonstration reste empirique et il faut attendre J. Hadamard et C.J. de La Vallée-Poussin en 1896 pour en obtenir la première démonstration de ce que l'on nomme le théorème des nombres premiers. Le théorème de raréfaction de Legendre en est alors une conséquence.Références : [Delah1]p199 et [KoMe] p 95