Dans cette page, nous allons évoquer les nombres premiers.
Par définition, un nombre premier est un entier naturel qui possède exactement 2 diviseurs entiers positifs distincts : 1 et lui-même.
Par exemple 17 est un nombre premier car ses deux seuls diviseurs sont 1 et 17 (c.a.d. lui-même).
Autre exemple : 16 n’est pas un nombre premier car ses diviseurs sont : 1, 2, 4, 8 et 16.
A noter que 1 n’est pas premier car il possède un seul diviseur (1) et non pas 2 uniques diviseurs distincts.
La liste des nombres premiers est une liste ‘infinie’ commençant par : 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 (A noter qu’il s’agit ici de la liste de tous les nombres premiers inférieurs à 100).
– Crible d’Ératosthène
Dès l’Antiquité, les savants avaient identifié le rôle particulier des nombres premiers en mathématiques.
Ératosthène, au troisième siècle avant notre ère, a donné une méthode pour les identifier, grâce au crible qui porte son nom (Le crible d’Ératosthène).
Il suffit d’écrire les différents nombres entiers et de supprimer successivement chacun des multiples des nombres premiers trouvés.
2 est un nombre premier … on supprime tous les multiples de 2
3 est un nombre premier … on supprime tous les multiples de 3
5 est un nombre premier … on supprime tous les multiples de 5 … etc …
– Conjecture de Gauss
Près de 2000 ans plus tard, le jeune prodige des mathématiques, Carl Friedrich Gauss, à l’âge de 16 ans, a constaté que les nombres premiers se font de plus en plus rares à mesure qu’on les cherche parmi des nombres toujours plus grands (même si on sait qu’il existe une infinité de nombres premiers).
Il a conjecturé que le nombre de nombres premiers inférieurs à une valeur n tend vers n divisé par le logarithme de n : Nombre de nombres premiers < n → n/ln(x) Ce «théorème des nombres premiers » ne sera démontré que cent ans plus tard, en 1896, et indépendamment par Jacques Hadamard et Charles-Jean de La Vallée Poussin.
– Reconnaître un nombre premier
Il est souvent très compliqué de savoir si un nombre entier est premier ou pas.
Plus le nombre sera grand, plus il sera difficile d’avoir rapidement une réponse à cette question.
Néanmoins, il existe quelques règles simples permettant d’avoir un ‘indice’ et parfois de savoir assez aisément si le nombre concerné est premier (et surtout dans la plupart des cas de savoir facilement que le nombre n’est pas premier).
Voici donc quelques règles …
-> Constatation …
Faisons déjà une première constatation : si le nombre n est premier alors 2n – 1 est premier
Cette ‘constatation’ permet de connaître certains nombres premiers (mais pas tous).
Mais cette méthode ne permet pas d’affirmer ou d’infirmer qu’un nombre donné est premier …
→ 1ère règle
Pour tout entier n supérieur ou égal à 5, si n est premier, alors (n-1) ou (n+1) est forcément un multiple de 3.
(Cela signifie que pour un entier n donné, si aucune des 2 valeurs (n-1) et (n+1) n’est divisible par 3, alors n ne peut pas être un nombre premier).
Reprenons le début de la liste des nombres premiers (à partie de 5) : 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
5 + 1 = 6 (= 3 *2)
7 – 1 = 6 (= 3 *2)
11 + 1 = 12 (= 3 *4)
13 – 1 = 12 (= 3 *4)
17 + 1 = 18 (= 3 *6)
19 – 1 = 18 (= 3 *6)
23 + 1 = 24 (= 3 *8)
29 + 1 = 30 (= 3 *10)
31 – 1 = 30 (= 3 *10)
37 – 1 = 36 (= 3 *12)
41 + 1 = 42 (= 3 *14)
43 – 1 = 42 (= 3 *14)
47 + 1 = 48 (= 3 *16)
53 + 1 = 54 (= 3 *18)
…
Bon, OK, fondamentalement cette règle n’est pas très utile.
(Attention, la réciproque n’est pas vraie : si pour une valeur donnée n ; soit (n-1) soit (n+1) est un multiple de 3, cela ne signifie pas que n est forcément premier ; par exemple pour n = 26 , n-1=25(=5*5) ; n+1=27(=3*9); n+1 est bien un multiple de 3, mais 26 n’est pas un nombre premier … aucun des 3 entiers 25, 26, 27 est premier … Condition nécessaire mais pas suffisante …)
→ 2ème règle
Si n est premier (supérieur ou égal à 5), alors (n2-1) est divisible par 3 et (n2-1) est divisible par 8, donc à fortiori, (n2-1) sera divisible par 24.
A noter que n2-1 = (n-1)*(n+1) …. cela peut clairement nous ‘rappeler’ une certaine logique avec la 1ère règle ci-dessus …
Reprenons donc le début de la liste des nombres premiers (à partie de 5) : 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
52 – 1 = 25 – 1 = 24 (= 24 *1)
72 – 1 = 49 – 1 = 48 (= 24 *2)
112 – 1 = 121 – 1 = 120 (= 24 *5)
132 – 1 = 169 – 1 = 168 (= 24 *7)
172 – 1 = 289 – 1 = 288 (= 24 *12)
192 – 1 = 361 – 1 = 360 (= 24 *15)
232 – 1 = 529 – 1 = 528 (= 24 *22)
292 – 1 = 841 – 1 = 840 (= 24 *35)
312 – 1 = 961 – 1 = 960 (= 24 *40)
372 – 1 = 1369 – 1 = 1368 (= 24 *57)
412 – 1 = 1681 – 1 = 1680 (= 24 *70)
432 – 1 = 1849 – 1 = 1848 (= 24 *77)
…
→ 3ème règle
Si n est premier (supérieur ou égal à 7), alors (n4-1) est divisible par 3, par 5 et par 16, donc à fortiori, (n4-1) sera divisible par 240.
A noter que n4-1 = (n2-1)*(n2+1) …. ce qui permet de savoir directement grâce à la 2ère règle ci-dessus que n4-1 est divisible par 3 et par 8.
74 – 1 = 2401 – 1 = 2400 (= 2 * 3 * 52 * 16)
114 – 1 = 14641 – 1 = 14640 (= 3 * 5 * 16 * 61)
134 – 1 = 28561 – 1 = 28560 (= 3 * 5 * 16 * 119)
174 – 1 = 83521 – 1 = 83520 (= 22 * 32 * 5 * 16 * 29)
…
→ 4ème règle (le polynôme d’Euler)
P(n) = n2 + n + 41 est premier pour tous les nombres entiers positifs strictement inférieurs à 40
A noter que P(40) = 1681 = 412. Notons aussi que et si n est un multiple de 41, P(n) sera lui aussi un multiple de 41, donc non premier.
P(0) = 41
P(1) = 43
P(2) = 47
P(3) = 53
P(4) = 61
P(5) = 71
P(6) = 83
… Grâce à ce polynôme, on retrouve la plupart des nombres premiers supérieurs à 41.