CHAPITRE XIX. — CODIVISEURS ET COMULTIPLES. SBg

el ainsi de suif e. Donc, en supposant la relation (i)vérinée, lorsque Ton y remplace p par (p — i) et par (/? — 2), on a

si Ton porte ces valeurs de r^^o et de r^i dans régalité qui définit Fp

(»n retrouve la relation (i), en posant

, , \ /p~ fp-i Qp-^ fn-i^

Ainsi la relation (1) est démontrée. On observera que les nombrcs/y, et gp sont tous entiers positifs, et croissent avec l'indice /?, puisque cliaciin d'eux est au moins égal a la somme des deux précédents, attendu que Çp^i- On calcule successivement les nombres/y, ci gpy en partant des valeurs qui correspondent aux indices i et 2; par convention, on pose

et il suffit alors de connaître /« et g^t car la loi de récurrence s'applique encore, ainsi qu'on le constate, à partir de l'indice zéro.

Si l'on applique le théorème précédent au dernier reste r„i qui est le plus grand codiviseur 0 des deux nombres positifs a et 6, on en déduit ce théorème : Le plus grand codiviseur de deux entiers positifs a et b est égala la différence de deux multiples de a et de b. En efifet, on a pour^ = n

Plus particulièrement, si aet b sont positifs et premiers entre

eux, on peut trouver deux entiers positifs x et y, tels que Von

ait

r-. \ — ax — hy,

192. Théorème d'Euclide. — Tout nombre 0 qui divise un produit de deux facteurs ab et qui est premier à Vun d'eux b divise l autre a.

34'A LIVRE III. — LA DIVISIBILITÉ ARITIlMéTlQUE.

Le résultat prcccdent s'applique encore pour m impair, en changeant b en — b, aux deu\ facteurs du produit

a -r- b et ,- •

Exemple l', — Si a'-+-^f* est premier, le plus grand codiviseur de a et fl est i ou une puissance de a.

193. Codiviseurs de plasieurs nombres. — 11 s'agit de déterminer tous les nombres qui divisent à la fois plusieurs nombres donnés a, b^Cfd, D'abord il est évident que l'ordre de succession

des nombres'donnos peut être pris arbitrairement ; et que, par conséquent, a et b désignent deux quelconques des nombres donnés.

Désignons par o le plus grand codiviseur des deux nombres a ei b; nous avons vu que tout nombre qui divise a et 6 divise o, et inversement tout nombre qui divise o divise a et 6. Par suite, tout nombre 0, codiviseur de «, 6, c, </,... , est un codiviseur de 0, c, rf, . . . , et inversement, tout codiviseur de o, c, rf, ... divise les nombres donnés. Par conséquent, la recherche des codiviseurs de n nombres entiers se ramène à la recherche des codiviseurs de (/i — i) nombres, en remplaçant deux quelconques des nombres donnés par leur plus grand codiviseur. En appliquant ce procédé au système nouveau des (n — i) nombres, on pourra remplacer celui-ci par un système de (/i — 2) nombres, et ainsi de suite, jusqu'à ce que le système soit remplacé par un seul nombre. On a donc cette proposition : Les codiviseurs de plusieurs nombres sont tous les diviseurs de leur plus grand codiviseur. Mais il est bon d'observer que l'on excepte le cas où les nombres donnés sont tous nuls.

Dans la pratique, il est plus commode de rechercher le plus grand codiviseur de la manière suivante. On place les nombres donnés par ordre de grandeur croissante

rt, />, r, d. Cy . . • ;

on divise tous ces nombres parle plus petit d'entre eux a. On range encore dans Tordre de grandeur les restes obtenus, en négligeant les restes nuls, et en ne conservant que l'un des restes égaux parmi plusieurs ; on obtient la suite

«1, bu Cl, du —