CHAPITRE V

155. Un nombre premier est un nombre qui n admet pas d'autre diviseur que lui-même et Vuniié (*).

Ainsi 7 est un nombre premier, parce qu'il n'est divisible par aucun des nombres 2, 3, 4, 5, 6.

Le mot premier a déjà été introduit au n® 140, dans un sens différent : 4 et 15 sont premiers entre eiur, ou 4 est premier avec 15; dans ce sens, il est question de deux nombres ; c'est relativement à Tun que Tautre est premier. Au contraire 7 est premier absolu.

Tout nombre premier (absolu) est premier relativement à un nombre qu'il ne divise pas; ainsi 7 est premier à 15 qu'il ne divise pas; en effet, d'une part 7 ne divise pas 15, d'autre part tout nombre autre que 1 et 7 ne peut diviser 7, et par conséquent ne peut diviser 7 et 15. 7 n'est pas premier à 14 qu'il divise. En particulier, tout nombre premier absolu est premier relativement à tout nombre plus petit que lui.

156. Tout nombre qui n'est pas premier* admet un diviseur premier, autre que un.

En effet, un nombre a qui n'est pas premier admet des diviseurs plus petits que lui, autres que un ; le nombre de ces diviseurs est limité ; le plus petit d'entre eux, è, est premier, car autrement il admettrait un diviseur plus petit que lui, autre que un, et ce diviseur diviserait a; donc b ne serait pas le plus petit des diviseurs de a.

157. La suite des nombres premiers est illimitée. Cet énoncé veut dire que, si l'on donne un nombre premier quelconque, il y en a un plus grand.

Supposons, en effet, qu'il y ait un nombre premier p plus grand que tous les autres. Formons le produit de tous les nombres qui ne sont pas supérieurs à p, produit que nous représenterons par 1. 2. 3... p; ajoutons 1 à ce produit; de deux choses Tune : ou le nombre ainsi formé,

est premier, et alors il est plus grand que p; ou il n'est pas pre-

I. Quelques auteurs do comptent pas un parmi les nombres premiers.

mier; dans ce dernier cas, il admettrait un diviseur premier, autre que un ; mais ce diviseur ne peut être un des nombres 2, 3,..., /> ; car alors, divisant la somme 1.2. 3... /) + 1 et Tune des parties de cette somme, i. 2. 3... p, dans laquelle il entre en facteur, il diviserait la seconde partie, qui est un ; il est donc plus grand que p ; dans les deux cas, il est prouvé qu'il existe un nombre premier plus grand que p.

158. Dans ce numéro et dans le suivant, afin d'éviter des répétitions fastidieuses, je ne regarderai pas le nombre un comme un nombre premier ; en parlant des diviseurs premiers d'un nombre, j'entendrai donc les diviseurs autres que un. Enfin, en parlant des multiples d'un nombre, j'entendrai les multiples obtenus en multipliant ce nombre par un facteur plus grand que un.

Ceci posé, j'établirai d'abord le lemme suivant :

Si le nombre A est inféHeur au carré du nombre a et s'il n'est divisible par aucun des nombres premiers inférieurs à a, on peut affirmer que le nombre A est premier.

Supposons, en effet, que les conditions imposées au nombre A soient réalisées et que, cependant, il ne soit pas premier : soit alors p le plus petit nombre premier qui divise A, on aura

en désignant par q le quotient de la division de Apar p; puisque A n'est divisible par aucun nombre premier inférieur à a, p est au moins égal k a; q est donc inférieur à a, puisque le produit de deux nombres égaux ou supérieurs à a serait au moins égal à a X a et, par conséquent, plus grand que A ; mais A est divisible par 7, et par n'importe quel diviseur premier de 9, c'est-à-dire par un nombro premier inférieur ou égal à q, et, dans tous les cas, moindre que a. La contradiction est manifeste.

159. Fo)*maiion d'une table de nombres premiers. — Soit maintenart à construire une table de nombres premiers inférieurs ou égaux à un nombre donné N. J'écris la suite naturelle

des nombres, depuis 2 jusqu'à N. 2 est premier; je barre tous les multiples de 2 ; c'est à 2 X 2 qu'il faut commencer. Après 2, on rencontre 3, qui n'est pas barré; mais il ne reste plus dans la table aucun nombre qui soit divisible par 2, le seul nombre premier plus petit que 3 ; donc, en vertu du lemuie, tous les nombres qui subsistent

