Nombres premiers

#1 Préambule

Un nombre premier est un nombre qui est divisible par 1 et lui-même.

Exemple : 17

17 = 17 x 1

à la différence de 8 qui est divisible par 1 et lui-même mais également par 2 et 4 :

8 =   8 x 1   = 2 x 4

Pour rappel, '1' n'est pas qualifié de premier.

#2 Trouver les nombres premiers

1.1 : Par la méthode de la division modulo :

L'ordinateur permet de calculer rapidement les nombres premiers, en utilisant la division 'modulo' (symbole courant en informatique '%') qui donne comme résultat le reste de la division plutôt que le quotient :

8 / 2 = 4  

alors que

8 % 2 = 0

Le principe est le suivant : si le résultat de la division modulo est différent de 0 alors le nombre est un nombre premier.

On procède par étape. On créé une liste des nombres premiers, qui sera mise à jour au fur et à mesure du process. Le premier nombre premier est 2 (le seul à être pair). La liste commence avec l'élément 2 comme ceci : [2].

Ensuite, au nombre suivant, on applique la division modulo en se servant de la liste des nombres premiers comme diviseur. Si le résultat de la division modulo est différent de 0, alors le nombre est premier.

Le nombre suivant est 3. Le diviseur est 2 (liste des nombres premiers)

3 % 2 ≠ 0

3 est premier. Il est ajouté à la liste des nombres premiers qui devient [2, 3]. Puis on continue le process avec les nombres suivants en cherchant les divisions modulo qui donnent un résultat différent de 0.

4 % 2 = 0

5 % 2 ≠ 0
5 % 3 ≠ 0

5 est premier, il s'ajoute à la liste des nombres premiers qui devient [2, 3, 5].
...

La liste des nombres premiers devient [2, 3, 5, 7, 11, 13, 17, ...]. Voici une représentation des nombres premiers.

1.2 : Par la méthode d'Eratosthène :

Ce savant a inventé une méthode révolutionnaire. Il n'est plus nécessaire de calculer des divisions. On utilise en fait la théorie des ensembles. On crée un ensemble de tous les nombres puis des sous-ensembles des multiples (qu'on peut calculer à partir des tables d'addition).

Prenons l'exemple des 20 premiers nombres positifs :

1 2 3 4 5 6 7
8 9 10 11 12
13 14 15 16
17 18 19 20

