PLUS GRAND COMMUN DIVISEUR

si 6 — c est plus petit que c, il sera avantageux de le substituer à c dans la recherche du plus grand commun diviseur; c*esl ce qui arrivera si l'on a 6 < 2 c; ainsi dans l'exemple précédent, au diviseur 12 on pourra substituer le diviseur 16 — 12 = 4, et supprimer une division.

136. Règle. — Pour trouver le plus grand commun diviseur de deux nombres dont aucun n^est nul, on divise le plus grand par le plus petit; si la division se fait exactement, le plus petit est le plus grand commun diviseur cherché; sinon on divise le nombre employé comme diviseur par le reste de la division; puis, le nombre employé comme diviseur dans cette nouvelle division par le reste qu'elle fournit, et ainsi de suite, jusqu'à ce qu'une division réussisse. Le nombre employé alors comme diviseur est le plus grand commun diviseur cherché. Pour simplifier cette recherche, on peut d'ailleurs utiliser les remarques précédentes.

137. Considérons maintenant le cas de plusieurs nombres a^b,c,d,... : puisque les diviseurs communs à deux de ces nombres a, b sont les mêmes que les diviseurs de leur plus grand commun diviseur D, il est clair que les communs diviseurs de a, ^, c, t/,... seront les mêmes que les communs diviseurs de D, c, ^,... ceux-ci sont les mêmes que les diviseurs communs de D', cf..., en désignant par D' le plus grand commun diviseur de D et de c, etc.. ; on finira par n'avoir plus que deux nombres et les diviseurs communs à a, 6, e, rf,... seront évidemment les mêmes que les diviseurs du plus grand commun diviseur de ces nombres-là. Étant donnés autant de nombres que l'on voudra, il existe donc un nombre dont les diviseurs sont les mêmes que les diviseurs communs des nombres donnés; on lui donne le nom de plus grand commun diviseur de ces nombres; on ramène la recherche de ce plus grand commun diviseur au cas de deux nombres, en s'appuyant sur ce qu'on ne change pas les diviseurs communs de plusieurs nombres en substituant à deux de ces nombres leur plus grand commun diviseur. — Il est d'ailleurs évident qu'on pourrait aussi bien remplacer trois, quatre,... de ces nombres par leur plus grand commun diviseur.

Soient, par exemple, les nombres 360, 180, 54, 372. 180 est le plus grand commun diviseur de 360 et de 180, le plus grand commun diviseur des quatre' nombres est le même que le plus grand commun diviseur de 180, 54, 372; le plus grand commun diviseur de 180 et de 54 est 18; celui de 372 et de 18 est 6 : le plus grand commun diviseur des quatre nombres est 6, et les communs diviseurs de 360, 180, 54, 372 sont les mêmes que les diviseurs de 6.

Dans la pratique, quand on a à chercher le plus grand commun

diviseur de plusieurs nombres, il est généralement avantageux de commencer par les plus petits.

138. Quand on multiplie deux ou plusieurs nombres par un même fadeur, leur plus grand commun diviseur est multiplié par ce facteur. On entend par là que le plus grand commun diviseur des- nouveaux nombres est égal au plus grand commun diviseur des anciens nombres multiplié par le facteur par lequel on les a multipliés eux-mêmes.

Dans le cas de deux nombres, cette proposition résulte du procédé exposé pour obtenir le plus grand commun diviseur de deux nombres. Reprenons les notations du n^ 134 : soient a, b les deux nombres proposés, c le reste de la division de a par A, d le reste de la divi» sion de b parc, ..., A le plus grand commun diviseur.

Si Ton multiplie les nombres a eib par un facteur »j, c'est-à-dire si on substitue aux nombres a, b les nombres am, bm,\e reste osera aussi multiplié par wi, c'est-à-dire que cm devra remplacer c; de même le reste de la division de bm par cm sera dm ; tous les restes seront multipliés par m : le plus grand commun diviseur, qui est le dernier de ces restes, sera aussi multiplié par m.

Ainsi le plus grand commun diviseur de 360 et de 172 est 4 : celui de 360 X 5 = 1800 et de 172 X 5 = 860 sera 4 X 5 = 20.

Considérons maintenant le cas de trois nombres a, b, c; soient D le plus grand commun diviseur de a, b et D' le plus grand commun diviseur de D et de c, c'est-à-dire le plus grand commun diviseur de a, ô, c; je dis que le plus grand commun diviseur de am, Am, cm. est D'm ; en effet le plus grand commun diviseur de am et de bm est Dm; le plus grand commun diviseur de Dm et de cm^ ou le plus ^rand commun diviseur de am, bm, cm, est D'm.

Du cas de trois nombres on s'élève successivement au cas de quatre, cinq, ... nombres. La proposition est générale.

139. Quand deux ou plusieurs nombres sont divisibles par un même nombre m il en est de même du plus grand commun diviseur; si on effectue les divisions, le plus grand commun diviseur est lui-même divisé par le nombre m ; c'est-à-dire que le plus grand commun diviseur des nouveaux nombres est égal au plus grand commun diviseur des anciens divisé par m.

On peut démontrer celle proposition de la même façon que la précédente; on peut aussi observer qu'elle en résulte.

Considérons, par exemple, les trois nombres a, b, c divisibles par m; soit D leur plus grand commun diviseur; soient a', b', c' les résultats de la division de a, b, c par m, et soit D' leur plus grand