et qui sont inférieurs à 3 X 3 sont premiers; je barre tous les multiples de 3; c'est à 3 X 3 qu'il faudra commencer, car un multiple inférieur de 3, n'étant pas premier, n'a pu subsister dans la table. Après 3, on rencontre 5, qui n'est pas barré; mais il ne reste plus dans la table de nombre qui soit divisible par 2 ou par 3, les seuls nombres premiers inférieurs à 5; donc, en vertu du lemme, tous les nombres qui subsistent et qui sont inférieurs à 5 X 5 sont premiers ; je barre tous les multiples de 5 ; c'est à 5 X 5 qu'il faudra commencer, puisque les multiples inférieurs, n'étant pas premiers, ont été barrés. Après 5, on rencontre 7, qui n'est pas barré ; mais il ne reste dans la table aucun nombre qui soit divisible par un nombre premier inférieur à 7; donc, en vertu du lemme, tous les nombres qui subsistent et qui sont inférieurs à 7 X 7 sont premiers; je barre tous les multiples de 7; c'est à 7 X 7 qu'il faut commencer. Après 7, on rencontre 11 ; tous les nombres qui subsistent dans la table et qui sont inférieurs à H X 11 sont premiers; si, en continuant de la mémo façon, on vient de barrer les multiples du nombre premier />, et si y' est le premier nombre de la table qui ne soit pas barré, on est sûr que tous les nombres qui subsistent et qui sont inférieurs à /?' X f^' sont premiers; si p' X /?' est supérieur à N, l'opération est terminée. Si l'on avait voulu construire, par exemple, une table des nombres premiers inférieurs à 100, on se serait arrêté après avoir barré les multiples de 7.

Cette construction donne lieu à quelques observations : elle a été appuyée sur un lemme qui est commode, mais non essentiel. Après chaque radiation, il est manifeste que le premier nombre que l'on rencontre dans la table est premier, puisque, n'ayant pas été barré, il n'admet certainement pas de diviseur premier plus petit que lui : par exemple, quand on a supprimé les multiples de 2 et de 3, le premier nombre que l'on rencontre, c'est-à-dire 5, est certainement premier. Quand on veut ensuite barrer les multiples de 5, c'est assurément à 5 X 5 qu'il faudra commencer, car les multiples inférieurs obtenus en multipliant 5 par un nombre a plus petit que 5, et, par suite, divisible par un nombre premier moindre que 5, à savoir n'importe quel diviseur premier de a, ont déjà été barrés ; ce raisonnement se continue indéfiniment. Que les nombres inférieurs à 7 X 7, qui subsistent dans la table quand on a barré les multiples de 5, soient premiers, c'est ce qui résulte de ce que, dans la suite des opérations, on n'aura jamais à les barrer, puisque la radiation des multiples de 7 commencera à 7 X 7, etc.. Ainsi, la seule observation de la façon dont les choses se passent, jointe au théorème du n** 156,

Tannkry. ^

laO LEÇONS D*ABITIUIÈT1QUE.

permet d*obtenir iouies les coachisioiis essentielles. Le lecteur reconnaîtra qu'on peut même se passer aisément de ce théorème.

Au point de vue pratique, pour barrer les multiples d'un nombre, de 5 par exemple, en commençant à Tun de ces multiples, à 25 par exemple, on procède comme il suit : après avoir barré 25, on place successivement la plume sur les nombres suivants 26, 27, 28, ..., barrés ou non, en comptant 1, 2, 3, ... ; on s'arrête quand on compte 5 et i'on barre le nombre sur lequel on s'est arrêté, puis on recommence à compter 1, 2, 3, ... sur les nombres suivants, et, quand on compte 5 de nouveau, on barre encore le nombre sur lequel on est arrêté, etc... Ajoutons que, tout en opérant exactement de la même laçon, on peut, au début, se dispenser d'écrire les nombres pairs, sauf 2 ; ceci, toutefois, aurait besoin d'une justification, que le lecteur trouvera aisément de lui-même, surtout s'il veut bien se reporter au théorème du n*" 160.

La table I, à la fin du volume, donne la liste des nombres premiers moindres que 1000.

