JOO. RÈGLE DU PLUS GRAND COMMUN DIVISEUR DE DEUX NOMBHES

Ces deux principes conduisent à la règle à suivre pour trouver le plus grand commun diviseur de deux nombres. Soient, par exemple, les deux nombres 8118 et 2772.

Si 2772 divisait exactement 8118, il serait (98) le plus grand commun diviseur cherché. On est donc conduit à essayer cette division. On trouve 2 pour quotient et 2574 pour reste ; 277a n'est donc pas le plus grand commun diviseur.

Mais, d'après le second principe (99), le plus grand commun diviseur entre 8118 et 2772 est le même que celui qui existe entre 2772 et le reste 2574. Si donc 2574 divisait exactement 2772, il serait le plus grand commun diviseur: on est donc conduit à essayer cette nouvelle division. On trouve i pour quotient et 198 pour reste: 2574 n'est donc pas le plus grand commun diviseur. Mais ce nombre est le même que le plus grand commun diviseur entre 2574 et le reste 198, Si donc 198 divise

m PLUS GRArs'D COMMUN DIVISEUR. 71

2574^ il sera le plus grand commun diviseur cherché. C'est ce qui arrive en effet, puisque 2574 est égal à i3 fois 198.

Ce raisonnement est général, et conduit à la règle suivante : Pour trouver le plus grand commun diviseur de deux nombres, on divise le plus grand par le plus petit; s'il y a un reste, on divise le plus petit par ce reste. S'il y a un second reste, on divise le premier reste par le second. S'il y a un troisième reste, on divise le second reste par le troisième. Et l'on continue ainsi à diviser chaque reste par le suivant, jusqu'à ce que l'on rencontre un reste qui divise exactement le reste précédent. Le dernier diviseur employé est le plus grand commun diviseur.

On dispose ordinairement le calcul de la manière suivante :

On écrit toutes les divisions sur une même ligne, et on place le quotient au-dessus du diviseur , afin de réserver la place pour le reste suivant.

dOl. Remarques. 1» Les restes successifs allant toujours en diminuant , on en trouvera nécessairement un qui divisera exactement le reste précédent, comme Texige la règle. Mais ce dernier reste pourra être l'unité. Si cette circonstance se présente, les deux nombres, ayant l'unité pour plus grand commun diviseur, sont premiers entre eux (75).

Réciproquement; si deux nombres sont premiers entre eux . la règle précédente conduira nécessairement à un dernier reste égalai. Car si le dernier reste , divisant exactement le précédent, était différent de i, il serait diviseur commun aux deux nombres, ce qui est contre l'hypoilièse.

2° Si, dans la suite des opérations, on rencontre deux restes consécutifs que Fon sache premiers entre eux, comme leur plus grand commun diviseur est Tunité, il en est de même (100) du plus grand commun diviseur des nombres donnés euxmêmes, et il devient inutile de continuer le calcul.

i2 LIVRE II.— CHAPITRE II.

Exemple : Plus grand commun diviseur entre 567 et 121.

Comme 7 n'a d'autre diviseur que 7, et que 38 n'est divisible que par 2 et par 19, 7 et 38 sont premiers entre eux : il en est de même de 567 et 121.

102. Simplification. Lorsque Tim des restes est plus grand que la moitié du diviseur qui l'a fourni, on peut abréger le calcul, en prenant comme diviseur, dans la division suivante, au lieu du reste obtenu, Texcès du diviseur sur ce reste.

Exemple : Plus grand commun diviseur entre 5832 et 774.

En appliquant la règle générale, on forme le tableau suivant :

et Ton trouve 18 pour plus grand commun diviseur.

Or le premier reste 4i4 est plus grand que la moitié du diviseur 774 qui l'a fourni : l'excès de 774 sur 4i4 est 36o; et il faut prouver qu'on peut substituer 36o à 4i4 comme diviseur de la seconde division. Pour cela, on remarque que 5832 étant égal à 7 fois 774 + 414^ ou à 7 fois 774-I-774 — 36o, on peut

écrire i

Et par conséquent, en vertu du principe 11 (78), tout diviseur commun à 5832 et à 774 est diviseur commun à 774 et à 36o ; et tout diviseur commun à 774 et à 36o est diviseur commun à 5832 et à 774. Les plus grands communs diviseurs entre 5832 et 774, et entre 774 et 36o,soïit donc les mêmes. On peut donc substituer 36o à 4^4 comme diviseur de la seconde division.

Cette modification supprime la seconde division; car puisque l'on a, d'après le tableau ci-dessus :

774=z4i4-j-36o et 414 = 3604-54,

on en conclut 774^=(36oX2)-l-54.