Plus grand commun diviseur entre deux nombres
Un diviseur commun à deux nombres est un nombre qui les divise tous deux exactement. Le plus grand commun diviseur de deux nombres est le plus grand de leurs diviseurs coramiins.
Si deux nombres ont pour plus grand commun diviseur Vanité, ils sont premiers entre eux.
La recherche du plus grand commun diviseur de deux nombres repose sur le théorème suivant :
/.f-Y diviseurs communs à deux nombres sont exactement les jnêmes que ceux qui sont communs au plus petit des deux nombres et au reste de leur division.
Eq effet, si nous désignons par a et b les deux nombres, et par a le plus grand des deux nombres, la division de a par b nous conduit à l'égalité
a = bq-^r, (r<ô),
g et » désignant le quotient et le reste.
Cela posé, tout diviseur commun à a et é, divise aussi bq ; il divise donc la différence a — bqy c'est-à-dire r ; c'est donc un diviseur commun à ô et r. Réciproquement, tout diviseur commun à é et r, divise bq^ et, par suite, la somme ég^-4-r, c'est-à-dire a; c'est donc un diviseur commun h a et b. Les deux couples (a, b) et {b^ r) sont donc complètement équivalents, au point de vue des diviseurs commims.
Considérons alors deuxnombres quelconques, sur lesquels nous ne ferons aucune hypothèse particulière, par exemple, 80712 et 8712. Divisons 80712 par 8712 ; le quotient est 9 et le reste 2304 ; nous pouvons donc, d'après ce qui précède, au point de vue des diviseurs communs, remplacer le couple 80712 et 8712 par le couple plus simple 8712 et 2304. Divisons de même 8712 par 2304 ; nous aurons 3 pour quotient et 1800 pour reste, et nous pourrons remplacer le couple 8712 et 2304 par le couple plus simple 2304 et 1800. Et ainsi de suite.
La suite de ces divisions se termine nécessairement ; car les restes successifs vont en décroissant, de telle sorte qu*on arrive nécessairement soit à un reste nul, c'est-à-dire à une division exacte, soit à un reste égal à 1, étalons comme il divise exactement le précédent, quel qu'il soit, la division suivante se fait exactement. Dans tous les cas, on a donc une suite limitée de divisions terminée par une division exacte.
Dans le cas actuel, il y a 7 divisions en tout, la dernière se faisant exactement ; c'est la division de 216 par 72. Il ressort des raisonnements précédents que les deux nombres donnés, d'une part, le plus petit de ces deux nombres et le premier reste, d'autre part, et deux restes consécutifs quelconques forment des couples équivalents, au point de vue des diviseurs communs. Donc les deux nombres 80712 et 8712 ont les mêmes diviseurs que 216 et 72. Or 216 est un multiple de 72 ; donc les diviseurs de 72 appartiennent tous à 216 ; par conséquent les diviseurs communs à 216 et à 72 sont les diviseurs de 72 ; le plus grand d'entre eux est 72 ; donc 72 est le plus grand commun diviseur entre 80712 et 8712.
De tout ce qui vient d'être dit, résultent la règle et le théorème suivants :
Bà6LB« — Peur trouver le plus grand commun diviseur de
deux nombres donnés, on divise le plus grand par le plus petite celui-ci par le premier reste ainsi obtenu^ puis le premier reste par le second ; et ainsi de suite^ jusqu'à ce que ton arrive à une division exacte. Le dernier reste obtenu est le plus grand commun diviseur cherché.
Théorème. — Les diviseurs communs à deux nombres sont les diviseurs du plus grand commun diviseur.
Les mêmes conclusions 8*appliquent à chacun des couples formés par le plus petit nombre et le premier reste ou par deux restes consécutifs.
Si nous désignons par a et 6 les deux nombres donnés, a > 6, par r^, r,, ..., r* les restes successifs, les diverses divisions signalées donnent naissance aux égalités suivantes :
a = bq^+r^ (r, < 6)
La suite, a, *, r^^ r^, ..., r^^ est décroissante. Tous les couples (a, *), (*, r,) ,..., {r|,^^,rj^) ont les mômes diviseurs communs ; r» est le plus grand commun diviseur de chacun d'eux, et les diviseurs communs à tous ces couples sont les diviseurs de rj^.
Les égalités (1) constituent Talgorithme du plus grand commun diviseur. — On appelle algorithme une opération composée ou un ensemble d*opérations simples conduisant à un résultat déterminé.
Pour effectuer les opérations qui conduisent au plus grand commun diviseur, on réunit toutes les divisions en une seule opération complexe; pour cela, on écrit, à chaque fois, le quotient à la place du diviseur et réciproquement,
de telle sorte que les divisions soient placées les unes à la suite des autres, sans interruption. Nous donnons ici les opérations qui conduisent au plus grand commun diviseur de 80712 et 8712 et au plus grand commun diviseur de 81833 et 9125.
Reharoue I. — Les diviseurs commuas h a et b sont les mêmes que ceux qui sont communs à a et a + A, «et a — b, b et a -+-6, 6 et a — b. On peut donc, dans le couple Vp, rp.i, remplacer le reste rp par son complément à rp i, c'est-à-dire par le nombre rp i — rp. Ceci est avantageux quand le nouveau nombre est inférieur à Vp, ce qui arrive toutes les fois que le reste rp est plus grand que la moitié de rp^i (nous appelons moitié d'un nombre le quotient par 2 de ce nombre à une unité près).
Si le dernier reste r» est égal à 1, les deux nombres a et b n'ont pas de diviseur commun : ils sont donc premiers entre eux, et l'on voit que l'algorithme du plus grand commun diviseur permet de savoir si deux nombres sont ou ne sont pas premiers entre eux.
Reharoue II. — Limite supérieure du nombre iet divisions à effectuer dans la recherche du plus grand commun diviseur . — Il n'y a qu'à consulter la suite des égalités (1), pour voir qu'à chacun des nombres de l'ensemble
correspond une division, si l'on compte toutefois la dernière division qui se fait exactement. Parcourons cette suite en ordre inverse, nous obtiendrons
AlUTHH. HDMB.
remarquons en outre qu'entre trois nombres consécutifs nous avons la relation
dans laquelle qp est au moins égal à 1 ; nous en conclurons de suite
rp^> rp^i -h rp.
D'autre part, le premier reste rk est au moins égal à i, le second rk-t au moins égal à 2 ; si donc nous formons une suite qui commence par les nombres i et 2, et dont chaque terme soit la somme des deux précédents,
les nombres de cette suite ne seront pas supérieurs à ceux qui leur correspondent dans l'ensemble
''Aï ^ik-i, , n, b.
Il en résulte donc que si l'on parcourt la suite des nombres ainsi obtenus jusqu'à ce que l'on arrive à un terme supérieur à 6, on n'aura pas moins rencontré de nombres
qu'il y en a dans l'ensemble r^^ r^^i, , b. Le rang
du dernier nombre envisagé est donc au moins égal au nombre des divisions à efifectuer, et constitue une limite supérieure du nombre des opérations.
Si on cherche le plus grand commun diviseur entre deux termes consécutifs de cette suite, on ajuste autant de divisions à effectuer qu'il y en a d'indiquées.
Nous donnons ici cette suite pour tous les nombres qu'elle renferme et qui sont inférieurs à 10.000 :
Si donc le plus petit des deux nombres employés est inférieur à 10000, il y a au plus 19 opérations à effectuer.
Deux nombres consécutifs de cette suite sont premiers entre eux.
On peut trouver autrement une limite supérieure du
nombre des opérations : il suffit de remarquer que, d'après
la loi de formation des nombres indiquée antérieurement,
les termes de rangs impairs sont supérieurs aux diverses
puissances de 2,
car chacun d'eux est la somme du nombre antéprécédent dans la suite complète et d'un nombre plus grand que lui ; il dépasse donc le double de celui qui le précède dans les rangs impairs. Nous chercherons alors un nombre n tel que 2">6, et le nombre 2n ou même 2n — 1 est une limite supérieure du nombre des divisions. Mais cette limite est en général plus élevée que la précédente : si nous prenons pour exemple le cas où le plus petit nombre est é^al à 6500, la première règle donne 19, ou même 18, pour nombre maximum des opérations, tandis que la seconde règle donne 27.