Reconnaître si un nombre donné est premier. — Supposons maintenant qu'on veuille reconnaître si le nombre donné n est premier, et que ce nombre ne figure pas dans la table que Ton a à sa disposition. On essaiera successivement comme diviseurs les nombres premiers 2, 3, S, 7 ... dans l'ordre où ils se suivent, jusqu'à ce qu'on ait été amené à essayer, sans que cette division ait réussi, non plus que les précédentes, un nombre premier p qui fournisse un quotient q inférieur ou égal au nombre premier p' qui suit p dans la table ; dès lors on peut affirmer que le nombre n est premier; on a, en efiet,

n<p{q + i)<p'Xp\

et le nombre n, n'étant divisible par aucun nombre premier inférieur kp\ est premier en vertu du lemme.

Par exemple, le nombre 1009 est premier : l'emploi des caractères de divisibilité montre qu'il n'est divisible ni par 3, ni par 5, ni par 11 ; les divisions par 7, 13, 17, 19, 29, 31 ne réussissent pas; la dernière donne pour quotient 32, nombre inférieur au nombre premier 37 qui suit 31. 11 n'est pas utile d'aller plus loin.

Cette méthode suppose qu'on ait une tabl^ de nombres premiers à sa disposition. S'il n'en est pas ainsi, on essaiera comme diviseurs les nombres de la suite naturelle 2, 3, 4, S, ... dans leur ordre, en se dispensant toutefois d'essayer les nombres dont on sait qu'ils ne sont pas premiers, et l'on s'arrêtera quand on aura essayé en vain un

mmuoBS PUMisK. ni

dnmenrp qui fbtiniisse un qttolieiit f moindre que hii ; os aura en

effet alors

et Ton sera certain que le nombre m, n'admettant pas de diTisenr premier moindre quep, est premier.

160. Un nombre premier qui divise un produit de plusieurs facteurs divise au moins Vun d*eux.

En effet, si le nombre premier ne drvise anenn des fiittenrs, il est premier à chacun d'eux (n* 155); 0 est donc premier à leur produit {n« 144).

La démonstration précédente s'appuie sur la théorie du plus grand commun diviseur : comme le théorème que Ton rient d'établir est le fondement essentiel de ce qui va suivre, il ne sera pas inutile d'en donner une démonstration directe, qui ne s*appoie que sur les propositions plus élémentaires du chapitre UL

Considérons d'abord un produit de deux facteurs a, 6, et soit p un nombre premier. Je dis que si p ne divise ni a, ni 6, il ne divise pas ab ; il sufQt de faire la démonstration dans le cas où les nombres a, b sont inférieurs à p. Si Ton désigne, en effet, par a', 6' les restes de la division de a, b par p, les restes de la division par p des produits ab, a'b' sont égaux (n° 126); si le second reste n'est pas nul, le premier ne le sera pas non plus ; si donc on a démontré qae le produit ah ne pouvait être divisible par p quand les nombres s, h sont inférieurs à p, la proposition sera démontrée dans tous les cas

Or, supposons qu'on puisse associer à un nombre a, plus petit que le nombre premier p, un nombre plus petit aussi que p, tel que son produit par a soit divisible par p, et soit 6 le plus petit des nombres pour lesquels cela a lieu; b est plus grand que un, puisque a X 1 = a, étant inférieur à p, ne peut être divisible par p. Soit r le reste de la division de p par 6, et q le quotient ; on aura p^bq+r, et, par conséquent, ap = abq -f ar; la somme abq+ ar est divisible parp; la première partie l'est aussi, puisque aîb est, par hypothèse, un multiple de p ; il faudrait donc que la seconde partie ar fût divisible aussi par p; mais cela est impossible, puisque r est plus petit que 6, et que 6 est, par hypothèse, le plus petit nombre qui, associé à a, donne un produit divisible par p.

Considérons maintenant un produit de trois facteurs a. 6, c, dont aucun u est divisible par le nombre premier p; p» ne divisant ni a ni 6, ne divise pas ab ; ne divisant ni ab ni c, il ne peut diviser leur produit ahc\ du cas de trois facteurs on s'élève successivement au cas de quatre, cinq, six, ... facteurs; la proposition est générale. Cette démonstration est due à Gauss.

161. Tout nombre qui n'est pas premier peut être décomposé en un

m LEÇONS D'ARITHMETIQUE.

produit de facteurs premiers autres que un; la décomposition ne peut se faire que dune seule façon,