ajoutons (par simples additions) l'ensemble des multiples de 2 (sauf 2) et l'ensemble des multiples de 3 (sauf 3). [on fait de même avec 1 qui n'est pas premier]

Il n'est pas utile de continuer jusqu'aux muliples de 7, 11, 13, 17 et 19. Eratosthene a noté qu'il fallait s'arrêter au nombre premier inférieur ou egal à la partie entière de la racine carrée de la limite supérieure : ici la limite supérieure est 20 et la partie entière de la racine carrée de 20 - 4,4721 - est 4 : on utilisera comme diviseur, les nombres premiers inférieurs ou égaux à 4 soit 2 et 3.

1 2 3 4 5 6 7
8 9 10 11 12
13 14 15 16
17 18 19 20
 1   4 6 8
10 12 14
16 18 20
 9
15

  2 3
  5 7
11 13
17 19 1   4 6 8
10 12 14
16 18 20
 9
15

On voit le résultat de cette méthode : tous les nombres qui ne sont pas dans les sous-ensembles sont premiers. En enlevant les sous-ensembles, il ne reste que les nombres premiers.

  2 3 5
7 11 13
  17 19

La méthode d'Eratosthene est appelée 'crible d'Eratosthene'.
Elle est plus rapide que la méthode par modulo.

1.3 : Recherche de la primalité "à la main" :

Avec un ordinateur il est facile de calculer si un nombre est premier ou non. Mais est-il possible de le faire avec une feuille et un crayon ?

J'ai trouvé amusant de coder une simulation des calculs dans ce contexte : créer un programme qui simule le comportement d'un humain qui recherche les nombres premiers avec seulement une feuille et un crayon : voir la simulation .

#3 le gap

Un "gap" ('fossé)' est la distance entre 2 nombres premiers. Un gap peut comporter 2, 3 ou 4 nombres, voire 14 ou 15, voire encore davantage.

Par exemple, entre les nombres premiers 1327 et 1361, il y a un gap de 33 nombres.

1300 1301 1302 1303 1304 1305 1306 1307 1308 1309
1310 1311 1312 1313 1314 1315 1316 1317 1318 1319
1320 1321 1322 1323 1324 1325 1326 1327 1328 1329
1330 1331 1332 1333 1334 1335 1336 1337 1338 1339
1340 1341 1342 1343 1344 1345 1346 1347 1348 1349
1350 1351 1352 1353 1354 1355 1356 1357 1358 1359
1360 1361 1362 1363 1364 1365 1366 1367 1368 1369
1370 1371 1372 1373 1374 1375 1376 1377 1378 1379
1380 1381 1382 1383 1384 1385 1386 1387 1388 1389
1390 1391 1392 1393 1394 1395 1396 1397 1398 1399

Un "triangle des bermudes" des nombres premiers : 33 nombres qui se suivent sans qu'un seul ne soit premier. Mais ce vide est en fait un plein : ce vide de nombres premiers est en fait un plein de nombres multiples. Les nombres premiers et les nombres multiples sont les deux faces d'une même pièce.

Dans une dizaine (par exemple de 10 à 19), la moitié est paire : 10 12 14 16 18, il ne reste que 5 nombres impairs : 11 13 15 17 et 19. Les nombres se finissant par 5 sont multiples de 5 et donc jamais premiers, il ne reste plus que 4 nombres impairs susceptibles d'être premiers (4/10 = 40 % de probabilité).

Dans notre exemple, il y a 33 nombres qui forment le gap : d'une part les nombres pairs et divisibles par 5 et d'autre part les nombres impairs susceptibles d'être premiers mais qui ne le sont pas.

Les premiers sont au nombre de 20 soit 61 % des 33 nombres (1328 1330 .32 .34 .36 .38 1340 1342 .44 .46 .48 1350 1352 .54 .56 .58 1360 + 1335, 1345 et 1355 soit 17 + 3 = 20)

Les autres sont au nombre de 13 soit 39 % (1329, 1331, .33 .37 .39 1341 1343 .47 .49 1351 1353 .57 .59). Parmi ces 13 nombres qui se suivent, aucun n'est premier. Ils sont tous multiples d'un nombre premier diviseur :

1329:   3 x 443

1331 : 11 x   21
1333 : 31 x   43
1337 :   7 x 191
1339 : 13 x 103

1341 :   3 x 447
1343 : 17 x   79
1347 :   3 x 449
1349 : 19 x   71

1351 :   7 x 193
1353 :   3 x 451
1357 : 23 x   59
1359 :   3 x 453

Cela signifie que 13 nombres impairs qui se suivent sans interruption (sans compter les nombres impairs se terminant par un 5) sont des multiples des tables de 3, 7, 11, 13, 17, 19, 23, et 31. Cette configuration semble exceptionnelle, 13 nombres impairs sans aucune coupure par un nombre premier. Et il existe des gap encore plus grands.

#4 Changement de perspective

Lors de l'affichage de la liste des nombres premiers, on les a insérés dans des tableaux de 10 lignes sur 10 colonnes.

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
...

Cependant, en regardant ces tableaux de nombres premiers (ceux qui sont supérieurs à 10), on remarque qu'il se terminent toujours par 1, 3, 7 ou 9.

On pourrait afficher les nombres premiers dans un tableau de 4 colonnes uniquement.

01 03 07 09
11 13 17 19
21 23 27 29
31 33 37 39
41 43 47 49
...

De plus, au lieu d'afficher chaque nombre précisèment, on pourrait le représenter par une case dans un tableau de 4 colonnes, où chaque colonne représente les nombres se finissant par 1, 3, 7 ou 9. Les cases représentant un nombre premier seraient mises en rouge.

Ce qui donnerait ceci :

    0                     100
1  3  7  9                      
00       00
10       10
20       20
30       30
40       40
  ...                       ...

= nbre premier

Cette façon de visualiser les nombres premiers permet de voir la densité des nombres premiers dans chaque centaine. Voir ici la représentation par cases.

Une autre façon d'afficher les nombres premiers, serait de les afficher sur plusieurs dizaines de colonnes. Lorsqu'on les affiche sur 10 colonnes, on voit apparaître les 4 colonnes de nombres premiers : 1 3 7 9.

Mais dans ces 4 colonnes, il n'y a pas que des nombres premiers. Se peut-il qu'un certain affichage ne fasse apparaître que des colonnes de nombres premiers ?

En affichant sur 60 colonnes par exemple (il faut avoir un grand écran), une séparation s'opère. Certains nombres se finissant par 3 par exemple et qui ne sont pas premiers, apparaissent dans des colonnes distinctes. Exemple : la colonne commençant par '3' (de même, la colonne '33') : tous les nombres de cette colonne sont divisibles par 3.

60x0: 001 002 003 004 005 006 007
60x1: 061 062 063 064 065 066 067
60x2: 121 122 123 124 125 126 127
60x3: 181 182 183 184 185 186 187
60x4: 241 242 243 244 245 246 247
60x5: 301 302 303 304 305 306 307
60x6: 361 362 363 364 365 306 367

En 60 colonnes, une symétrie apparait avec pour centre la colonne 30.

022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038
082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278
322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338
382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398
442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458

Voici l'image des 5.640 premiers nombres affichés sur 60 colonnes.

#5 factorisation des nombres premiers

On peut factoriser les nombres premiers sous la forme (2 * n) - 1 :

n=1 : 2*n -1 = (2 x 1) - 1 = 1
n=2 : 2*n -1 = (2 x 2) - 1 = 3
n=3 : 2*n -1 = (2 x 3) - 1 = 5
n=4 : 2*n -1 = (2 x 4) - 1 = 7
n=5 : 2*n -1 = (2 x 5) - 1 = 9 = 3 x 3
n=6 : 2*n -1 = (2 x 6) - 1 = 11
n=7 : 2*n -1 = (2 x 7) - 1 = 13
n=8 : 2*n -1 = (2 x 8) - 1 = 15 = 3 x 5
n=9 : 2*n -1 = (2 x 9) - 1 = 17
n=10 : 2*n -1 = (2 x 10) - 1 = 19
n=11 : 2*n -1 = (2 x 11) - 1 = 21 = 3 x 7
n=12 : 2*n -1 = (2 x 12) - 1 = 23

(2*n)-1 est en fait la signature des nombres impairs.

Pour rappel, multiplier un nombre par 2 donne toujours un nombre pair (2x7=14; 2x9=18 ...). il suffit d'enlever 1 au nombre pair pour avoir un nombre impair d'où la factorisation sous la forme (2 * n) - 1.
Il est également possible d'avoir la forme (2 * n) + 1 : à partir du nombre pair, soit on retient le nombre impair inférieur (-1) soit supérieur (+1).

Comme les nombres premiers (sauf 2) sont toujours impairs, la signature des nombres premiers se superpose, partiellement, à la signature des nombres impairs.

(2*n)-1 n'est pas spécifique aux nombres premiers. Cette factorisation donne les nombres premiers mais également les multiples de 3 (à partir de 32), de 7 (à partir de 72), 11 (...), 13(...), etc. Une autre factorisation possible est est celle basée sur la forme (6 * n) - 1 et (6 * n) +1. Cette factorisation permet de supprimer les multiples de 3 :

(6 * 1)  - 1 = 5
(6 * 1) + 1 = 7

(6 * 2)  - 1 = 11
(6 * 2) + 1 = 13

(6 * 3)  - 1 = 17
(6 * 3) + 1 = 19

(6 * 4)  - 1 = 23
(6 * 4) + 1 = 25

(6 * 5)  - 1 = 29
(6 * 5) + 1 = 31

(6 * 6)  - 1 = 35
(6 * 6) + 1 = 37
...

voir ici la forme de factorisation 6n-1 et 6n+1