II. APPLICATIONS

129. Problème i. Former une table des nombres premiers. La série des nombres premiers étant illimitée (H7), la table

qu'il s'agit de former doit renfermer seulement tous les nombres premiers inférieurs à une limite donnée.

Proposons-nous, par exemple, de former la table des nombres premiers inférieurs à 1000. On écrit, à la suite les uns des autres, tous les nombres entiers jusqu'à 1000 :

l, 2, 3, 4, 5, ê, 7, 8, 9,10, 11,^2, 13, M, fô,^@, 17, ^8, 19,20,

r, 22, 23, 2i, 2S, 2%, 27, 28, 29, 30, 31, 32, 33, 34, 3â, 3ê, 37, 38, 39, 40, l, 42, 43, ii, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 1, 62, 63, 64, 65, m, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80.

et Ton efface successivement tous ceux qui ne sont pas premiers.

Pour cela, on efface tous les nombres de deux en deux, à partir de 2, c'est-à-dire 4, 6j S, ... 998, 1000; car ce sont tous les multiples de 2.

On efface ensuite tous les nombres de trois en trois, à partir de 3^ c'est-à-dire 6, 9, 12, ... 999; car ce sont les divers multiples de 3.

Comme 4 est multiple de 2, les multiples de 4 ont été effacés comme multiples de 2. On efface donc les nombres de cinq en cinq, à partir de 5^ c'est-à-dire 10, i5, 20, ... 995, 1000 ; car ce sont les divers multiples de 5.

Comme 6 est multiple de 2 et de 3, il est effacé ainsi que ses multiples; mais 7 est un nombre premier. On efface tous les nombres de sept en sept, à partir de 7, c'est-à-dire 14, 21, 28,.,. 994 ; car ce sont les divers multiples de 7.

Et Ton continue ainsi, jusqu'à ce que Ton reconnaisse que tous les nombres non premiers sont effacés.

C'est ainsi que l'on a formé la table suivante :

I, 2, 3, 5, 7, II, i3, 17, 19, 23, 29, 3i, 37, 41, 43, 47, 53, 59, 61, 6y, 71, 73, 79, 83, 89, 97.

loi, io3, 107, 109, ii3, 127, i3i, 137, iSg, 149, i5i, 167, i63, 167, 173, 179, 181, 191, 193, 197, 199.

307, 3ii, 3i3, 317, 33i, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397.

809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 8yy, 88i,

130. Remarques, i*' La méthode précédente porte le nom de crible à'Éraiosthène. L'opération même fournit, à mesure qu'elle se poursuit, les nombres premiers dont on doit effacer

les multiples. Ainsi, lorsqu'on a effacé tous les multiples de 7, le plus petit nombre non effacé que Fou rencontre après 7 est II ; dès lors 11 est un nombre premier, car il n'est multiple d'aucun nombre inférieur.

2° Lorsqu'on est amené par la méthode à effacer les multiples d'un nombre })remier, ceux de 11 par exemple, le plus petit de ces multiples qui ne soit pas encore effacé est le carré de ce nombre premier. Car les multiples de 11, inférieurs à 11 fois II, c'est-à-dire 2 fois 11, 3 fois 11, etc., sont en même temps des multiples de 2, de 3, etc, et ont été effacés comme tels. Il en résulte que la table est achevée, lorsque l'on est conduit à effacer les multiples d'un nombre premier dont le carré est supérieur à la limite que l'on s'est imposée. Par exemple, si la limite supérieure est 1000, comme 31^=961, etque 37^= i369, on doit s'arrêter, après avoir supprimé les multiples de 3i. Les nombres qui restent alors sont tous premiers.

131. Problème ii. Décomposer un nombre en ses facteurs premiers. Soit le nombre 2820. On reconnaît (83) que ce nombre est divisible par 2, et l'on trouve que 2820:=2Xi4i^« On reconnaît que le quotient 14 10 est aussi divisible par 2, et l'on trouve i4io:=2 X 7o5 : par suite (i8)

Le quotient n'est pas divisible par 2, mais il est divisible (88) par 3 ; et l'on trouve 705 = 3 X 235 : par suite

Le nouveau quotient 235 n'est pas divisible par 3 ; on passe donc au nombre premier suivant, et l'on reconnaît (83) que 235 est divisible par 5. On trouve 235 = 5x47;» de sorte que :

Et comme 47 est un nombre premier, l'opération est achevée, et l'on a

On conclut de là la règle générale suivante : On divise successivement le nombre donné par les nombres premiers 2, 3, 5, 7 , et Ion s'arrête lorsque l'on a trouvé un diviseur exact : ce diviseur est le plus petit facteur premier du

90 LIVRE II. — CHAPITRE lïl.

nombre. On divise h quotient obtenu par- ce facteur, puis le nouveau quotient par le même nombre, jusqu'à ce que la division ne réussisse plus. On opère ensuite sur le dernier quotient exact, comme on a opéré sur le nombre donné, et l'on continue ainsi, jusqu'à ce qu'on obtienne un quotient premier. Les diviseurs des divisions exactes et le quotient premier sont les facteurs premiers du nombre.

