THÉORIE DU PLUS GRAND COMMUN DIVISEUR

Pins grand commun diyisenr de denx nombres.

109. Deux nombres peuvent admellre un diviseur commun ; ils peuvent en admettre plusieurs : le plus grand de tous ces diviseurs s'appelle \eur plus grand commun diviseur. Ainsi 36 et 24 ont pour diviseurs communs 2, 3> 4i ^ ^^ 12 • ^^ ^st leur plus grand commun diviseur.

110. I. Le plus grand commun diviseur de deux nombres divisibles l'un par l* autre est le plus petit d'entre eux.

Si 36 divise exactement 180, il est le plus grand commun diviseur de 36 et de 180; car le plus grand nombre qui puisse diviser 36 est 36.

On sera donc conduit, pour chercher le plus grand commun diviseur de deux nombres, à essayer leur division. Si la divir sien réussit, la recherche du plus grand commun diviseur est terminée; sinon on s'appuie pour la continuer sur le théorème suivant,

111. IL Le plus grand commun diviseur de deux nombres est le même que celui du plus petit d'entre eux et du reste de leur division.

Soit à chercher le plus grand commun diviseur des nombres 672 et 276. En effectuant leur division, on trouve a pour quotient et 120 pour reste. On remarque alors que tous les diviseurs communs à 672 et à 276 divisent 120, reste de leur division (91), c'est-à-dire sont diviseurs communs de 276 et de 120»

On remarque ensuite que 672 = 276 X 2 -h 120 et que, par conséquent, tous les diviseurs communs à 276 et à 120, divisant 276 X 2, divisent aussi la somme 276 x 2 h- 120 ou 672, c'esi-à-dire sont diviseurs communs de 672 et de 276.

On en conclut que les deux groupes 672 et 276 d'une part, 276 et 120 de l'autre, admettant la même série de diviseurs communs, ont en particulier le même plus grand commun diviseur.

112. Reprenons l'exemple proposé. On est conduit à diviser 276 par 120 : on trouve 2 pour quotient et 36 pour reste. La recherche est donc ramenée à celle du plus grand commun diviseur des nombres 120 et 36. On divise 120 par 36, on trouve 3 pour quotient et 12 pour reste. Enfin on cherche le plus grand commun diviseur des nombres 36 et 12. En divisant 36 par 12, on trouve 3 pour quotient et o pour reste : 12 est donc le plus grand commun diviseur demandé.

On remarquera que les quotients successifs doivent être écrits au-dessus des diviseurs correspondants.

On voit q\x*il faut diviser le plus grand nombre par le plus petit, le plus petit par le reste trouvé, ce premier reste par le second, et ainsi de suite, jusqu'à ce qu'on trouve un reste qui, divisant exactement le reste précédent, soit le plus grand commun diviseur cherché.

113. L'opération se terminera nécessairement; car, puisqu'il s'agit de nombres entiers et que tout reste doit être plus petit que le diviseur correspondant, les restes iront toujours en diminuant; il faudra donc qu'on arrive au moins au reste i qui divise tous les nombres.

Lorsque deux nombres ont pour plus grand commun diviseur l'unité, on dit qu'ils soni premiers entre eux.

Si, dans la recherche du plus grand commun diviseur de deux nombres, on arrive à deux restes qu'on sache être premiers entre eux, le plus grand commun diviseur des deux nombres proposés est aussi i, puisque ce plus grand commun diviseur est celui de deux restes consécutifs quelconques(112).

Théorèmes relatifs au plus grand commiin diviseur

de deux nombres.

114. I. Tout commun diviseur de deux nombres divise leur plus grand commun diviseur.

En effet, lout commun diviseur de deux nombres divise le reste de leur division.

Reportons-nous à l'exemple précédent (112), et considérons 4 qui divise 672 ei 276. II divisera alors 120; divisant 276 et 120, il divisera 36; divisant 120 et 36, il divisera 12.

On voit par là que» pour obtenir tous les diviseurs communs de deux nombres, il suffit de trouver tous les diviseurs de leur plus grand commun diviseur.

115. IL En multipliant ou en divisant deux nombres par un troisième nombre, on multiplie ou Von divise leur plus grand commun diviseur par ce troisième nombre.

En effet, en multipliant ou en divisant deux nombres par un troisième nombre, on multiplie ou Ton divise le reste de leur division par ce troisième nombre (68, 91).

