DU PLUS GRAND COMMUN DIVISEUR

Par suite, en divisant immédialemenl 774 par 36o, on a pour reste 54, qui est le reste de la troisième division.

Ainsi, chaque fois que Ton trouve à appliquer la simplification dont nous parlons, on supprime une division. Voici le tableau du calcul ainsi modifié :

On y rencontre deux fois l'occasion d'opérer la simplification : d'abord, lorsqu'on remplace 4i4 par 36o; puis plus loin, lorsqu'on remplace 36 par 54 — 36 ou par 18. On a ainsi supprimé deux divisions.

On peut remarquer que, si l'on opère de cette manière, chaque diviseur est toujours moindre que la moitié du diviseur précédent. Car il en est toujours ainsi, quand le quotient est au moins égal à 2 ; et dans le cas où le quotient est i seulement, la nouvelle règle substitue au diviseur employé l'excès du diviseur précédent sur celui-ci, nombre plus petit que la moitié du diviseur précédent.

103. Limite du nombre des divisions a faire dans la recherche du plus grand commun diviseur de deux nombres.

Désignons les deux nombres par A et B ; appelons R^, R3, R^. . . .R„. les restes des divisions successives, ou plutôt les nombres qui doivent servir de diviseurs successifs, lorsqu'on applique la méthode simplifiée (102). 11 y a w divisions, et le dernier reste R„ est le plus grand commun diviseur. D'après la remarque qui précède, on a :

B>2R,, R5>2R3, R3>p.R4,....Rh,>2R„.

Si Ton multiplie membre à membre ces diverses inégalités, on a :

ou, en supprimant les facteurs communs aux deux membres,

Or, s'il y a un plus grand commun diviseur, il est au moins égal à 2. Ainsi, dans ce cas, R„ est égal ou supérieur à 2, et l'on a