CHAPITRE V NOMBRES PREMIERS

134. Un nombre premier est un nombre qui n'admet pas d'autre diviseur que lui-même et l'unité (1).

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

Le mot «premier » a déjà été introduit au n° 122 (p. 186), dans un sens différent : 4 et 15 sont premiers entre eux, ou 4 est premier avec 15 ; dans ce sens, il est question de deux nombres ; c’est relativement à l'un que l’autre 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 Tne peut diviser 7, et par conséquent ne peut diviser 7 et 15. T n’est pas premier à 14 qu’il divise. En particulier, tout nombre premier absolu est premier relativement à tout nombre plus petit que lui.

135. Tout nombre qui n'est pas premier admel un diviseur premier, autre que 1.

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

136. 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

4. Quelques auteurs ne comptent pas un parmi les nombres premiers.

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 l'une : ou Fe nombre ainsi formé,

est premier, et alors il est plus grand que p; ou il n’est pas premier ; dans ce dernier cas, il admeltrait un diviseur premier, autre que À ; mais ce diviseur ne peut être un des nombres 2, 3,...,p;car. alors, divisant la somme 1.2.3... p +1 et l'une des parties de cette somme, 1.2.3...p, dans laquelle il entre en facteur, il diviserait la seconde partie, qui est 1 ; il est donc plus grand que p; dans les deux cas, il est prouvé qu’il existe un nombre premier plus grand que p.

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

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

Si le nombre A estinférieur au carré du nombre a et S'il nest. divisible par aucun des nombres premiers inférieurs à a, on peul affirmer que le nombre À es premier. re

Supposons, en effet, que tout diviseur premier de À soit au moins égal à a ; il en sera de même de n'importe quel diviseur D de A, car si D n'est pas premier, il admet un diviseur premier moindre que lui, qui doit diviser À et qui est donc au moins égal à a.

Si maintenant A n'est pas premier, soit D un diviseur de À autre que A et soit D’ le quotient de la division de A par D ; D sera différent de 4 et on aura A—DD'; les deux nombres D et D’ étant au & moins égaux à a, leur produit sera au moins égal à 4? qui, par hypothèse, est plus grand que À; la contradiction est manifeste.

138. Formation d'une table de nombres premiers. — Soit à construire une table de nombres premiers inférieurs ou égaux à un nombre donné N. J'écris la suite naturelle

20 Des NN;

des nombres, depuis 2 jusqu’à N. 2 est premier, je barre tous leñ multiples de 2; c'est à 2><2 qu'on commence. Les nombres qui. suivent et qui ne sont pas barrés ne sont pas divisibles par 2. Le

A DIR tot

premier que l’on rencontre est 3 ; le seul nombre premier plus petit que 3 est 2; les nombres de la table qui ne sont pas barrés et qui sont moindres que 3>X<3 sont premiers, d’après le lemme, puisqu'aucun d'eux n’admet de diviseur premier moindre que 3 ; en particulier 3 est premier. Je barre tous les multiples de 3 ; il suffit de commencer à 3><93. Parmi les nombres qui suivent 3, et qui ne sont pas barrés, aucun n’est plus divisible par 2 ou par 3; le premier de ces nombres est5; sauf 2 et 3, il n'y a pas de nombres premiers plus pelits que 5 ; les nombres de la table qui ne sont pas barrés et qui sont plus petits que 5><5 sont premiers, puisqu'ils n'’admettent pas de diviseur premier plus petit que 5; en particulier 5 est premier. Je barre tous les multiples de 5; il suffira de commencer à X<9. On continue ainsi : supposons qu’on vienne de barrer tous les multiples de p ; parmi les nombres qui subsistent et qui suivent p, aucun n’admet un diviseur premier inféricur ou égal à p; soit p' le premier de ces nombres ; les seuls nombres premiers plus petits que p’ sont précisément ces nombres dont on a barré les multiples : les nombres de la table qui ne sont pas barrés et qui sont moindres que p' Xp, le nombre p'en particulier, sont premiers, puisqu'ils n'admettent pas de diviseur premier moindre que p! : si p'? est supérieur à N, l'opération est terminée; sinon, on barrera les multiples de p', en commençant par p'>x<p, etc... Si l'on avait voulu construire, par exemple, une table des nombres premiers jusqu’à 100, on se serait arrêté après avoir barré les multiples de 7.

