|
|
|
|
|
|
|
|
Les nombres premiers ont fasciné des générations de mathématiciens, mais de quoi s'agit-il ?
Un entier naturel est premier s'il n'admet que deux diviseurs : 1 et lui-même.
1 n'est pas premier, c'est une convention.
2, 3, 5, 7, 11 sont premiers.
A partir de cette simple définition, on peut trouver (et prouver) quantité de propriétés sur ces nombres, par exemple :
Tout entier (sauf 1) admet au moins un diviseur premier.
Tout entier naturel supérieur à 1 se factorise de manière unique en produit de nombres premiers.
Il y a une infinité de nombres premiers.
etc.
Certains résultats ne sont toujours pas démontrés, par exemple la conjecture de Goldbach (1690-1764) : Il affirme en 1742, sans le démontrer, que tout entier pair supérieur à deux est la somme de deux nombres premiers.
Ainsi, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 7 + 5, 14 = 7 + 7 ...
Comment savoir si un entier est premier ?
Soit N un entier naturel. Une façon de faire est de dresser la liste des nombres premiers en éliminant tout d'abord les multiples de 2, puis de 3, puis de 5 (les multiples de 4 ont déjà été éliminés comme multiples de deux), etc. C'est le crible d'Erathostène.
Une autre façon de faire pourrait être de tester la divisibilité de N par tous les entiers naturels qui lui sont inférieurs ... Pas très élégant et cela demande de nombreux calculs pour peu que N soit assez grand.
Ici nous allons "diminuer" le nombre des calculs en remarquant que tout entier naturel peut s'écrire sous la forme 6a, 6a+1, 6a+2, 6a+3, 6a+4, 6a+5 pour un certain a entier relatif :
a = 0 : 6a = 0 ; 6a+1 = 1 ; 6a+2 = 2 ; 6a+3 = 3 ; 6a+4 = 4; 6a+5 = 5
a=1 : 6a = 6 ; 6a+1 = 7 ; 6a+2 = 8 ; 6a+3 = 9 ; 6a+4 = 10; 6a+5 = 11
......................
On peut chercher si N est divisible par l'un de ces six nombres (en prenant a = 0, a = 1, ...).
Or, 6a = 2*3*a, c'est un multiple de 2 et de 3, par conséquent, si N est divisible par 6a, il est aussi divisible par 2 et par 3.
6a+2 = 2*(3a+1), si N est divisible par 6a+2, il est aussi divisible par 2.
6a+3 = 3*(2a+1), si N est divisible par 6a+3, il est aussi divisible par 3.
6a+4 = 2*(3a+2), si N est divisible par 6a+4, il est aussi divisible par 2.
Ainsi, si N n'est pas divisible par 2 ou 3 (ce qu'il est facile de vérifier avec les critères de divisibilité), il n'y a plus qu'à vérifier qu'il ne soit pas divisible par 6a+1 ou 6a+5 pour un certain a.
En pratique on peut s'arrêter lorsque 6a+5 est inférieur ou égal à la racine carré de N.
 |
Il permet de dresser la liste des nombres premiers inférieurs ou égaux à N en éliminant successivement les multiples de 2 autres que 2, ceux de 3 autres que 3, ...etc.
Une fois éliminés tous les multiples de i, 2 <= i <= k, le plus petit entier p restant est premier, sinon il aurait un diviseur compris entre 2 et k, ce qui est impossible puisqu'on a éliminé tous leurs multiples.
Il faut ensuite éliminer les multiples de p en commençant par p2, les autres multiples de p : kp avec 2 <= k <= p ont été éliminés comme multiples de k.
 |
 |
C. Grospellier |