LIVRE II

eflectue plus de 5n divisions, B contient plus de n chifrres, ou , autrement , le nombre des divisions effectuées ne peut excéder cinq fois le nombre des chiffres de B.

PROPOSITION XIII

Trouver la plus petite limite du nombre des divisions O faire, pour trouver le plus yrand commun diviseur de deux nombres entiers A et B, parmi celles qui ne diminuent pas, lorsque le plus petit B des nombres proposés augmente.

Considérons la suite des nombres

Chacun de ces nombres , à partir du troisième, étant égal à la somme des deux qui le précèdent immédiatement, si l'on cherche le plus grand commun diviseur de deux termes consécutifs, tels que 34 et 21, on obtiendra successivement pour restes les nombres précédents 13, 8, 5, 3, 2, 1 et le dernier reste 0 ; d’où il résulte que le nombre des divisions effectuées est égal au nombre des termes qui précèdent le plus grand 34 des deux nombres qu’on a pris dans la série.

Pour obtenir la limite précédente (pr.l2), nous avons supposé seulement que les sixième et septième termes de cette série contiennent l’un la base 10 et l’autre le double de cette base, sans tenir aucun compte de l’excès 3 de 13 sur 10 ni de l’excès 1 de 21 sur 10x2 ; il est donc présumable qu’en ayant égard à ces différences nous pourrons trouver une limite plus approchée.

On a vu (pr. 12) que est au moins égal à 2 ou, autre; ment, que lorsqu’on fait deux divisions pour trouver le plus grand commun diviseur des nombres A et B, le plus petit nombre B est au moins égal à 2 ; pareillement , quand on

Aï COMPLÉMENT d’aRITHMÉTIQDE.

fait trois divisions, B est au moins égal à 3; quand on fait quatre divisions , B est au moins égal à 5 , et , en général , quand on fait n divisiçns, B est au moins égal au terme de la série (i). Cela étant, supposons qu’on ait B = 17 : si l’on cherche dans la série C) le premier terme 21>17, le nombre 6 des termes précédents sera une limite du nombre des divisions à faire pour trouver le plus grand commun diviseur de A et 17; car, s’il fallait faire plus de six divisions, B serait au moins égal à 21, ce qui est contraire à l’hypothèse. De plus, aucune autre limite, parmi celles qui ne diminuent pas lorsque B augmente, ne donnera pour maximum du nombre des divisions un nombre inférieur à 6; car, si cela était, cette même limite appliquée au nombre 13<17 donnerait encore un maximum inférieur à 6, et l’on vient de voir qu’en supposant A =21 et B=13 le nombre des divisions à faire était égal à 6. Donc, en général , pour avoir la limite demandée, il suffit d'écrire les termes de la série {K)jusqu'a%i premier terme supérieur à B, et de compter le nombre des termes précédents.

PROPOSITION XIV

Le nombre des divisions à faire, pour trouver le plus grand commun diviseur de deux nombres entiers A et B, ne peut excéder trois fois le nombre des chiffres du plus petit B des nombres proposés, lorsqu'on fait en sorte qu’aucun des restes n excède la moitié du diviseur correspondant.

Chaque fois qu’une division conduirait à un reste plus grand que la moitié du diviseur correspondant, on peut ajouter une unité au quotient et soustraire le dividende du produit du diviseur par le quotient, ce qui conduit à un reste moindre que la moitié du diviseur (pr.9, cor.). En réduisant ainsi deux divisions à une seule, on conçoit qu’on