LIVRE II

puisse trouver des limites moindres que celles qu’on vient d’obtenir. Supposons donc qu’on apporte cette modification à la recherche du plus grand commun diviseur des nombres  et B, et soient, comme précédemment,

tous les nombres qui ont servi de diviseur. Si l’on considère trois diviseurs consécutifs tels que D^, 1)^, le troisième sera le reste de la division du premier par le second; donc, suivant qu’on aura pris le quotient par excès ou par défaut, afin d’obtenir un reste D’ < i I)^, on aura

D, = ou>3D— D. ou D,= Ôu>2I).4-D„.

5 4 5 5 4 tf

Désignant par K l’excès de 1)^ sur 2Dj, on trouve 3 I)^-Dj= 5D3+3K et 2D^+D,=5Dj + 2K, d’où l'on conclut

Donc, quel que soit le mode de division, on aura toujours U = ou>2D^ + D3î

mais D3 est au moins égal à 2, donc D3 est au moins égal à 5; pareillement, est au moins égal à 12, au moins égal à 29, et ainsi de suite ; donc on a

(*) D,>10 et D3>10 x 2.

Or, de môme que les inégalités [(<) pr. 12] ont conduit à

Dü»+i > 10*

les inégalités (*) conduiront , par des raisonnements analogues, à

Dsd+i > 10",

œUPLÉUEMT d'arithmétique.

d’où l’on conclut que le nombre des divisions à faire ne peut excéder trois fois le nombre des chiffres de B.

Remarque t. En admettant ce nouveau mode de division, on peut facilement déduire de la série w 1, 2, 5, 12, 29..., dans laquelle trois termes consécutifs sont tels que le 3“ est égal au double du 2' augmenté du 1", un principe analogue à celui qu’on a déduit de la série 1, 2, 3, 5, 8... (pr. 13). Aussi nous contenterons-nous de l’énoncer : pour avoir ta limite la plus approchée du nombre de divisions à faire , dans la recherche du plus grand commun diviseur de deux nombres entiers A et B, parmi celles qui ne diminuent pas lorsque B augmente, il suffit d’écrire les termes de la série (*) Jusqu'au premier terme supérieur à B, et de compter le nombre des termes précédents.

Remarque 2. Lorsqu’on connaît le plus grand commun diviseur de A et B ou , plus généralement , un facteur D commun à ces deux nombres , on substitue à B , dans le calcul des limites précédentes (pr. 12, 13, 14.), le quotient de la division de B par P, ou seulement au nombre des chiffres de B celui des chiffres de ce quotient, ce qui donne ordinairement des limites plus approchées.

Preuons pour exemple les nombres 2904 et 1122 écrits dans le système décimal , et dont le plus grand commun diviseur s’obtient en effectuant 5 ou 4. divisions selon la manière d’opérer. En désignant par c le nombre des chiffres de B, par l et l ' les limites qu'on déduit des séries (i) et ( 2 ), les limites 5e (pr. 12) et 3e(pr.l4) appliquées à 1122 donnent 5c=20, 3c=12 : les séries (P et (a) donnent les limites plus approchées ^ = 15, î'=9. Mais les nombres 2904 et 1122, étant divisibles par 2, par 3, et par 11, sont divisibles par le produit 2x3x11 =66 (ar. liv. 2,pr.20, cor.l) et , sans effectuer la division de 1122 par 66, on voit que le quotient de cette division contient deux chiffres; ce qui réduit les limites 5c et 3c à 5c=10, 3c=6. Enfin si l’on divise 1122 par 66 et qu’on emploie les séries C> et ( 2 ) en substituant le