Reprenons encore l'exemple du n"112. En multipliant ou en divisant 672 et 27G par 3, on multipliera ou Ton divisera le reste 120 par 3. Le dividende 276 et le diviseur 120 étant multipliés ou divisés par 3, le reste 36 sera lui-même multiplié ou divisé par 3. Entin, le dividende 120 et le diviseur 36 étant multipliés ou divisés par 3, le reste 12 sera lui-même multiplié ou divisé par 3. Le dividende 36 et le diviseur 12 donnaient o pour reste : il en sera de même de ces deux nombres multipliés ou divisés par 3, c'est-à-dire que le plus grand commun diviseur sera 12 multiplié ou divisé par 3.

116. Ce qui précède permet de simplifler dans certains cas la recherche du plus grand commun diviseur de deux nom* bres. Si l'on demande, par exemple, le plus grand commun diviseur des nombres 368oo et 24000, on pourra diviser ces deux nombres par 100 et chercher le plus grand commun diviseur 16 des quotients 368 et 240. Pour avoir ensuite le plus grand commun diviseur des nombres proposés, il suffira de

j multiplier 16 par loo.

117. IIL Les quotients de deux nombres divisés par leur plus grand commun diviseur sont premiers entre eux.

En efTct, en divisant deux nombres par leur plus grand commun diviseur, on divise ce plus grand commun diviseur par lui-même (115), de sorte que le plus grand commun diviseur des deux quoiienis obtenus «si l'unité.

La réciproque (*) de ce théorème est évidente.

Soient, en effet, les nombres A et B qui, divisés par D, donnent les quotients a ei b premiers entre eux. û et 6 a^anl 1 pour plus grand commun diviseur, les produits rt 13 el 6D, c'est-à-dire A et B, auront i X D ou D pour plus grand commun diviseur (115).

118. £n Arithmétique, Tutilité de la théorie que nous venons d'exposer est bornée à la recherche des quotients de deux nombres par leur plus grand commun diviseur. Il est donc bon d'indiquer une règle pour trouver rapidement ces quotients, au moyen de l'opération même qui fournit le plus grand commun diviseur.

Reprenons encore l'exemple du n**112. 12 se contient luimême I fois : écrivons i au-dessous de 12. 36 contient 3 fois 12 : écrivons 3 au-dessous de 36. 120 contient 3 fois 36 + 12, c'està-dire un nombre de fois 12 représenté par 3x 3 -h i ou 10 : écrivons 10 au-dessous de 120. On voit qu'il faut, pour obtenir ce résultat, multiplier le résultat précédent 3 par le quotient qui est placé au-dessus, et ajouter à ce produit le nombre i placé à droite de 3. 276 contient 2 fois 120 plus 36, c'esi-à-diro un nombre de fois 12 représenté par 10 x 2 -+- 3 ou 23 : écrivons 23 au-dessous de 276. Ce résultat s'obtient encore en multipliant le précédent par le quotient 2 placé au-dessus, et en ajoutant au produit le résultat anté-précédent. EnQn 672

(*) Dans l'énoncé d*un théorème, il y a toujours une hyp tihèse et une conclusion; la démonstration a pour but de passer de Thypothèse à la conclusion, à l'aide d'une série de déductions évidentes. Le théorème réciproque s'obtient en prenant la conclusion <]u théorème direct pour hypothèse, et Thypolbcse de ce théorème pour conclusion. Dans le cas considéré, l'hypot'aèse du théorème direct est que l'on divise deux nombres par leur plus (;rand commun diviseur; la conclusion est que les quotients obtenus sont premiers entre eux. Le théo* rème réciproque s'énonce en disant : Si l'on divise deux nombres par un troisième nombre et que les quotients obtenus soient premiers entre eux, le troisième nombre est le plus grand commun diviseur des deux premiers. Les réciproques ne sont pas toutes vraies, parce que l'hypothèse et la conclusion n'ont pas toujours le môme degré de généralité : nous eu verrons des exemples en Géométrie»

\niTHMÉTIQt7E. 65

conlienl 2 fois 276 plus 120, c'esi-à-dire un nombre de fois 12 représenté par 23 x 2 4- 10 ou 56 : écrivons 56 au-dessous de 672. Les quotients clierchés sont 56 et 23.

On voit sans peine la règle à suivre. Après avoir écrit i sous le plus grand commun diviseur, et avoir placé le quotient qui lui correspond à gauche de i , il faut multiplier successivement le dernier résultat obtenu par le quotient qui est audessus et ajouter au produit V avant-dernier résultat. On trouve ainsi la série des quotients des restes conséculifs et des deux nombres proposés par leur plus grand comn)un diviseur.

