ÉLÉMENTS SIMPSON (II) …

4) Nombres Premiers

Simon Singh donne deux ou trois indications élémentaires sur les nombres premiers et s'intéresse à une des démonstrations prouvant que leur suite est infinie. La littérature sur le sujet est immense, il n'est donc pas question de creuser. Il faut simplement savoir qu'un entier naturel (un entier au sens habituel: {0, 1, 2, 3, 4, ….}) est dit premier si et seulement si il possède deux diviseurs et deux seulement (qui sont alors nécessairement 1 et lui-même, ce qui écarte 1 de la définition). Le plus petit entier premier est 2.

On peut les déterminer à la main par le crible d'Eratosthène, mathématicien grec du III° siècle avant J.C. Question de patience.

Si on cherche par exemple les nombres premiers inférieurs à 100, on écrit la liste de tous les entiers de 1 à 100 :

1 2 3 4 5 6 7 8 9 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

Les nombres premiers de la liste commencent avec 2 et au-delà de 2, sont tous les nombres qui (1 mis à part) n'ont d'autre diviseur qu'eux-mêmes, donc qui ne sont multiples d'aucun des nombres les précédant.

Eratosthène prend la question à l'envers. Il ôte 1 qui n'est pas premier. Puis il raye (ci-après, en rouge) tous les multiples de 2 (sauf 2). Ensuite, il raye (ci-après en vert) tous les multiples (sauf lui) du premier entier non rayé qui succède à 2 (c'est 3) et qui ne sont pas déjà rayés, puis (ci-après en bleu), tous les multiples (sauf lui) du premier entier non rayé (c'est 5) qui succède à 3 et qui ne sont pas déjà rayés, etc.

Quand il en a fini, les seuls entiers non rayés (ici en italique, noir et en gras) sont les entiers premiers de la liste des entiers inférieurs ou égaux à 100.

2 3 4 5 6 7 8 9 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

Soit, la liste des nombres premiers inférieurs à 100: {2 3 5 11 13 17 19 23 29 31 41 43 47 53 59 61 67 71 73 79 83 89 97}

Tout nombre entier est premier ou s'écrit comme produit de nombres premiers. L'écrire effectivement ainsi, c'est "le décomposer en produit de nombres premiers". On peut, tant que la grandeur de l'entier est raisonnable, faire assez bien cette décomposition "à la main" (en fait avec une petite calculatrice) en testant la divisibilité du nombre par un nombre premier qui le précède (le résultat de la division est-il entier?).

On peut remarquer que si l'on peut écrire : n=ab , et si on suppose a≤b, alors a²≤ab, soit a²≤n, soit a≤√n. Il suffit donc de tester les nombres premiers au plus égaux à √n dans la recherche des diviseurs premiers de n. Dès lors, la liste ci-dessus de nombres premiers inférieurs à 100 suffit pour décomposer les entiers inférieurs à 10 000.

Un exemple: le nombre 7781 est-il premier?

√7781 = 88,2099…

Il suffit donc de tester sur les nombres premiers inférieurs à 89 : {2 3 5 11 13 17 19 23 29 31 41 43 47 53 59 61 67 71 73 79 83}.

Il est clair que 7781 n'est pas divisible par 2 car impair, ni par 3 (critère de divisibilité par 3 : somme des chiffres multiple de 3, or ici : 7+7+8+1=23), ni par 5 (critère de divisibilité : dernier chiffre 0 ou 5) . Il suffit donc de tester sur : {11 13 17 19 23 29 31 41 43 47 53 59 61 67 71 73 79 83}.

Après échec pour : {11 13 17 19 23 29}, on obtient 7781/31=251, soit 7781=31x251.

√251= 15,842 …

Donc, si 251 n'était pas un nombre premier, il serait divisible par un nombre premier inférieur à 16, qui du coup diviserait aussi 7781. Or on les a testés pour un résultat négatif.

Donc, 251 est premier et la décomposition de 7781 en produit de nombres premiers est acquise: 7781=31x251.

Bien entendu, dans la décomposition en produit de nombres premiers, un diviseur premier peut intervenir "plusieurs fois".