1® La décomposition est possible.

Soit A un nombre qui n'est pas premier ; il admet un diviseur premier a autre que 1 et que A (n® 156); soit q le quotient de la division de A par a ; q n'est pas égal èi 1 et Ton a

A = aç.

Si q est premier, la décomposition est faite; si 9 n'est pas premier, il admet un diviseur premier b autre que 1 et que q\ si y' est le quotient de la division de q par 6, q' n'est pas égal èi 1 et Ton a

q = bq\

et par conséquent en remplaçant q par bq' dans aq^

K = abq';

si q' est premier, la décomposition est effectuée; sinon q' admettra un diviseur premier c autre que 1 et que y', et l'on pourra poser

q'=cq'\ d'où

PL = abcq",

Si q'' est premier, la décomposition est terminée ; sinon, on continuera. Les nombres A, y, q\ 9", ... vont en diminuant, puisque chacun d'eux s'obtient en divisant le précédent par un nombre plus grand que 1; il n'y a qu'un nombre limité de nombres inférieurs èi A, il faudra donc que la suite des opérations s'arrête; elle ne peut s'arrêter que lorsqu'on trouve un quotient qui est un nombre premier; cette circonstance se présentera donc. A ce moment, la décomposition sera effectuée et le nombre A sera mis sous la forme d'un produit abc, r de facteurs «, 6, r, ..., r tous premiers et différents de un. Les facteurs peuvent d'ailleurs être différents ou égaux.

2» La décomposition ne peut s'effectuer que d'une seule façon. Soit en effet a'b'c'.,,p' un produit de facteurs a\b\c% ..., p' tous premiers, qui soit égal au produit abc.r. Je dis, en supposant que le facteur 1 ne figure pas parmi les nombres a, ô, c..., r, a\ b% c'y..,, p\ que les deux produits abc.r, a'b'c'...p\ sauf l'ordre des facteurs, sont identiques; en effet, a divise le premier produit; il doit diviser le second, et par conséquent l'un de ses facteurs, et par conséquent être égal à ce facteur. Supposons que a' soit égal à a; en supprimant dans les deux produits égaux les fac-

leurs égaux a et a\ les résultats doivent être encore égaux, et Ton doit avoir

mais le même raisonnement s'applique au facteur b du premier produit qui doit avoir son égal b' dans le second; en supprimant ensuite les deux facteurs égaux b et b\ on voit que le facteur c du premier produit devra avoir son égal c' dans le second, etc.. Ainsi, chaque facteur du premier produit doit avoir son égal dans le second, et comme Tégalité ne saurait subsister après avoir supprimé tous les facteurs d'un produit, s'il en restait quelqu'un dans l'autre, on voit qu'il y a nécessairement autant de facteurs dans un produit que dans l'autre, et qu'on peut ranger ces facteurs de manière que les facteurs qui occupent le même rang dans les deux produits soient identiques.

162. Nous allons maintenant montrer, sur un exemple, comment l'on effectue la décomposition.

Soit à décomposer 360; on essaie la division par les nombres premiers successifs, en s'aidant pour les premiers des caractères de divisibilité. 360 est divisible par 2; le quotient est 180; ce nombre est encore divisible par 2; le quotient est 90; ce nombre est encore divisible par 2; le quotient est 45; ce nombre n'est plus divisible par 2, mais il est divisible par 3; le quotient est 15; ce nombre est divisible encore par 3; le quotient est 5, qui est premier(*).

On adopte, pour indiquer ces résultats, la disposition suivante : en haut, k gauche, on place le nombre à décomposer et Ton tire à droite un trait vertical; en face du nombre, à droite du trait, on écrit le diviseur premier et au-dessous du nombre, le quotient; en face de ce quotient le diviseur premier, et au-dessous du premier quotient le nouveau quotient, etc. ; on continue jusqu'à ce que l'on ait obtenu un quotient qui soit un nombre premier; on a soin de l'écrire à nouveau, k droite du trait vertical, en face de lui-même :

1. Dans chaque opération, le dividende n'est certainement pas divisible par les nombres premiers antres que un et moindres que celui qu'on essaie comme diviseur ; si l'on vient de faire la division par le nombre premier p, si la division a réussi, et si le quotient q est moindre quep*, on peut affirmer (n* 158) que q est premier, puisqu'il ne peut être divisible, non plus que le dividende, par un nombre premier autre quo un et inférieur à p.