d32. Remarques, l*" Lorsqu'on applique la règle précédente, on rencontre des quotients exacts qui vont toujours en diminuant; on en trouvera donc un qui sera premier. D'ailleurs les diviseurs que l'on essaie successivement vont toujours en augmentant; par conséquent;, si ces essais ne réussissent pas, on rencontrera nécessairement un diviseur qui fournira un quotient inexact, plus petit que lui. Lorsque cette dernière circonstance se présente, on doit s'arrêter; le quotient que Ton essaie de diviser est premier. Pour le prouver, reprenons Texemple précédent. Après avoir divisé 235 par 5, on a trouvé pour quotient 47- Or 47 n'est plus divisible par 5; d'ailleurs, divisé par 7, il fournit un quotient inexact plus petit que 7 : dès lors 47 est premier. En effet, si 47 admettait un diviseur plus grand que 7, par exemple 1 1, il en admettrait un second qui serait le quotient de 47 par 11. Mais ce quotient serait plus petit que le premier quotient, puisque le diviseur nouveau 11 est plus grand que 7 : par suite, 47 admettrait un diviseur plus petit que 7 ; ce qui est impossible.

L'opération conduit donc d'elle-même au dernier facteur premier du nombre donné : et Von doit s'arrêter, lorsque Von est amené à essayer comme diviseur un nombre premier qui fournit un quotient plus petit que lui.

2*^ Lorsqu'on veut reconnaître si un nombre est premier, on essaie de le diviser parles nombres entiers 2, 3, 4» •••jusqu'à ce qu'on arrive à un diviseur qui fournit un quotient plus petit que lui.

433. Problême III. Diviser un nombre par un autre, quand la division doit se faire exactement.

Soient le dividende (2*x3^X7Xïi^) et le diviseur (2X3^X7), préalablement décomposés en leurs facteurs premiers. Puisque

le reste est nul, le dividende contient tous les facteurs premiers du diviseur (126), et on peut récrire en groupant les facteurs