Plus grand commun diviseur de plusieurs nombres.

119. n nombres peuvent admettre un diviseur commun, ils peuvent en admettre plusieurs : le plus grand de tous ces diviseurs s'appelle Xeuv plus grand commun diviseur.

On peut ramener la recherche du plus grand commun diviseur de plusieurs nombres à celle du plus grand commun diviseur de deux nombres, à l'aide du théorème suivant :

Soient n nombres a, ^f y,. - .,1; si d est le plus grand commun diviseur de deux d'entre eux a et (3, le plus grand commun diviseur des n nombres a, (3, y, . . . , X est le même que celui des [n — i) nombres rf, y, . . . , A.

Éa effet, tout diviseur commun des nombres a, |3, y, . . ., X est diviseur commun des nombres dy 7, .., \ puisque tout nombre qui divise a et (3 divise leur plus grand commun diviseur d (114). Réciproquement, tout diviseur commun des nombres £f, y, . . ., X est diviseur commun des nombres a,, |3, />•.., ly puisque tout nombre qui divise d divise ses muK liples a et p. Le plus grand commun diviseur est donc le même pour les deux suites.

D'après ce théorème, la recherche du plus grand commun

De C. — Cours. 1. 5

diviseur de n nombres, ramenée d'abord a celle du plus grand commun diviseur de (n — i) nombres, le sera de môme à celle du plus grand commun diviseur de (n — 2) nombres, et ainsi de suite, jusqu'à ce qu'on parvienne à deux nombres seulement, dont le plus grand commun diviseur sera le plus grand commun diviseur cherché.

Si Ton a, par exemple, les quatre nombres a, (3, y, d, on cherchera le plus grand commun diviseur d des nombres a et p, et la série des nombres a, p, 7, d sera remplacée par celle des nombres d, y, i. On cherchera ensuite le plus grand commun diviseur d' des nombres d et y, et les nombres d, y, d seront remplacés par les nombres d' et d. Le plus grand commun diviseur d" des nombres d' et d sera donc le plus grand commun diviseur cherché. On peut représenter la suite des opérations par le tableau ci-dessous :

120. Dans la pratique, on a intérêt à exécuter le calcul précédent en opérant toujours sur les plus petits nombres. Il peut arriver, en effet, que le plus grand commun diviseur cherché soit le plus petit des nombres considérés. En prenant la précaution indiquée, on diminue d'ailleurs généralement le nombre des divisions à effectuer.

Lorsque le plus grand commun diviseur de plusieurs nombres est égal à l'unité, ces nombres sont dits premiers entre eux dans leur ensemble,

121. D'après ce qui précède, les théorèmes démontrés aux n*"* IH, 115, 117 s'étendent immédiatement au cas de plusieurs nombres. Ainsi :

Tout diviseur commun de plusieurs nombres est diviseur de leur plus grand commun diviseur. Il en résulte que, pour trouver les diviseurs communs de plusieurs nombres, ii sufGt de déterminer tous les diviseurs de leur plus grand commun diviseur.

Lorsqu'on multiplie ou qu'on divise plusieurs nombres par

iRITHMÉTIQUE. 67

un certain nombre, leur plus grand commun diuiseur est multiplié ou dii/isé par le même nombre.

Lorsqu'on divise plusieurs nombres par leur plus grand commun diviseur, les quotients obtenus sont premiers entre eux dans leur ensemble. Réciproquemenl, lorsque les quotients obtenus en divisant plusieurs nombres par un même nombre sont premiers entre eux dans leur ensemble^ le diviseur employé est le plus grand commun diviseur des nombres considérés.

Simplification dans la recherche dn pins grand commun diviaenr.

122. On peut simplifier la recherche du plus grand commun diviseur de deux ou plusieurs nombres, à l'aide des considérations suivantes.

Dans toute division non exacte (44), le dividende est compris entre deax mulliplcs consécutifs du diviseur. Le multiple inférieur représente le quotient pHs par défaut, le multiple supérieur représente le quotient pris par ejrcès. Dans le premier cas, le reste est Texcès du dividende sur le produit du diviseur par le quotient : il est additif. Dans le second cas, le reste est l'excès du produit du diviseur par le quotient sur le dividende : il est soustractif. Le reste soustractif est évidemment l'excès du diviseur sur le reste additif. Par suite, quand le reste additif est plus pvnd que la moitié du diviseur, le reste soustractif est plus petit que cette moitié.

Eo effet; si l'on se reporte à l'égalité fondamentale

D^dQ-i-Vi,

00 voit que le dividende D est compris entre les deux multiples consécutifs £^0 et </(Q + 1) ; et si Ton veut prendre le quotient par excès, 00 a nécessairement (6i)

D = rf(QH-i)-(rf-R).

Cela posé, dans la recherche du plus grand commun diviseur de deux nombres, on a intérêt à rendre chaque reste moindre que la moitié du diviseur correspondant. Cherchons, par exemple, le plus grand commun divi-* £eur des nombres 624 et 216.

sG 9 8 I 26 9 I

La première division donne pour quotient 2 et pour reste 192 qui surpasse la moitié du diviseur 216. Si Ton prend alors le quotient par excès,

c'est-à-dire égal à 3, le reste devient 216 — 19a oa 24. On a, dans ce cas,

Cette égalité montre d'abord que tout diviseur commun de 624 et de 216, divisant 216 x 3, divise la différence 216x3 — 624 ou 24, c'est-à-dire est diviseur commun de 216 et de 24. Elle montre ensuite que, réciproquement, tout commun diviseur de 216 et de 24, divisant 216 x 3, divise la différence 216 x 3 — 24 ou 624} c'est-à-dire est diviseur commun de 624 et de 216. Donc les nombres 624 et 216 d'une part, 216 et 24 d'autre part, admettant la même série de diviseurs communs, ont en particulier le même plus grand commun diviseur.

On arrive par suite au même plus grand commun diviseur, en divisant 216 par le reste additif 192 ou par le reste soustractif 24. De plus, comme le reste additif 192 est ici plus grand que la moitié du diviseur 216, hi division de 216 par 192 donne 1 pour quotient et 216 — 192 ou 24 pour reste. En d'autres termes, la différence entre les deux procédés, c'est que le reste soustractif sur lequel on opère immédiatement dans la seconde méthode n'est autre chose que le reste additif fourni par la division suivante quand on applique la première méthode.

A chaque transformation d*un reste additif plus grand que la moitié du diviseur en reste soustractif correspond donc une division de moins,

123. L'algorithme développé au jf 118 peut encore être suivi quand on pratique la simplification qu'on vient d'indiquer, à la condition de retrancher de chaque produit le terme précédent de la série (au lieu de l'ajouter), lorsqu'on emploie comme facteur un quotient pris par excès- C'est ce que les calculs ci-dessus mettent suffisamment en évidence.