lU LEÇONS D^AamiMËnQtJE.

Si on lit les nombres àgancàe, em reoMMitajit, U est clair qme Ton aura 15=3x5, puis

45 = 3xl5 = 3x(3x5) = 3x3x5,

puis

et ainsi de suite^ en sorte que «iMqiie Bonfare, à gaadM; est le produit des «feoiiiiffes de ia coionae de droite situés à la méoie lia«ieiir qw lui on plas bas; ea pariiciilier 96d sera égêï an produit de toits ies nombres de la ooikmioe de droite, ea sorte q«e Vom aara

en employant la notation des exposants.

Quand un nombre est premier, on doit le regarder comme tout décomposé. A proprement parler, ce n'est pas un produit. Même dans ce cas, nous emploierons (abusivement) Fexpression de produit de facteurs premiers. On observera enfin que jMirmi les facteurs premiers d'un nombre, on ne compte pas le nombre 1.

163. Cette façon de représenter un nombre quelconque par un produit de facteurs premiers est très utile dans beaucoup de circonstances : elle facilite diverses opérations et met en évidence diverses propriétés des nombres.

Quand deux nombres B, C sont décomposés en facteurs premiers, on obtient immédiatement leur produit décomposé en facteurs premiers ; il suffit en quelque sorte de juxtaposer les facteurs de C à ceux de B; en d'autres termes, les facteurs du produit BC sont les facteurs qui figurent dans B et dans C, et le nombre de fois que chaque facteur entre dans ce produit est la somme des nombres qui expriment combien de fois le facteur entre dans B et dans C.

Lorsqu'on emploie la notation ^s exposants, on peut dire que chaque facteur premier du produit BC est un facteur premier de Tun ou de l'autre des nombres "B, C et que l'exposant dont il est affecté est la somme des exposanfts avec lesquels il figure dans B et dans C, s'il figure à la fois dans ces deux nombres ; il ne faut pas oublier que les facteurs qui n'ont pas d'exposant doivent être regardés comme affectés de l'exposant 1 .

iPer «eseoqile, le frodwi *ée& éewK oenb^es

B = 2x2x2xâx3xS, C = 2x2xSx7xU

BG = 2x2x2x2x2x3x3x5x5x7xll = 2*x3«x5^x7xll.

164. Pour qu'mm nowibre A décompoêé en faeieun prewuen soit dioùMe par un nombre B déeompoêé en fadeurt première, il faut et U suffit que tous les facteurs premiers qui figurent dans B se retrouvent dans A, chacun d'eux en nombre au moins égal.

V L9L condition est nécessaire ; en eflfet, supposons A divisible par B et soit C le quotient, aussi décomposé en facteurs premiers, on aura

A=BxCL

Le second membre est tout décomposé en bcieors premiers, comme le premier membre; les deux décompositions doivent être identiques. Donc tous les facteurs qui entrent dans B doivent figurer dans A, en nombre au moins égal.

2** La condition est suffisante : en effet, si A contient tous les facteurs de B, en nombre au moins égal, on pourra dans A mettre en avant tous les facteurs de B, en les répétant autant de fois qu*ils figurent dans B ; on voit alors clairement que A est divisible par B, et que le quotient est le produit des autres facteurs. Ainsi, si on a A = 2x2x3x7x7xH et B=: 2x3x7x7, on écrira

A:=r(2x3x7x7)X(2xH);

si Ton emploie la notation des exposants, on peut exprimer le théorème précédent sous la forme que voici :

Pour que le nombre A soit divisible par le nombre B, il faut et il suffit que chaque facteur qui figure dans B figure dans A avec un

exposant égal on supérieur. Le quotient g est égal alors au produit

des facteurs de A qui ne figurent pas dans B, avec leurs exposants^ et des facteurs de A qui figurent aussi dans B, mais avec des exposants moindres, égaux à la différence des exposants qu^ils ont dans A et dans B.

Ainsi, A = 2»X3*X5«X7X19 est divisible par B = 2*x5x7 et Ton a

Le théorème précédent est capital dans la théorie de la divisi-

130 LEÇONS DARITHMÉTIQUE.

bilité et résout en quelque sorte toutes les questions posées dans le précédent chapitre.