Au point de vue pratique, pour barrer les multiples d’un nombre, de 5 par exemple, en commençant à l'un 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 et l’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 ES encore le nombre sur lequel on est arrêlé, etc. Ajoutons que, tout en opérant exactement de la même façon, on peut, au début, se dispenser d'écrire les nombres pairs, sauf ? ; ceci, toutelois, aurait besoin d’une jusüfication, que le lec-

. teur trouvera aisément de lui-même, surtout s’il veut bien se repor-

ter au théorème du n° 139 (p. 159).

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

Reconnaître si un nombre donné est premier. — Supposons main-

tenant qu'on veuille reconnaître si le nombre donné n est premier, et que ce nombre ne figure pas dans la table que l'on a à sa disposition. On essaiera successivement comme diviseurs les nombres premiers 9, 8, 5, 7. dans l’ordre où ils se suivent, jusqu à cequon 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 effet, n <p (9 +1) Mc

et Je nombre n, n'étant divisible par aucun nombre prenuer inférieur à p', est premier en vertu du lemme.

. Par exemple, le nombre 1009 est premier: l emploi des a

de divisibilité montre qu'il n’est divisible ni par 3, ni par 5, ni par 11; les divisions par 7, 13, 17, 19, 23, 29, 31 ne réussissent

pas; la dernière donne pour quotient 32, nb biE inférieur au Dome

premier 37 qui suit 31. Il n'est pas alle d'aller plus loin.

Celte méthode suppose qu’on ait une table de nombres premiers à sa disposition. S’il n’en est pas ainsi, on essaiera comme diviseurs les nombres de la suite naturelle %, 3, 4, 5, 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 diviseur p qui fournisse un quotient g moindre que Jui ; on aura en effet alors

n<p (a+) <ps

et l’on sera certain que le nombre n, n’admettant pas de diviseur premier moindre que p, est premier. | :

439. Un nombre premier qui divise un produit de plusieurs facleurs divise au moins l'un d'eux. à En effet, si le nombre premier ne divise aucun des facteurs, il est premier à chacun d’eux (n°134, p. 147) ; il est donc premier à Jeur produit (n° 126, p. 139).

La démonstration précédente s’appuie sur la théorie du plus grand commun diviseur : comme le théorème que l’on vient 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'appuie que sur les propositions Me élémentaires du chapitre nr.

Considérons d'abord un produit de deux facteurs a, b, et soit p-un nombre premier. Je dis que si p ne divise ni a, ni b, il ne divise pas ab;

il suffit de faire la démonstration dans le cas où les nombres a, d sont inférieurs à p. Si l’on désigne, en effet, par a’, b' 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° 109, p. 121); si le second reste n’est pas nul, le premier ne le sera pas non plus; si donc on a démontré que le produit ab ne pouvait être divisible par p quand les nombres a, b 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 b le plus petit des nombres pour lesquels cela a lieu ; b est plus grand que 1, 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 b, etq le quotient; on aura p — bq + r, et, par conséquent, ap — abq + ar; la somme abq + ar est divisible par p; la première partie l'est aussi, puisque ab 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 b, et que best, par hypothèse, le plus petit nombre qui, associé

à a, donne un produit divisible par p.

Considérons maintenant un produit de trois facteurs à, b, c, dont aucun n’est divisible par le nombre premier p; p, ne divisant ni a ni b, ne divise pas ab ; ne divisant ni ab ni ç, il ne peut diviser leur produit abc; 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.

140. Décomposition d'un nombre en un produit de facteurs premiers. — Tout nombre qui n'est pas premier peul élre décomposé en un produit de facteurs premiers autres que 1 ; la décomposition ne peut se faire que d'une seule façon.

Toutes les fois qu’on parle d’un produit de facteurs premiers, 1l est sous-entendu que le nombre 1 ne figure pas parmi ces facteurs. 1° La décomposition est possible.

Soit À un nombre qui n’est pas premier; il admet un diviseur premier a autre que 1 et que A (n° 135, p. 147) ; soit g le quolient de la division de A par a : g n’est pas égal à 1 et l'on a A — ag. Si g est premier, la décomposition est faile ; sig n'est pas premier, il admct un diviseur premier à autre que 1 “ que g; si g' est le quotient de la division de q par b, qg'n’est pas égal à 1 et l’on a g— bg, et par conséquent, en remplaçant q par bg! ae ag, A—=aba!; sig'est premier, la décomposition est effectuée ; sinon g/ admettra un diviseur premier c autre que Î et que g!, et l’on pourra poser g'= cg", d'où A= abcg".Si q” est premier, la décomposition est terminée ; sinon, on continuera.