lii. Passons maintenant au cas de plusieurs nombres a, ^,7, ^, et supposons-les rangés par ordre de grandeur croissante.

Divisons successivement p, 7, ^ par a, en opérant de manière que chaque reste soit inférieur à la moitié de a (122). Si l'on désigne ces restes, additifs ou soustractifs, par r, r', r', il résulte de ce qui précède ({ue les groupes a et p, a et 7, a et ^ admettent respectivement les mêmes diviseurs que les groupes a et r, a et r', a et r". Donc les deux séries a, P, 7, (î, d'une part, et a, r, r', r", d'autre part, ont les mômes diviseurs communs et, en particulier, le môme plus grand commun diviseur.

En opérant sur la série a, r, r', r" de la même manière que sur la série a, p, 7, ^, on obtiendra une nouvelle série de nombres moindres admettant toujours le môme plus grand commun diviseur ; et, en continuant ainsi, on mettra rapidement en évidence le plus grand commun diviseur cherché, qui sera le plus petit des quatre nombres obtenus lorsque ce plus petit nombre divisera les trois autres.

Prenons, par exemple, les nombres,

En divisant successivement i32o, 2712, 6208 par 672, on obtient les restes 24, 24, 168. Le second reste est additif, le premier et le troisième

ARITHMÉTIQUE. 6g

sont soustractifs. Deux des restes obtenus étant égaux, la question est ramenée à trouver le plus grand commun diviseur des trois nombres

24, divisant exactement i68 et 672, est le plus grand commun diviseur demandé.

Limitas dn nombre de divisions à eifectner dans la recherche du plus grand commun diviseur de deux nombres.

125. Nous donnerons deux limites différentes. La première suppose qu'on a cherché le plus grand diviseur sans modifier les restes; la seconde, qu'on a appliqué la simplification du n"* 1S2.

Première limite. — Quand on divise deux nombres par leur plus grand commun diviseur, les quotients obtenus sont premiers entre eux (117); et, pour trouver le plus grand commun diviseur i de ces quotients, il faut évidemment (il5) effectuer le mtoie nombre de divisions que pour obtenir le plus grand commun diviseur des deux nombres donnés. On peut donc supposer immédiatement que les nombres considérés a et 6 sont premiers entre eux.

