Les nombres premiers

Détails: Mis à jour : 14 février 2016; Affichages : 63462

Vote utilisateur: 3 / 5

Les Nombres Premiers

1. Une approche

L'étude des nombres premiers 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 et 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'os d'Ishango et les nombres premiers
L'archéologue Jean de Heinzelin de Braucourt (6 août 1920 — 4 novembre 1998) 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 cet os, daté de plus de 23 000 ans avant notre ère, seraient gravées des représentation de nombres premiers.
On les a considérés d'abord comme des bâtons de comptage mais certains scientifiques pensent qu'il s'agirait d'une compréhension bien plus avancée que le simple comptage.
Cette thèse est rejetée par certains auteurs, dont Olivier Keller.

Os d'Ishango (Museum of Brussel)

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éfinitions
- Un nombre premier est un nombre entier supérieur ou égal à 2 et divisible uniquement par 1 et lui-même.
  ou encore
- Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même).
Exemples
La liste de 10 premiers nombres premiers est alors : $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29$$
Pour avoir les nombres premiers inférieurs à 1 000 : liste de nombres premiers.
Remarques
- L'entier 2 est le seul nombre premier pair ;
- L'entier 1 n'est pas premier car il n'a qu'un seul diviseur entier positif, lui-même ;
- L'entier 0 n'est pas premier car il est divisible par tous les entiers positifs.

Euclide et les nombres premiers : la première définition

Le célèbre mathématicien grec Euclide (III^e 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".

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’Ératosthè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 qu'on a atteint la racine carrée de n.

=> Pour en savoir plus : Le crible.

4. Une infinité de nombres premiers

Euclide (IIIe av. J.-C.) a démontré dans son traité qu'il existait une infinité de nombres premiers.

C'est dans Le livre IX des Éléments, que l'on trouve à la proposition 20, la démonstration par l'absurde de cette proprié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 p₁, p₂,...., p_k.

Alors considérons le nombre $$N = ( p_1\times p_2\times p_3\times \cdots \times p_k ) + 1$$ Si N est premier, alors on a trouvé un nombre premier plus grand que p_k, ce qui contredit l'affirmation.

Sinon, N est composé, alors N est divisible par un nombre premier p qui est forcément un des nombres p₁, p₂, ..., p_k (puisque ce sont les seuls).
De ce fait, il existe un premier noté p_i tel que p_i divise N. Or cela implique que p_i divise 1, et donc que p_i = 1 ce qui est impossible.

Attention au piège suivant.
Si l'on note $$M_k = ( p_1\times p_2\times p_3\times \cdots \times p_k ) + 1$$

La démonstration précédente n'implique pas que M_k soit un nombre premier.

En effet on a : M₁ = 3 ; M₂ = 7 ; M₃ = 31 ; M₄ = 211 ; M₅ = 2 311 qui sont tous premiers,
mais les nombres M₆ = 59 × 509 et M₇ = 19 × 97 × 277 ne le sont pas.

On ne sait toujours pas si cette suite (M_k) contient une infinité de nombres premiers !

5. La recherche de grands nombres premiers

La recherche de grands nombres premiers est toujours d'actualité et les records sont battus régulièrement. On a dépassé la barre des 20 millions de chiffres en 2016, étourdissant !

=> La course au record du plus grand nombre premier

6. Les grands théorèmes

6.a. Théorème des Nombres premiers.

Théorème.
En notant π(x), le nombre de nombres premiers inférieurs ou égaux à x, le théorème des nombres premiers affirme que le rapport x/ln(x) équivaut à π(x) quand x tend vers +∞ soit :

$$\pi(x) \underset{+\infty}{\sim} \dfrac{x}{\ln x}$$

6.b. Théorème de Brun (1885 - 1978).

Théorème.
Notons P l'ensemble des nombres premiers jumeaux, c'est à dire des entiers p tels que p et p+2 soient premiers.
Alors la série suivante est convergente. ([HaSu]^p56)

$$\sum_{p\,\in\, P} \left( \dfrac{1}{p}+\dfrac{1}{p+2}\right)=\left( \dfrac{1}{3}+\dfrac{1}{5}\right)+\left( \dfrac{1}{5}+\dfrac{1}{7}\right)+\left( \dfrac{1}{11}+\dfrac{1}{13}\right)\cdots$$

6.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.

$$\sum_{p\,\in\, P} \left( \dfrac{1}{p}\right)~~\text{diverge}$$

6.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 d'autres termes signifie que, en notant π(m), le nombre de nombres premiers inférieurs ou égaux à m, le rapport π(m)/m tend vers 0 quand m tend vers l'infini.

$$\lim_{m\longrightarrow +\infty}\dfrac{\pi(m)}{m} =0$$

7. Conjectures et questions ouvertes.

Il y a beaucoup de conjectures (affirmation établie empiriquement mais pas démontrée) et de questions ouvertes sur les nombres premiers.

La conjecture de Goldbach : tout nombre pair strictement supérieur à 2 peut s'écrire comme somme de deux nombres premiers.
La conjecture de De Polignac : tout entier naturel pair peut s'écrire comme différence de deux nombres premiers consécutifs et cela d'une infinité de manières.
La conjecture des nombres premiers jumeaux : il existe une infinité de jumeaux premiers (cas particulier de la conjecture de De Polignac pour n=2).
En 2013, une avancée considérable est faite par un modeste professeur d'université concernat cette fameuse conjecture : Nombres premiers jumeaux, une avancée.
Toute suite de Fibonacci généralisée dont les deux termes initiaux sont premiers entre eux contient-elle une infinité de nombres premiers ?
Existe-t-il une infinité de nombres premiers de Fermat ou de Mersenne ?
Y a-t-il une infinité de nombres premiers de la forme n² + 1 ?
Y a-t-il une infinité de nombres premiers factoriels (de la forme n! + 1) ?
La conjecture de Legendre : il existe toujours au moins un nombre premier entre n² et (n+1)² ; cette conjecture est liée à l'hypothèse de Riemann et, comme cette dernière, reste non démontrée à ce jour.

Et bien d'autres ...