Ainsi, décomposons : 27783

2+7+7+8+3=27. 27 est un multiple de 9. Donc, 27783 est divisible par 9 : 27783 = 9x3087

Mais 3+0+8+7= 18. Donc, 3087 est encore divisible par 9. 3087=9x343

On teste 343 pour les nombres premiers inférieurs à √343 = 18,52…, soit {2, 3, 5, 7, 11, 13}

343 est impair, non terminé par 0 ou 5, et 3+4+3=10 n'est pas multiple de 3. Donc 2, 3 et 5 sont exclus.

On teste pour 7 : 343/7=49, soit 343=7x49. Mais 49=7².

Finalement : 27783=9²x7x7²=(3²)²x7³=3⁴x7³

On rappellera pour mémoire que sur la base de leurs décompositions, on détermine aisément le pgcd (plus grand commun diviseur) et le ppcm (plus petit commun multiple) de deux nombres qui sont d'un usage constant.

Le ppcm intervient constamment dans le calcul sur les fractions.

Ainsi : 5/252 + 11/702 = ?

252 = 2²x3²x7

702 = 2x3³x13

ppcm: comme multiple de 252 et de 702, le ppcm doit contenir tous les facteurs premiers de chacun de ces deux nombres et s'il y en a un qui est commun, nécessairement avec le plus grand exposant. Et comme on cherche le plus petit multiple, il n'en contiendra pas d'autre.

ppcm = 2²x3³x7x13 = 9828

ppcm = 252x(3x13) = 702x(2x7)

5/252= (5x3x13)/9828 = 195/9828

11/702 = (11x14)/9828 = 154/9828

5/252 + 11/702 = 195/9828  + 154/9828  = (195+154)/9828 = 349/9828

La fraction obtenue peut-elle se réduire, se simplifier (sinon elle est dite irréductible).

Elle ne peut l'être que par un diviseur de 9828, et devrait donc l'être par 2 ou 3 ou 7 ou 13.

2 est exclu (349 est impair), 3 est exclu (3+4+9=16). On a vu 343=7³. 343 est un multiple de 7, donc 349 = 343 + 6 ne peut pas être divisible par 7.

Enfin : 349 = 390 – 41 ; 41 = 390 – 349 = 13x30 – 349

349 n'est pas multiple de 13 sinon ce serait aussi le cas de 41.

La fraction est irréductible, le calcul est terminé.

Bilan définitif : 5/252 + 11/702 = 349/9828

Le pgcd fait les beaux jours des exercices de répartition qui fleurissent dans les collèges.

Ainsi: On dispose de 6435 chocolats  et de 5577 bonbons acidulés. Comment les répartir  dans B boîtes-cadeaux identiques, B étant le plus grand possible,  contenant toutes le même nombre C de chocolats et A de bonbons?

On devra avoir : 6435 = BxC et 5577 = BxA

B apparaît donc comme un diviseur commun à 6435 et à 5577.

On le veut maximum. B sera donc le pgcd de 6435 et de 5577.

On décompose ces deux nombres en produit de facteurs premiers.

6435?

6435 = 5x1287

1+2+8+7 = 18, donc 1287 est divisible par 9 : 1287 = 9x143

Et clairement : 143 = 11x13

6435 = 3²x5x11x13

5577 ?

5+5+7+7=24, donc 5577 est divisible par 3 : 5577 = 3x1859

√1859 = 43,11…

Inutile de tester 2, 3, 5. On teste 7 . Négatif. On teste 11 : 1859/11 = 169

Donc: 1859 = 11x169. Or, 169 = 13²

Finalement : 5577 = 3x11x13²

Un diviseur commun devra contenir des facteurs communs aux deux décompositions et pour avoir le plus grand, le plus de facteurs possibles avec le plus grand exposant possible. Ce qui revient à choisir les nombres premiers communs avec le plus petit des deux exposants.

pgcd = 3x11x13 = 429

6435 = 429x3x5 = 429x15

5577 = 429x13

On pourra remplir 429 boîtes-cadeaux, avec dans  chacune 15 chocolats et 13 bonbons.

429 boîtes-cadeaux !!! Joyeux Noël !!!