II. La suite des nombres premiers est illimitée
Soit en effet un nombre premier quelconque p : il existe un nombre premier supérieur à p.
Formons le produit des nombres premiers jusqu'à p : ce
y6 ARITHMÉTIQUE.
produit sera
iXax3x5X7XiiX...X/?.
Ajoutons I à ce produit, nous formerons le nombre iX2X3x5x7XiiX. ..Xp-hi.
Ce nombre, supérieur à p^ est premier ou admet un diviseur premier; et, dans ce dernier cas, ce diviseur premier doit ôtre supérieur à p; car il ne peut se trouver dans la suite
sans quoi, divisant la première partie du nombre considéré sans diviser la seconde, il ne pourrait diviser ce nombre.
138. III. Formation d'une table de nombres premiers^ Pour former une table des nombres premiers, compris depuis 1 jusqu'à une limite donnée, on écrit tous les nombres depuis I jusqu'à cette limite :
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é (135).
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 e^t 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 i remier.
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, II est un nombre premier.
Cn continue en suivant toujours la même marche {').
(*) La Table I, placée à la fin du volume, fait connaître les nombres premiers compris entre 2 et 355o.
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 labie étant alors nécessairement premiers.
Supposons, par exemple, que la limite de la table soit 260, et qu*on soit arrivé au nombre [Premier 1 9 dont le carré est 289: tous les nombres non barrés sont des nombres premiers. En effet, si un seul de ces nombres n'était pas premier, il admetiraiiun diviseur premier plus grand que i3, puisque tous les multiples de 1 3 ont dû être barrés. Supposons que ce diviseur premier soit 17 ou plus grand que 19. 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 loi-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é elTacé, et tous les nombres non barrés sont bien des nombres premiers.
139. rV. Ce que nous venons de dire prouve évidemment qiïun nombre est premier, lorsqn*il n'est divisible par aucun des nombres premiers dont les carrés sont plus petits que lui; car il ne peut alors être divisible par aucun des nombres premiers dont les carrés le surpassent (13G].
Théorèmes sur les nombres premiers.
140. 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 100 x 36 qui est divisible par 9; 9 étant premier avec 100 divisera 36. En effet, 100 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 (115), de sorte que le plus grand commun diviseur des nombres 100 x 36 et 9 X 36 sera i x 36 ou 36. Tout nombre qui en divise deux autres divise leur plus grand commun diviseur (114); 9 divisant 100 x 36 par hypothèse, et 9X36, parce qu'il est un facteur de ce produit (69), divisera donc 36.
8o ARITHMÉTIQUE.
Il faul remarquer que le théorème n'aurait plus de sens s) 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 7.2 X i5 est divisible par lo, et lo ne divise ni 22 ni i5. Mais les facteurs2ol5 qui composent 10 se retrouvant, l'un dans 22, l'autre dans i5, 10 n*est premier avec aucun des facteurs du produit proposé.
14-1 . II. Lorsqu'un nombre premier divise un produit de plusieurs fadeurs, il divise au moins l'un d'eux.
Soit le produit 89x4^ X 25 qui est divisible par le nombre premier i3, i3 devra diviser l'un des fadeurs du produit. En effet, on peut considérer ce produit comme composé des deux facteurs (39 X 4^) d'une part, 25 de l'autre. Si i3 divise 25, le théorème est démontré; sinon, i3 étant premier sera premier avec 25 (135 ) : divisant le produit (39x42^) X ^5 et étant premier avec 25, il devra diviser le facteur (39 X42) [140]. Mais ( 39 X 4^) peut être regardé comme le produit des deux facteurs 39 et 4». Si i3 divise 4^» le théorème est démontré ; sinon i3 sera premier avec 4^, et, divisant le produit 89X4*» il devra diviser 39; ce quia 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 Alevé à 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.
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 i5' admettraient un diviseur premier commun (136) qui diviserait alors à la fois 22 et i5.
14-2. ni. Tout nombre premier avec les facteurs d'un pro~ duit est premier avec ce produit; réciproquementy tout nom^ bre 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, C, il sera premier avec leur produit P; car s'il admettait avec lui un diviseur premier commun (136), ce divi-
▲niTHMÉTIQUE. 8l
seur devrait diviser au moins Tun [des facteurs A, B, C (l&'l), qui alors ne seraient plus tous premiers avec N.
Réciproquement, si N est premier avec le produit P, il le sera avec tousjes facteurs A, fi, C ; 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.
Ce théorème prouve que, si plusieurs nombres sont premiers entre eux deux à deuxy leur plus petit commun multiple est égal à leur produit [i^'^] \ et il en résulte que tout nombre divisible séparément par plusieurs nombres premiers entre eux deux à deux est dinsible parleur produit ( 128). C'est ce qu'on peut d'ailleurs établir directement comme il suit :
IW. IV. Lorsqu'un nombre est divisible séparément par plusieurs nombres premiers entre eux deux à deux y il est di" visible par leur produit.
Soit le nombre N, divisible séparément par les nombres a^ 6, c, premiers entre eux deux à deux. Si Ton effectue la division de N par a^ on trouve un quotient exact q, et Ton peut poser N = aq. N est divisible par b, le produit aq doit donc Tèire ; mais b est premier avec a, il devra donc diviser q. Si Ton effectue la division de q par b^ on trouve un quotient exact q'y et l'on peut poser q = bq', c'est-à-dire N = abq\ N est divisible par c, le produit abq' doit donc l'être ; mais c, étant premier avec a et avec b, le sera avec leur produit ab ( 142) ; c divisant le produit abq' ou ab X q' et étant premier avec le facteur ab devra diviser q\ Si Ton effectue la division de q' par c, on trouve un quotient exact q", et l'on peut poser q'^zcq", c'est-à-dire TSl = abcq''. N est donc un multiple du produit abc.
144. 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 quelle condition doit remplir un nombre divisible par 66. On remarque que 66= 2 x 3 X n. Les nombres a, 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 suffît qu'il réunisse les caractères de divisibilité par 2, 3 et II (95,96,97).
De c. — Cours, I. 6
8a ARITHMÉTIQUE.
Décomposition d'un nombre en factenrs premiers.
itë. I. Tout nombre qui fCest 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 a ( 136]. Désignons par N' le quotient de N par a : on aura N = aN'. Si N' est premier, le théorème est démontré ; sinon N' admettra un diviseur premier b. Désignons par N'' le quotient de N' par b : on aura N' = ôN", c'est-à-dire N = a6 N'. On répétera pour N" ce qu'on vient de dire pour N'. Si l'on remarque alors que les quotients N', N'', ... vont toujours en diminuant, on voit [qu'on doit finir par arriver à un quotient au moins égal à i, auquel cas le quotient précédent est un nombre premier, puisqu'il n'est 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 considéré un nombre quelconque de fois. Si un nombre contient 3 fois le facteur 2, 1 fois le facteur 3, une fois le facteur 5, comme 36o, on se sert de la notation des exposants (72), et Ton écrit
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.
1&6. II. Un nombre quelconque riest décomposable que d*une seule manière en facteurs premiers.
Supposons que le nombre N soit égal à la fois aux deux systèmes de facteurs premiers ahcdei cSVc'd\ Nous allons prouver que ces deux systèmes sont forcément identiques. En
effet, on a
abcd=a'b'c'd\
a divisant le premier membre doit diviser le second ; mais a étant un nombre premier doit diviser au moins l'un des facteurs du produit a'b'c'd\ et, comme tous ces facteurs sont premiers, il ne peut diviser Fun d'eux que si ce dernier lui est égal(lM, 135).
Supposons a = a'. On pourra diviser le premier membre de I égalité considérée par a et le second par ci : il restera
bcd=ib'&d'.
On pourra répéter pour 6 ce qu'on vient de dire pour a, et l'on prouvera qu'on a, par exemple, b = b\ En continuant le même raisonnement, on démontrera que tous les facteurs du premier système se retrouvent parmi ceux du second, et réciproquement.
Remarquons que le raisonnement indiqué n'exclut pas le cas où quelques-uns des facteurs du premier système sont égaux entre eux ; mais alors ils se répètent en même nombre dans l'autre système.
Les deux systèmes considérés sont donc identiques, nonseulement quailt aux facteurs qui les composent, mais encore quant aux exposants de ces facteurs.
U7, III. Décomposition d'un nombre en ses facteurs premi ers.
Cela posé, prenons pour exemple le nombre 5425a.
Nous commencerons par essayer la division de ce nombre par le plus petit nombre premier après i, c'est-à-dire par 2. Elle réussira, puisque le nombre proposé est pair. On obtient pour quotient 27 126, et l'on a
Les facteurs premiers de 54252 sont donc 2 et les facteurs premiers de 27126. Essayons de nouveau la division de 27126 par 1. On trouve pour quotient i3563, et l'on a
c'est-à-dire
La question est donc ramenée à chercher les facteurs pre-
84 AaiTHMÉTIQUE.
raiers de i3563. La division par 2 n'étant plus possible, il faut essayer la division par le nombre premier suivant, c'està-dire par 3 : elle réussira, puisque la somme des chiffres de i3563 est divisible par 3. On trouve pour quotient 4^21 , et
Ton a
c'est-à-dire
La question est ramenée à chercher les facteurs premiers de 45^1. Lorsqu'on a cessé d'employer un diviseur, on n'a d'ailleurs plus besoin d'y revenir. Ainsi 4^21 ne saurait être divisible par 2, puisque, sans cela, son multiple i3563 le serait. 4^21 est encore divisible par 3, et l'on trouve pour quotient 1507. On a donc
c'est-à-dire
La question est ramenée à chercher les facteurs premiers de 1507. i5o7 n'est plus divisible par 3, ni par 5, puisqu'il est terminé par un 7, ni par 7. Il faut essayer la division par 11 : elle réussira, puisque l'excès de la somme des chiffres de rang impair sur la somme des chiffres de rang pair est égal à ti. On trouve pour quotient 137, et l'on a
i5o7 = II X 137, c'est-à-dire
54252 =:2X2X3x3XiiX 137.
La question est ramenée à chercher les facteurs premiers de 1 37 ; 137 n'étant plus divisible par 1 1, il n'est pas nécessaire d'essayer la division par i3.' Le carré de i3 ou 169 étant supérieur à 137, on peut affirmer que 137 est un nombre premier. En effet, 1 37 n'étant divisible par aucun des nombres premiers dont les carrés sont plus petits que 137 ne sera divisible par aucun des nombres premiers dont les carrés sont plus grands (139).
La décomposition se trouve donc terminée, et l'on a
54252=2X2X3x3XiiXi3'7 0u54252 = 2*X3*XiiXi37.
Voici comment on indique liabiluellemenl le calcul :
ihS. Lorsqu'un nombre est le produit de nombres connus, on abrège l'opération en cherchant les facteurs premiers de ces nombres et en les réunissant ensuite. Ainsi, si Ton a le nombre 26800, on cherche séparément les facteurs premiers de 268 et ceux de 100. On a
par suite
a68 = 2^X67 et ioo = a*x5% 26800 = 2* X 5» X 67.
149. IV. Lorsqu'un nombre est une puissance exacte, les exposants de ses facteurs premiers sont divisibles par le degré de la puissance.
Si Ton a N = N", et si N' = 2» x 3 x 7, on a
c'esi-a-dire
N=2'x^X3»X7' {7ii., 76).
La réciproque est évidente. Si Ton a
on a aussi
150. La table II, placée à la On du volume, donne la décomposition en facteurs premiers des nombres composés compris entre 1 et 355o. Nous avons omis seulement dans cette table les nombres divisibles par les facteurs premiers 2, 3, 5, qu'on découvre facilement. Si un nombre plus petit que 355o et non divisible par un de ces facteurs n'est pas dans, la table II, il est premier et l'on doit le retrouver dans la table I.
86 ÂBITBMÉTIQUE.
On demande, par exemple, de décomposer en facteurs pre mîers les nombres iS'jg, io63, iio3o.
La lable II donne immédiatement
i859 = iiXi3'.
ao63 ne se trouvant pas dans cette table et n'étant divisible ni par 2, ni par 3, ni par 5, est un nombre premier. C'est ce que conûrme la table I.
i'2o3o est divisible par 2, 3 et 5, et le quotient ^oi de iao3o • par le produit 3o de ces facteurs est un nombre premier. On a donc
i2o3o = a X 3 X 5 X 4oï-
ABITHMÉTIQUE. 87