PLUS GRAND COMMUN i)lVlSEUR. 117

commun diviseur : le plus grand commun diviseur de ma'^ mb\ me' sera, en vertu de la proposition démontrée en premier lieu, égal à mD' ; on aura donc D = wD', en d'autres termes D' est le quotient de la division de D par m.

140. En particulier, si Ton divise les nombres a, b, c,... par leur plus grand commun diviseur D, le plus grand commun diviseur des

quotients a', b\ c',... sera — ou un. Les quotients n'auront pas de

diviseur commun autre que un. Réciproquement si les nombres a', 6',

c\... ont pour plus grand commun diviseur Tunité et si D est un

nombre quelconque, le plus grand commun diviseur des nombres

a'D, ô'D, c'D,..., obtenus en multipliant par D les nombres a', b\ c',...,

sera le produit de un par D, c'est-à-dire D.

Lorsque le plus grand commun diviseur de deux nombres est un,

on dit que ces deux nombres sont premiers entre eux; ainsi 8 et 11

sont premiers entre eux. On peut donc dire : Quand on divise deux

nombres par leur plus grand commun diviseur^ les quotients sont

. .360 ,.^ 172 ,^ premiers entre eux\ ainsi -^ = 90 et — = 43 sont premiers entre

eux; réciproquement quand deux nombres sont premiers entre eux et qu'on les multiplie par un troisième nombre, ce troisième nombre est le plus grand commun diviseur des produits (*).

On dit que plusieurs nombres sont premiers entre eux deux à deux lorsque chacun de ces nombres est premier à chacun des autres. Ainsi 3, 8, Il sont premiers entre eux deux à deux; 10, 12, 7 ne sont pas premiers entre eux deux à deux, quoique le plus grand commun diviseur de ces nombres soit égal à un.

Remarquons en passant que lorsque deux nombres sont premiers entre eux, tout, diviseur de Tun est premier avec tout diviseur de l'autre; car, si ces deux diviseurs étaient multiples d'un même nombre, il en serait de même des deux nombres proposés.

141. Les propositions qui ont été établies au n" i40, bien qu'elles ne soient qu'un cas particulier du théorème du numéro précédent, sont tr^s importantes et il n'est peut-être pas inutile de remarquer que la proposition

1. Ces façons de parler s'étendraient d'elles-mômes au cas de plusieurs nombres, si l'on coDYenaît de dire que plusieurs nombres a, 6, r, ... sont premiers entre eux quand leur plus grand commun diviseur est un. A ce sujet le langage yarie un peu suivant les auteurs : quelques-uns disent, dans ce cas, que les nombres sont premiers entre eux, pris dans leur ensemble ; d^autres n'appellent nombres premiers entre eux que ceux quo nous appelons premiers entre eux deux À deux. Pour éviter toute confusion, quand il s'agira de plusieurs nombres, je dirai : nombres dont le plus grand commun diviseur est l'unité.

directe resuite immédiatement de ce que le plus grand commun diviseur de plusieurs nombres est le plus grand de leurs communs diviseurs.

Si on désigne encore, en effet, les nombresdonnés para,6,c,...,par D leur plus grand commun diviseur, par a', 6', c',... les résultats obtenus en divisant «, 6, c,... par D, je dis que a', h\ c',... ne peuvent avoir d'autre diviseur commun m que Tunité; si Ton avait en effet

a' = a"mf b' = b"m, & = c'^m,..., puisque Ton a

ou aurait

a = a"mD, b = 6"wD, c = &'mD,.,. ;

en sorte que les nombres a, 6, c auraient pour commun diviseur le nombre mD, qui serait plus ^rand que D si m était plus grand que un.

Quant à la réciproque, elle deviendrait évidente de la même façon si l'on admettait que tout diviseur commun à plusieurs nombres a, 6, c,... est un diviseur du plus grand D des communs diviseurs de ces nombi*es. Cette proposition a été démontrée plus haut en s*appuyant sur l'opération même qui fournit le plus gratid commun diviseur, elle le sera autrement un peu plus bas.

142. On ne change pas le plus grand commun diviseur de deux nonibres en multipliant tun d'eux par un facteur premier à Vautre.

Soient en effet a, b les deux nombres; soit m un nombre premier à A : je dis que le plus grand commun diviseur de a et de 6 est le même que le plus grand commun diviseur de ma et de b.

Il faut montrer que les diviseurs communs de a et de é sont les mêmes que les diviseurs communs de ma et de A : les diviseurs communs de a et de 6 sont évidemment des diviseurs communs de ma et de ô; il suffît donc de montrer que les diviseurs communs de ma et de b sont des diviseurs communs de a et de A, c'est-à-dire qu'ils divisent a ; or le plus grand commun diviseur de & et de m est i ; le plus grand commun diviseur de ba et de ma sera donc a ; mais tout nombre qui divise b et ma divise aussi ba et ma\ il divise donc leur plus grand commun diviseur a, ce qu'il fallait démontrer

Inversement, on n'altérera pas le plus grand commun diviseu entre deux nombres a, b en divisant l'un d'eux par un nombre premier à l'autre. On suppose essentiellement que la division se fasse exactement.

Cette proposition est au fond identique à la précédente : dire, en supposant que m soit premier à 6, que le plus grand commun diviseur de a et de A est le même que le plus grand commun diviseur