Formation d'une table de nombres premiers

Pour former une table des nombres premiers, depuis i jus-

(*) La suite des nombres premiers est illimitée. Soit en effet un nombre pre* mier quelconque p : je vais démontrer qu'il existe un nombre premier sopérieur k p. Furmons le produit des nombres premiers jusqu'à ce produit sera ixax3x5X7Xii...X/^. Ajoutons i à ce produit, nous formerons le nombre iXax3x5X7XnX Ce nombre, supérieur à p,

est premier ou admet un diviseur premier; et| dans ce dernier cas, ra diviseur premier doit être supérieur à pt car il ne peut se trouver dans la suite 1 X 2 X 3x5x7X11 X. . ,Xp, sans quoi il diviserait la preinièTe partie du nombre considère sans diviser la seconde.

46 AIllTHMÊTlQUE.

i|u a une limite donnée, on écrit tous les nombres depuis i jusqu’à cette limite :

I 2 3 4 ^ ^ 9 ioiii 2 i 3 t 4 i 5 i 6

On barre alors les nombres de cette suite de 2 en 2, à partir • de 2, comme multiples de 2 : on conserve i et 2, qui sont évidemment des nombres premiers.

Le premier nombre non barré après 2 étant 3, 3 est un nombre premier, puisqu’il n’est pas divisible par les nombres plus petits que lui, sauf l’unité.

On barre les nombres de la suite de 3 en 3, à partir de 3,comme multiples de 3. Le premier nombre non barré après 3 étant 5, 5 est un nombre premier.

On barre les nombres de la suite de 5 en 5, à partir de 5,comme multiples de 5. Le premier nombre non barré après 5 étant 7, 7 est un nombre premier.

On barre les nombres de la suite de 7 en 7, à partir de 7, comme multiples de 7. Le premier nombre non barré après 7 étant II, Il est un nombre premier.

On continuera en suivant toujours la même marche.

Il faut remarquer qu’on doit s’arrêter dès qu’on est parvenu à un nombre premier dont le carré surpasse la limite de la table, tous les nombres conservés dans la table étant alors nécessairement premiers.

Supposons, par exemple, que la limite de la table soit 260, et qu’on soit arrivé au nombre premier 17 dont le carré est 289, je dis que tous les nombres non barrés sont des nombres premiers. En effet, si un seul de ces nombres n’était pas premier, il admettrait un diviseur premier plus grand que i3, puisque tous les multiples de i3 ont dû être barrés. Supposons que ce diviseur premier soit 17 ou plus grand que 17. Puisque le nombre dont il s’agit est compris dans la table, il est inférieur à 289 et contient par suite 17 ou un diviseur plus grand que 17 moins de 17 fois; donc, ou le quotient de sa division par ce diviseur est un nombre premier inférieur à 17, ou ce quotient admet lui-même un diviseur premier plus petit que 17. Le nombre considéré étant nécessairement multiple de ce dernier diviseur, a donc déjà été effacé; et tous les nombres non barrés sont bien des nombres premiers.

106. Ce que nous venons de dire prouve évidemment qu’un nombre est premier, lorsqu’il n’est divisible par aucun

des nombres premiers dont les carrés sont plus petits que lui ; car il ne peut dès lors être divisible par aucun des nombres premiers dont les carrés le surpassent (104).

Théorèmes sur les nombres premiers.

. 107. I. Lorsqu’un nombre quelconque divise un produit de deux facteurs et qu’il est premier avec l’un de ces facteurs, il divise nécessairement l’autre.

Soit le produit loo x 36 qui est divisible par 9; 9 étant premier avec 100 divisera 36. En effet, loo et 9 étant premiers entre eux ont pour plus grand commun diviseur l’unité. Multiplions 100 et 9 par 36, nous multiplierons leur plus grand commun diviseur par 36 (99), de sorte que le plus grand commun diviseur des nombres 100 X 36 et 9 X 36 sera 1 X 36 ou 36. Tout nombre qui en divise deux autres, divise leur plus grand commun diviseur (98); 9 divisant 100 X 36 par hypothèse, et 9 X 36 parce qu’il est un facteur de ce produit (69), divisera donc 36.

Il faut remarquer que le théorème n’aurait plus de sens, si le diviseur considéré n’était pas premier avec l’un des facteurs du produit, c’est-à-dire qu’un nombre quelconque peut diviser un produit de deux facteurs sans diviser l’un d’eux. Ainsi ?.2 X est divisible par 10, et 10 ne divise ni ?.?. ni i5. JMais les facteurs 2 et 5 qui composent 10 se retrouvant, l’un dans 22, l’autre dans i5, 10 n’est premier avec aucun des facteurs du produit proposé.

108. II. Lorsqu’un nombre premier divise un produit de plusieurs facteurs, il divise au moins l’un d’eux.