Les nombres À, q, g'q",.…. 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 à 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; celte circonstance se présentera donc. À ce moment, la. décomposition sera effectuée et le nombre A sera mis sous la forme d’un produit abc. r de facteurs à, b, ce, .…, r tous premiers et différents de 1. 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 pre-

miers, qui soit égal au produit abc ...r. Je dis que les deux produits

abc...r, a! b'c!...p!, sauf l’ordre des facteurs, sont identiqués; 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 facteurs égaux a et a’, les résultats doivent être encore égaux, et l’on doit avoir be...r pl; 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 € 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 l'é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. | |

141. Je vais maintenant montrer, sur un exemple, ne lon effectue la décomposition.

Soit à décomposer 360; on essaie la division par 1e 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 %, mais il est divisible par 3 ; le quotient est 15 ; ce nombre es divisible encore par 8 ; le quotient est 5, qui est premier (®).

4. Dans chaque opération, le dividende n'est cerlainement pas divisible par les nombres premiers autres que 1 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 9 est moindre que p°, on peut

affirmer (n° 137, p. 118) que q est premier, puisqu'il ne peut être DRE non plus que le divi- -dende, par un nombre premier autre que 1 et inférieur à p.

ne

On adopte, pour indiquer ces résultats, la disposition suivante : en haut, à gauche, on place le nombre à décomposer et on 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 qu'on ait obtenu un quotient qui soit un nombre premier; on a soin de l'écrire à nouveau, à droite du trait vertical, en face de lui-même :

Si on lit les nombres à gauche, en remontant, il est clair

que l’on aura 15—3 <5, puis PE SKA (RE) KI XS, 90/2

puis 4513 M2 45% (III IIS, Le

ts)

et ainsi de suite, en sorte que chaque nombre, à gauche, est

le produit des nombres de la colonne de droite situés à la même hauteur que lui ou plus bas ; en particulier 360 sera égal au produit de tous les nombres de la colonne de droite, en sorte que l'on aura

FU TR Er CS tn D QE Ce

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) l'expression de produit de facteurs premiers.

442. 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 des exposants, on peut dire que chaque facteur premier du produit BC est un facteur premier de l’un ou de l’autre des nombres B, C et que l'exposant dont il est

affecté est la somme des exposants 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. .

Par exemple, le produit des deux nombres

B-=9:9.9.3.3.9,:0—72.2.5. 80 est | BC—9.9.9.9:9.3:3.5.5.7.11 22,907 00

143. Application à la divisibilité. — Pour qu'un nombre À décomposé en facteurs premiers soi divisible par un nombre B décomposé en facteurs premiers, 1 faul el il suffit que tous les facteurs . premiers qui figurent dans B se retrouvent dans À, chacun d'eux en

nombre au moins égal. : |

1° La condition est nécessaire ; en effet, supposons À divisible par B et soit C le quotient, aussi décomposé en facteurs premiers, on aura À — B C. Le second membre est tout décomposé en facteurs 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. |

9 La condition est suffisante : en effet, si A contient tous les facteurs de B, en nombre au moins égal, on pourra dans À mettre en avant tous les facteurs de B, en les répétant autant de fois quils 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=—9,9.3.7. 1.11 ét B—2.3.7.1;-0n Cr FE

si l’on emploie la notation des exposants, on peul exprimer le thcorème précédent sous la forme que voici : de | Pour que le nombre A soit divisiblé par le nombre B, il faut etil suffit que chaque facteur qui figure dans B figure dans À avec un exposant égal ou supérieur. Le quobent + est égal alors au produit des facteurs de A qui ne figurent pas dans B, avec leurs exposants, et des facteurs de À qui figurent aussi dans B, mais avec des exposants moindres, égaux à la différence des exposants quils ont dans A et dans B.

Ainsi, A = %.3.5%.7.19 est divisible par B=—2%.5.7etlona À = 3,5. 1,40 —2,9.H 10

à: pl NN Det;

Lys. [2 , \

LAS dde, 2 sale” DS

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

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