SUR LA THÉORIE DU PLUS GRAND COMMUN DIVISEUR

I. Nous nous proposons ici d'établir un théorème remarquable dû à M. Lamé, et que cet illustre géomètre a communiqué à lAcndémie des Sciences en 1844. Le théorème dont il s'agit est le suivant :

SUR LA THEORIE DU PLUS GRAND COMMUN DIVISEUR. 3o7

Le nombre des divisions à effectuer, pour tromper le plus grtind commun diviseur de deux entiers, est toujours moindre que ci ne/ fois le nombre des chiffres du plus petit des deux entiers.

II. Considérons la suite indéfinie [a] I, 2, 3, 5, 8, i3, 21, 34, 55, 89, 144, 233,...,

dont les deux premiers termes sont i et 2, et dans laquelle chacun des autres termes s'obtient en ajoutant les deux termes précédents. Nous appellerons groupe l'ensemble des termes de cette suite qui ont un même nombre de chiffres. Ainsi les nombres 1,2, 3, 5, 8, qui n'ont qu'un seul chiffre, formeront le premier groupe ; les nombres i3, 21, 34, 55, 89, formeront le deuxième groupe; et ainsi de suite, de sorte que le groupe de rang A- comprendra ceux des nombres de la suite [a) qui ont k chiffres. Cela posé, nous établirons d'abord la proposition suivante:

Un groupe quelconque de lu suite ( a ) se compose de quatre ou de cinq nombres.

En effet, soient M et N les deux derniers des termes de la suite [a] qui sont inférieurs à lo''""'. Le terme qui vient après N est M -(- N ; ce nombre est supérieur à lo*"', par hypothèse, mais il est moindre que 2N et, à plus forte raison, moindre que 2 x lo*"'; en conséquence, il a /■ chiffres. Les nombres de la suite [a] qui composent le groupe de rang k seront donc les premiers termes de la suite

M-^N, M-+-2N, 2M4-3N, 3M + 5N, 5M + 8N, 8xM^-i3N,...

Le quatrième nombre, savoir : 3M -t- 5N, est inférieur à 8N et, à plus forte raison, inférieur à 8 x io*~' ; donc ce nombre n'a que k chiffres. Le sixième nombre de la suite précédente, savoir :

8M-+-I3N ou Jo(M + N)-+-3N — 2N,

est supérieur àio(M-f-N); il a, en conséquence, plus de k chiffres. Donc la suite [a] contient au moins quatre nombres de /■ chiffres et au plus cinq.

Les trois premiers groupes de la suite [a] ont cinq termes, mais le quatrième groupe n'en a que quatre. Il serait aisé d'établir qu'après un groupe de quatre termes viennent au moins trois groupes de cinq termes el au plus quatre; mais cette proposition ne nous est pas nécessaire, et nous nous bornons à la mentionner.

m. Soient k et ^ deux nombres entiers^ Q le quotient et R le reste de Indivision de A par B. Si A et B tombent l'un et l'autre entre deux termes consécutifs '^ et M -t- N de la suite [a], le reste R ne peut tomber entre N ef M H- N ni même entre M et N.

En effet, on a R = A — BQ ; mais A est inférieur à M -r- N, tandis que

3o8 NOTE III.

13 est supérieur à N; d'ailleurs, Q est au moins égal à i et, par conséquent, R est inférieur à (M -t- N ) — N, c'est-à-dire à M.

Ce résultat subsisterait encore si A était égal à M + N; si l'on avait à la fois A = M H- N, B = N, on aurait évidemment R = M.

IV. Soient A et B deux nombres entiers et R,, R,,. . . , R„, les restes auxquels conduit la recherche de leur plus grand commun diviseur, de sorte que le dernier reste R„ soit ce plus grand commun diviseur. Supposons que le plus petit des nombres donnés B tombe entre les termes cotisécutifsM et N de la suite [a). Soit

cette suite (rt) arrêtée au terme N, et comparons-la à la suite

D'après ce qui précède, il ne peut y avoir plus de deux termes de la suite('i) compris entre deux termes consécutifs de la suite (0< ^t q»^iand il en tombe deux dans un intervalle, il n'y en a point dans l'intervalle précédent; il résulte de là que la suite (i) contient au moins un terme de plus que la suite (2). Mais si /,• désigne le nombre des chiffres de B, N a /ou /i ^- I chitîres; doncle nombre des restes R,, R2,... R„, est inférieur au nombre des termes de la suite [û], qui n'ont pas plus de -^ chiffres. Ce dernier nombre est lui-môme égal ou inféiieur à 5/-, et, par suite, la recherche du plus grand commun diviseur de A et B ne peut pas donner lieu à plus de 5k divisions.

Remarque. — Il est évident que notre conclusion subsiste dans le cas où les nombres donnés A et B sont respectivement égaux à N et M ; la suite (i) comprend alors les mêmes nombres que la suite (2), mais elle renferme un terme de plus que celle-ci.