2*X3'X7Xii'=:(2X3'X7)X(2'X3xii').

Sous cette forme, on voit que le quotient est (2'x3xii').

RÈGLE. On décompose le dividende et le diviseur en leurs fadeurs premiers; on prend chacun des facteurs premiers qui se trouve au dividende avec un exposant plus fort qu'au diviseur, et on Vaffecte dun exposant égal à la différence des exposants. Le produit des facteurs ainsi obtenus est le quotient cherché.

134. Problème iv. Former la table des diviseurs d'un nombre donné.

Soit le nombre 2160. On le décompose en ses facteurs premiers, et l'on trouve

Puis on écrit, sur une première ligne, l'unité et les puissances successives du premier facteur 2 jusqu'à celle qui entre dans le nombre; on écrit, sur une seconde ligne, Vunité et les puissances du second facteur 3 jusqu'à celle qui entre dans le nombre ; puis, sur une troisième ligne, Vunité et le troisième facteur 5, et ainsi de suite. On forme ainsi le tableau suivant :

On multiplie chacun des termes de la première ligne par chacun des termes de la seconde, puis chacun des produits ainsi obtenus par chacun des termes de la troisième, et ainsi de suite: 12 2^ 2' 2*

Ce tableau est le tableau des diviseurs du nombre.

92 LIVRE ir.- -CHAPITRE III.

En effets chacun des nombres du tableau [2] est le produit d'un des termes de la première ligne par un des termes de la seconde et par un des termes de la troisième, pris dans le tableau [i]; il ne contient donc que les facteurs premiers du nombre, affectés d'exposanis égaux ou inférieurs à ceux dont ils sont affectés dans le nombre : il est donc un diviseur du nombre (127).

D'autre part^ tout diviseur du nombre se trouve dans ce tableau; car, quelque soit celui que Ton désigne, il résultera nécessairement de la multiplication d'un des nombres pris dans la première ligne du tableau [i] par un des nombres pris dans la seconde et par un des nombres pris dans la troisième. Aucun diviseur n'a donc pu être oublié.

Enfin, aucun diviseur n'a pu être formé deux fois; car, dans une même ligne horizontale, les nombres du tableau [2] diffèrent par le premier facteur; et, d'une ligne àTautre, ils diffèrent par l'un des deux derniers.

Il est donc prouvé que le tableau [2] renferme tous les diviseurs du nombre et ne les renferme qu'une fois chacun.

Remarque. On pourrait aussi obtenir ce tableau, sans décomposer le nombre en ses facteurs premiers. Il suffirait de diviser le nombre par les nombres entiers i, 2, 3, 4^ etc., et d'écrire en regard les diviseurs et les quotients des divisions qui réussiraient. On aurait ainsi :

435. Problème v. Trouver le nombre des diviseurs d*un nombre entier.

Cherchons, par exemple, le nombre des diviseurs de 2160. Dans le tableau [i] du numéro précédent, chaque ligne renferme autant de termes, plus un, qu'il y a d'unités dans l'exposant de la puissance du facteur premier correspondant. Par conséquent, lorsque l'on multiplie chaque terme de la première ligne par chaque terme de la seconde, on forme autant de

produits qu'il y a d'unités dans (4-f-i)X(3-hi); et lorsqu'on multiplie chacun de ces produits par chaque terme do la troisième ligne^ on forme un nombre de produits égal à :

(4-hi)x(3+i)x(n-i).

Ce raisonnement est général, et montre que : Pour former le nombre des diviseurs d'un nombre entier, on le décompose en facteurs premiers; on augmente d'une unité chacun des exposants, et l'on fait le produit des sommes ainsi obtenues. Le produit est le nombre cherché.

Remarque. Si le nombre donné est un carré, tous les exposants sont pairs; augmentés d'une unité, ils deviennent impairs. Dans tout autre cas, un des exposants au moins est impair; augmenté d'une unité, il devient pair; et, par suite, le produit est pair. Donc le nombre des diviseurs d'un nombre donné estpair, à moins que le nombre ne soit un carré parfait.

136. Problême vi. Trouver la somme des diviseurs d'un nombre entier. Considérons encore le nombre 2160. La somme de ses diviseurs esi la

somme des termes du tableau [2] du no i34, c'est-à-dire la somme des pro •

duils qu'on obtient en multipliant successivement l'une par l'autre les trois

sommes (i -1-2 +2^+23-1-2*), (i -j- 3-}- 3^-1- 3'), (i-f-5), qui composent

le tableau [i]. Or, chacune de ces sommes est la somme des termes d'une

progression par quotient; et l'on démontre, en algèbre, le procédé pour

la former. La première est ésale à , la seconde à -n > et la der-

hière à • Donc la somme demandée est égale à

137. Problème vit. Former le plus grand commun diviseur de plusieurs nombres entiers.

Soient les nombres (2^x3*x5X7)^ (2^X3^x5^X11), (2''X3*x5'Xi3), préalablement décomposés en leurs facteurs premiers. Un diviseur commun à cesnombresnepeut contenir que les facteurs qui sont communs à tous, c'est-à-dire, 2, 3, 5. De plus, il ne peut pas contenir plus de 2 facteurs 2, puisqu'il doit diviser le second nombre (127); il ne peut, par une raison analogue, contenir plus de 2 facteurs 3, ni plus d'un facteur 5,

94 LIVRE 11. — CHAPITRE Hl.

Si donc le produit (2^x3^x5), qui contient tous ces facteurs, est un diviseur commun^ il est le plus grand commun diviseur. Or, cette condition est évidemment remplie. On peut donc conclure la règle suivante :

Pour former le plus grand commun diviseur de plusieurs nombres, on les décompose en leurs facteurs premiers; on choisit chacun des facteurs premiers communs à tous les nombres, et on Vaffecte de son plus petit exposant; le produit des nombres ainsi obtenus est le plus grand commun diviseur cherché.

Remarque. Un diviseur commun aux divers nombres ne peut renfermer qu'une partie des facteurs premiers du plus grand commun diviseur. Il en résulte que tout diviseur commun à plusieurs nombres divise leur plus grand commun diviseur. . Si Von divise les nombres donnés par leur plus grand commun diviseur, les quotients

n'ayant plus de diviseurs communs, sont premiers entre eux.

i38. Problème viîi. Former le plus petit multiple commun à plusieurs nombres.

On nomme plus petit multiple commun à plusieurs nombres le plus petit nombre qui soit exactement divisible par chacun d'eux.

Soient les nombres (2^ x3x^'), (2^x5X7^), (2X3'X7), (3-x5-X7'^), préalablement décomposés en leurs facteurs premiers. Un nombre divisible par chacun de ces nombres doit contenir tous leurs facteurs premiers (126), c'est-à-dire, 2, 3, 5, 7. De plus, il ne peut pas contenir moins de 3 facteurs 2, puisqu'il doit être divisible par le second nombre. Par une raison analogue, il ne doit pas contenir moins de 2 facteurs 3, ni moins de 2 facteurs 5, ni moins de 3 facteurs 7. Si donc le produit (2^x3^x5^X7^)? qni ne renferme que ces facteurs, est un multiple commun, il est le plus petit miilti[)le commun. Or cette condition est évidemment remplie. On peut donc con^ dure la règle suivante ;

Pour former le plus petit multiple commun à plusieurs nombres entiers, on les décompose en leurs facteurs premiers ; on

prend une fois chacun des facteurs communs ou non communs, et on Vaffecle de son plus grand exposant. Le produit des nombres ainsi obtenus est le plus petit multiple commun cherché. 139. Remarque. Un multiple commun quelconque aux divers nombnes doit renfermer tous les facteurs premiers du plus petit multiple (126); mais il peut en renfermer d'autres. Il est donc le produit du plus petit multiple par un nombre entier; ou, en d'autres termes, tout multiple commun à plusieurs nombres est multiple de leur plus petit multiple commun.