DEUXIEME PARTIE.

1 70

soit entier, il suffit que soit entier, c’est-à-dire que q 1 di-vise qq : ' ; mais si q' divise qq", il divise q", en vertu des deuxthéorèmes rappelés plus haut; donc q" ne peut pas être plus

petit que q 1 ; donc le p . p . c . m. de a et 6 est dqq 1 ou d • ^ ^ »

„ ab

ou enfin —> c. q.d ^

d.

N. B. — Cette démonstration ne doit pas être préférée à cellequi résulte de la décomposition des nombres en facteurs pre-miers ; mais elle est analytique et voilà pourquoi nous la don-nons comme exercice.

V

Sur le nombre des restes qu’on peut obtenir dans la re-cherche du p. g. c. d. de deux nombres a et b par la méthodedes divisions successives.

Supposons a > b, et soit n le nombre des restes obtenus enprenant les quotients par excès, quand il le faut pour quechaque reste soit plus petit que la moitié du reste précédent.

Soient d’ailleurs t\, r„ r 3 ,..., r n les n restes ainsi obtenus ;nous avons les inégalités successives

2r, < h, 2r s < i\, 2r 3 < r v

2i» < r„_, ;

et si nous les multiplions membre à membre, nous avonsaprès réduction

2* . r n < b,

d’où

log b —-log r n

n < -

log 2

Maintenant, si nous remplaçons dans l’inégalité (i) r» parsa valeur minimum i, et log 2 par o, 3 , quantité plus petite,

nous aurons a fortiori: n < ou bien

o.ô

10

n < -y m,

m désignant le nombre des chiffres de b : donc le nombre des