Soit

la série des diviseurs consécutifs, qui se termine par le plus grand com- Dun diviseur i. Le nombre des divisions effectuées est alors égal à /i + i* Dans toute division où le quotient est pris par défaut, le dividende est au moins égal au diviseur augmenté du reste. D'ailleurs, r„., est au moins égal à 2, sans quoi la recherche du plus grand commun diviseur aurait exigé une division de moins. Il en résulte que : r,., ^^ ^^ moins égal à 2 -f-i ou 3, r„3 est au moins égal à 3 -h 2 ou 5, r„^ est au moins égal à 5 -f- 3 ou 8, r^4 est au moins égal à 8 n- 5 ou i3, r,, est au moins égal à i3 + 8 ou 21. On peut donc poser

'•«^ > 10 et r^, > 2 X 10.

Les multiplicateurs de 10 sont ici 1 et 2, et ces multiplicateurs repré^ sentent également les limites inférieures de r^ et de r^,. Si l'on continue à remonter dans la série des diviseurs, les nombres 3, 5, 8, i3, 21, qu'on vient d'obtenir comme limites des différents diviseurs à partir de l'antépénultième, se reproduiront donc nécessairement comme multiplicateurs de 10, et l'on aura

'■—7 > 3 X 10, r„, > 5 X 10, r,.9 > 8 X 10, '•«-io>i3xio, r„.„> 21x10,

d'où l'on déduira encore

r„^^>ïo' et r^„>2Xio'.

fJO ARITHMÉTIQUE.

Ces deux derniers résallats peuvent s'écrire

En poursuivant, les nombres 3, 5, 8, i3, 21 reparaîtront de nouveau comme multiplicateurs de 10^, et Ton sera conduit à

'•«-»x»>ïo* et ^.(3x*+.) > ^ X ïo'- Là loi est évidente. On aura donc, en général,

Pour que r„^^ se confonde avec b ou r,, il faut que n ~ Sp. On a alors

^>io'. '

Mais 10' est le plus petit nombre de /? h- i chiffres. Donc, pour qu'on ait à effectuer n -^i divisions, c'est-à-dire plus de /i = 5/?, il faut que b renferme au moins (/' + 1) chiffres.

En d'autres termes, si b renferme seulement p chiffres, le nombre des divisions aura Sp pour limite supérieure.

On peut donc énoncer ce théorème dû à Lamé :

Dans la recherche du plus grand commun diviseur de deux nombres, Ir nombre des divisions à effectuer ne peut pas dépasser 5 fois le nombre des chiffres du plus petit nombre.

Quand on applique la simplification indiquée au n^ 132, la limite précédente peut se trouver beaucoup duninuée, puisque certains groupes do deux divisions consécutives peuvent être remplacés par une seule division.

Seconde LiMrrE. — Supposons en effet qu'on ait cherché le plus grand commun diviseur des nombres A et B, en employant la simplifica-> tion connue (122). Admettons qu'il ait fallu n divisions pour arriver à ce plus grand commun diviseur, et désignons les restes successivement obtenus par R|, Rî, R3, • • -, R»-i» o. L'avant-demier reste R^, sera en même temps le plus grand commun diviseur des nombres A et B.

Chaque reste devant être inférieur à la moitié du diviseur correspondant, chaque diviseur à son tour est supérieur au double du reste correspondant, et l'on a les (/i — 1) inégalités

B>2Ri, Ri>2Rî, Rï>î»Rj, ..., R»-i>2R«,.

En les multipliant membre à membre et en supprimant les facteurs communs aux deux membres de l'inégalité résultante, on trouve

Or, le plus grand commun diviseur R^-i est au moins égal à l'unité (113) et, par suite, dans le cas le plus défavorable, si l'on a eu /z divisions à effectuer, B l'emporte sur 2»-*.

ABITHMÉTIQUE.

Dans notre hypothèse, la limite supérieure du nombre des divisions exi^ ^ées par la recherche du plus grand commun diviseur de deux nombres ne ]}€ut donc surpasser que d^une unité V exposant de la plus haute puis~ sance de 1 contenue dans le plus petit de ces nombres.

Et en effet, si B, plus grand que 2"'', est moindre que 2", le nombre des divisions effectuées ne peut dépasser n\ car, si ce nombre était seulement égal à (/i +1), on aurait, en se reportant aux notations adoptées el d'après ce qui précède,

B > 2". R„ c'est-à-dire B > 2".