Soit le produit 39 X 4^ X qui est divisible par le nombre premier i3, i3 devra diviser l’un des facteurs du produit. En effet, on peut considérer ce produit comme composé des deux facteurs (39X4^) d’une part, 26 de l’autre. Si i3 divise 2$, le théorème est démontré; sinon, i3 étant premier, sera premier avec 25 (103) : divisant le produit (39 X 4=*) X 26 et étant premier avec 25, il devra diviser le facteur (39X4’-) [107]. Mais (39X 4*) peut être regardé comme le produit des deux facteurs 39 et 4®. Si i3 divise 42, le théorème est démontré; sinon 1 3 sera premier avec 42. et, divisant le produit 39 x 42, il devra diviser 3g; ce qui a lieu en effet.

On peut déduire de ce théorème les deux conséquences suivantes :

I® Lorsqu’un nombre premier divise une puissance, il divise le nombre élevé à la puissance. Si 7 divise 35% il divise 35. En effet, 7, nombre premier divisant le produit de 3 facteurs égaux à 35, devra diviser l’un d’eux, c’est-à-dire 35.

48 ABITIIMÉTIQL'E.

2 “. Lorsque deux nombres sont premiers entre eux, leurs puissances quelconques sont premières entre elles. Soient les nombres 22 et i5 qui sont premiers entre eux, les puissances 22 ’ et i5’ seront aussi premières entre elles. En effet, s’il n’en était pas ainsi, 22 ’ et 1 5’ admettraient un diviseur premier commun (104) qui diviserait dès lors à la fois 22 et i5.

109. III. Tout nombre premier avec les facteurs d’un produit^est premier avec ce produit; réciproquement, tout nombre premier avec un produit, est premier avec les facteurs de ce produit.

Soit un produit P = ABC. Si N est premier avec les facteurs A, B, G, il sera premier avec leur produit P; car s’il admettait avec lui un diviseur premier commun, ce diviseur devrait diviser au moins l’un des facteurs A, B, G (108), qui dès lors ne seraient plus tous premiers avec N.

Réciproquement, si N est premier avec le prpduitP, il le sera avec tous les facteurs A, B, G; car s’il admettait avec A, par exemple, un diviseur premier commun, ce diviseur diviserait P qui est un multiple de A; P ne serait donc plus premier avec N.

110. IV. Lorsqu’un nombre est divisible séparément par plusieurs nombres premiers entre eux deux à deux, il est divisible par leur produit.

Soit le nombre N, divisible séparément par les nombres a, b, c, premiers entre eux deux à deux. Si l’on effectue la division de N par a, on trouve un quotient exajet q, et l’on peut poser N = aq. N est divisible par b, le produit aq doit donc l’être; mais b est premier avec a, il devra donc diviser q. Si l’on effectue la division Ae q paré, on trouve un quotient exact q' et l’on peut poser q = bq', c’est-à-dire N = abq'. N est divisible par c, le produit aég' doit donc l’être; mais c étant • premier avec a et avec b, le sera avec leur produit «6(109) ; c divisant le produit abq' ou ab X q' et étant premier avec le, facteur «6, devra diviser g'. Si l’on effectue la division de q' par c, on trouve un quotient exact q", et l’on peut poser q' = cq", c’est-à-dire N = rtécç". N est donc un multiple du produit abc.

111. Le théorème qui précède permet de combiner entre eux les caractères de divisibilité déjà obtenus. Supposons qu’on cherche quelles conditions ooit remplir un nombre divisible par 66. On remarquera que 66 =■ 2 x 3 X 1 1 . Les nombres 2 , 3 et 1 1 étant premiers entre eux, tout nombre divisible séparément par ces trois nombres sera divisible par 66. Donc, pour

qu’un nombre soit divisible par 66, il faut et il suffit qu’il réunisse les caractères de divisibilité par 2 , 3 et 1 1 .

Décomposition d'un nombre en facteurs premiers.

112. I. Tout nombre qui n’est pas premier, est un produit de nombres premiers.

En effet, soit le nombre N qu’on suppose n’être pas premier : il admettra un diviseur premier « (104). Désignons par N' le quotient de N par«; on aura N=«N'. Si N' est premier, le théorème est démontre; sinon, IV' admettra un diviseur premier è. Désignons par N" le quotient de N' par/;; on aura N' = /»N", c’est-à-dire N =rt/»N". On répétera pour N" ce qu’on vient de dire pour N'. Si l’on remarque alors que la suite des quotients N', N", etc., va toujours en diminuant, on voit qu’on finira par arriver à un quotient au moins égal à i , auquel cas le quotient précédent sera un nombre premier puisqu’il ne sera divisible que par lui-même.

On en conclut que tout nombre non premier est un produit de nombres premiers.

Remarquons que ces nombres premiers peuvent se trouver répétés dans le produit cofisidéré un nombre quelconque de fois. '

Si un nombre contient 3 fois le facteur 2 , 2 fois le facteur 3, une fois le facteur 5,^comme 36o, on écrira : 36o = 2 ’ x 3’ x 5, en se servant de la notation des exposants.

Quand on cherche les nombres premiers dont le produit constitue un nombre donné, on dit qu’on veut décomposer ce nombre en ses facteurs premiers.

Avant d’indiquer la marche à suivre pour arriver à cette décomposition dans un cas quelconque, il est nécessaire de prouver qu’elle n’est possible que d’une seule manière ;èen d’autres termes, il faut démontrer qu’un nombre n’admet qu’un seul système de facteurs premiers.