SIMPLIFICATION DANS LA RECHERCHE DU PLUS GRAND COMMUN DIVISEUR

98. On peut simplifier la recherche du plus grand commun diviseur de deux nombres, à l'aide des considérations suivantes.

Dans toute division non exacte, le dividende est compris entre deux multiples consécutifs du diviseur. Le multiple inférieur représente le quotient pris par défaut, le multiple supérieur représente le quotient pris par excès. Dans le premier cas, le reste est l'excès du dividende sur le produit du

(*) Deux théorèmes sont réciproques, lorsque la conclusion de l'un est l'hypothèse de l'autre, et inversement.

diviseur par le quolieni : il est additif. Dans le second cas, le reste est l'excès du produit du diviseur par le quolicnl sur le dividende : il esi sous tract if. Le reste souslraciif est évidemment l'excès du diviseur sur le reste additif. Par suite, quand le reste additif est plus grand que la moitié du diviseur, le reste soustractif est plus petit que cette moitié.

99. Cela posé, dans la recherche du plus grand commun diviseur de deux nombres, on a intérêt à rendre chaque reste moindre que la moitié du diviseur correspondant. Cherchons, par exemple, le plus grand commun diviseur des nombres 624 et 216.

La première division donne pour quolieni 2 et pour reste 192 qui surpasse la moitié du diviseur 216; si l'on prend alors le quotient par excès, c'esl-à-dire égal à 3, le reste devient 2i6 — 192 ou i\. On a, dans ce cas,

et cette égalité prouve évidemment (90) que les nombres 624 et 216 d'une part, 216 et 24 d'autre part, admeilent le même plus grand commun diviseur.

On arrive par suite au même plus grand commun diviseur, en divisant 216 par le reste additif 192 ou par le reste soustractif 24. De plus, comme le reste addiiif 192 est ici plus grand que la moitié du diviseur 216, la division de 216 par 192 donne i pour quotient et 216 — 192 ou 24 pour reste. En d'autres termes, la différence entre les deux procédés, c'est que le reste soustraciif sur lequel on opère immédiatement dans la seconde méthode, n'est autre chose que le reste additif fourni par la division suivante quand on applique la première méthode.

J chaque transformation d'un reste additif plus grand que la moitié du diviseur en reste soustractif , correspond donc une division de moins.

THÉORIE DU PLUS GRAND CO.MiMUN DIVISEUR. 07

LIMITE DU NOMBRE DES DIVISIONS A EFFECTUER DANS LA RECHERCHE DU PLUS GRAND COMMUN DIVISEUR DE DEUX NOMBRES.

100. Supposons qu'on ail cherché le plus grand commun diviseur des nombres A el B, en employant la simplificalion que nous venons d'indiquer (99). Admettons qu'il ait fallu 71 divisions pour arriver à ce plus grand commun diviseur, el désignons les restes successivement obtenus par R,, R,, R3, . . . , R„i, 0. L'avant-dernier reste R„i sera en même temps le plus grand commun diviseur des nombres A el B.

Chaque reste devant être inférieur à la moitié du diviseur correspondant (99), chaque diviseur à son tour est supérieur au double du reste correspondant, et l'on a les [n — i) inégalités

En les multipliant membre à men>bre et en supprimant les facteurs communs aux deux membres de l'inégalité résultante, on trouve

Or, le plus grand commun diviseur R„i est au moins égal à l'unité (93) et, par suite, dans le cas le plus défavorable, si l'on a eu n divisions à effectuer, B l'emporte sur 2"-'.

La limite supérieure du nombre des divisions exigées par la recherche du plus grand commun diviseur de deux nombres, ne peut donc surpasser que d'une unité l'exposant de la plus haute puissance de 2 contenue dans le plus petit de ces nombres.

Et, en effet, si B, plus grand que 2"-', est moindre que 2", le nombre des divisions effectuées ne peut dépasser /i; car, si ce nombre était seulement égal à (n-t-i), on aurait, en se reportant aux notations adoptées el d'après ce qui précède,

B>2''.R„, c'esl-à-dire B>2".

(ro/rlaNoielI).