THÉORIE DU PLUS GRAND COMMUN DIVISEUR

93. Deux nombres peuvent admettre un diviseur commun, ils peuvent en admettre plusieurs : le plus grand de tous ces diviseurs s’appelle leur plus grand commun diviseur. Ainsi 36 et 24 ont pour diviseurs communs 2,3,4»^ et 12: 12 est leur plus grand commun diviseur.

94. 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 quijpuisse diviser 36 est 36.

On sera donc conduit, pour chercher le plus grand commun diviseur de deux nombres, à essayer leur division. Si la division 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.

95. II. 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. J’effectue leur division , je trouve 2 pour quotient et 120 pour reste. Je remarque alors que tous les diviseurs communs à 672 et à 276 divisent 120, reste de leur division, c’est-à-dire sont diviseurs communs de 276 et de 120,

Je remarque ensuite que 672 = 276x2-4-120 et que, par conséquent, tous les diviseurs communs à 276 et à 120, divisant 276x2, divisent aussi la somme 276x2-+- 120 ou 672, c’est-à-dire sont diviseurs communs de 672 et de 276.

J’en conclus que les deux groupes ; 672 et 276 d’une part, 276 et 120 de l’i^utre, admettant la même série de diviseurs communs, ont en particulier le même plus grand commun diviseur.

96. Reprenons l’exemple proposé. On est conduit à diviser 276 par 120 : on trouve 2 pour quotient et 36 pour reste. La recherche est 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 rcsic. Enfin, on cherche le plus grand commun diviseur des nomhics 36 ci 12, on trouve' 3 pour qiio-

lient 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 qu7/ 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, est le plus grand commun diviseur cherché.

97. L’opération se terminera nécessairement; car, puisquUl 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 sont premiers entre eux.

Si, dans la recherche du plus grand commun diviseur de deux nombres, on arrive à deux restes 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 (96).

98. Tout commun diviseur de deux nombres divise leur plus grand commun diviseur.

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

Ueportons-nous à l’exemple proposé (96), et prenons 4. par exemple, qui divise 672 et 276. 4 divisant 672 et 276, divisera 120; divisant 276 et 120, il divisera 36; divisant 120 el36, il divisera 12 {*).

( * ) Plus grand commun diviseur de plusieurs nombres. Soient les nombres 672, ^

276, 50 /| et io8. Cherchons le plus (;rand commun diviseur de 204 et de 108: nous trouverons 12. Je dis que le plus (^rand commun diviseur des quatre nombres 672, 276, 204 et 108, est le même que celui des trois nombres 672, 276 et 12. En effet, tout commun diviseur des nombres 20.4 et 108 divise leur plus grand commun diviseur 12 ( 98 ) et, par suite, tout commun diviseur des quatre nombres proposés est commun diviseur de 672, 276 et 12. Réciproquement, tout diviseur de j 2 est diviseur commun des nombres *iû4 et 108 qui sont des mulliples de leur plus grand commun diviseur et , par suite, tout commun diviseur des nombres 672, 27^ et 12, est commun diviseur des quatii’ nombres proposés. I.cs deux systèmes considérés ayant la même série dedivi-

ARITHMÉTIQl'E.

Théorèmes relatifs an pins grand commnn divisenr.

99 . I. En multipliant ou en divisant deux nombres par un troisième nombre, on multiplie ou l’on divise leur plus p,rand commun diviseur par ce troisième nombre.

En effet, en multipliant ou en divisant deux nombres par un troisième nombre^ on multiplie ou l’on divise le reste de leur division par ce troisième nombre.'

Reprenons l’exemple du n° 96 . En multipliant ou en divisantô^a et 2'j6 par 3 , par exemple, on multipliera ou l’on 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 . Enfin, le dividende 120 et le diviseur 36 étant multipliés ou divisés par 3 , le reste 12 sera luimê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 .

100 . Ce qui précède permet de simplifier dans certains cas la recherche du plus grand commun diviseur de deux nombres. Si l’on demande, par exemple, le plus grand commun diviseur des nombres 368 oo 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 multiplier 16 par 100.