Théorie générale
Soient A et B deux nombres dont il faut chercher le p. g. c. d. ‘
Si B divise A ce sera le P. ge d. cherché ; opérons done la division de A par B ; soit Q le quotient st R le reste. On a donc
A=BQ+R
B n’est donc pas donc pas le p. g. e. d.
Je dis que le p. g. c. d. entre A et B est le même que celui entre Bet R. En effet, tout diviseur de A et b est diviseur de A et BQ (principe IT) ; et tont diviseur de A et BQ est diviseur de leur différence À — BQ (principe I) c'est-àdire R.
Divisons donc B par R et soit
B=RQ+R
Tout diviseur de Bet R est diviseur de B et RQ, done
diviseur de : —R Q/ c’est-à-dire de R’ et ainsi de suite.
On obtient done la suite des opérations suivantes : A=BQ+R B=BQ'+R R= R'Q'+R’ R'= R'Q" R" divisont exactement K’. Je dis que R” est le plus grand commun diviseur cherché.
En effet, le p. g. c. d. doit diviser A et B, donc À et BQ, donc aussi A—BQ=R; divisant B et R, il divise Bet RQ, donc B—RQ':= R'; Divisant B et R'il divise R et R'Q”, donc R — RQ"=R".
D'un autre côté, R” divisant R’ et R” divise (R'Q"” + R”)=R ; divisant R et R’, il divise RQ'+R', c'est-à-dire B ; et divisant B et R, il divise (BQ+R) c'est-à-dire A.
Done R”, divisant A et B, ne peut être plus grand que le plus grand commun diviseur entre ces deux nombres. ‘
R” ne pouvant être, ni plus petit, ni plus grand que le plus grand commun diviseur, lui est égal.
80. Règle.— Pour trouver le p.g c. d. entre deux nombres, on divise le plus grand par le plus petit ; si cette vpe, tion ne donne pas de reste, le plus petit nombre est le p. g. c d. cherché. Dans le cas contraire, on divise le plus petit nombre par le 1er reste, le 1e" reste pur le second, et ainsi de euile jusqu'à ce que la division se fasse exactement. Le . dernier diviseur est le p. g. c. d. cherché,
Ces opérations sont établies comme i-dessous.
EXEMPLE : à rechercher le p. g. c. d. entre 1574 et 192
2 est le p. g. c. d. cherché.
91. Simplifications.—1lo On peut, à un moment quelconque de l'opération, retrancher du plus grand nombre un multiple exact du plus petit. (58).
2° On peut à un moment quelconque de l'opération et sans altérer la valeur du P. g c. d. supprimer dans un reste un facteur premier avec le diviseur,
En effet, le facteur étant premier avec l'un des deux nombres, ne pourra faire partie des facteurs communs qui doivent Composer le p. g. c. d
92. Procédé pour restreindre le nombre des divisions et limiter le nombre des opérations.
On peut toujours, dans une quelconque des divisions précédentes, supposer le reste plus petit. que le 4 diviseur, en Prenant le quotient entier pur défaut ou par excès et que le P. 8. c. d. n'est pas altéré par la forme négative que prend un reste,
Cela posé, soit n le nombre de divisions qu'il a fallu faire Pour obtenir le p. g. c. d. entre A et B. Ona:
Avec les conditions: 2 R< R () 2R"CR
2R; & Ro4
D'où multipliant membre À membre les égalités (1) il vient : 2RX2R X2R°x.. 2R, <B XRXR'XR"..R;1 d'où —
2BX2R'xX2B"%x..) BXB XF’ ....B.
2R,<B (2) Or le plus grand nombre d'opérations que
ou
l'on peut avoir à faire lors de la recherche du P. g. c. d. et donné lorsqu'on arrive à un reste R, = 1 (cas ou les deux nombres sont premiers entre eux) alors (2) devient : 2n < R,
= C'est-à-dire que l’exposant de la puissance à laquelle il faut élever 2 pour obtenir B ou un nombre immédiatement plus petit, est la limite supérieure du nombre des opérations à effectuer.
LT Vies
98. Théorème.— Tout nombre qui en divise deux autres divise leur P. G. 0. D. L
Soit m un nombre divisant À et B et soit D leur p. g. c. d. Je dis que m divise D.
En effet, la recherche du p.g.c. d. donne les égalités suivantes: A=BQ+R |
BRQ+D À Or m divisant A et B, divise R=DQ [ A et B Q done À — BQ c'est-à-dire R ; divisant B et R, il divise Bet RQ’ donc B— RQ’ c'est-àdire D. C. q. f. d.
94 Deux nombres sont dits premiers entre eux lorsqu'ils out pour plus gran: commun diviseur l'unité.
95. Th<orè ne.— Tout nombre qui divise un produit de deux fucteurs A X Bet qui est premier aves l'un d'eux À, divise l'autre B. ,
Soit D un nombre divisant le produit À X B et premier avec À. Je dis qu'il divise B.
En effet D et A sont premiers entre eux, ils ont donc pour p.g. ç. d. l'unité et on à :
A=DQ+R d'où malti-(AB=DQB+RB/ D=RQ'+R pliant par|D B=RQB+RB 5obBr nn vient
R, = Ro+1Qn+2+ 1 Ra B=Rn+1Qn+2B+B
Or D divise AB par hypothèse ot D X QB qui est un
multiple de D. Donc, en vertu de (92), il divise leur p g. c.
ë 96. Théorème.—/Zout nombre premier P qui divise un produit À.B.C. D divise l'un des fucteurs de ce produit.
En effet, si P ne divise pas À, par exemple, c'est qu'il est
premier avec À, et alors, il divise l'autre facteur BXCXD;
s'il ne divise pas B, il divise l'autre facteur C X D du produit
=: B x C x D; enfin, divisant le produit C X D, il doit diviser
l'un des facteurs C ou D (95).
é À, mier
pour
e un & il est XD; oduit iviser
97. Décomposer un nombre en ses facteurs premiers, c'est déterminer les nombres premiers qui divisent le nombre proposé et combi:x 4 fois chacun d'eux y entre comme facteur.
On opère cette : composition en divisant le nombre donné autant de fois qu'il esë pusble par chacun des nombres Premiers, jusqu'à ce que l'on arrive à un dernier quotient qui soit lui-même un nombre prenier.
EXEMPLE : 1260 | 2 Les facteurs premiers sont done : 630 | 2 2,8, 5,7.
315 | 3 2 y entre 2 fois 3 “e “« Es « 5 “e « 1 LL 7 « « 1 «
et alors 1260=2 X3xX5X7 98. Théorème.— Un nombre ne peut étre décomposé en ses facteurs premiers que d’une seule manière,
Supposons qu'on puisse décomposer un nombre P de 2 manières différentes et soient
P=axbxcxd et P=@xbLXcx d !
On a identiquement & X b X € X d = XX c'X d'
Mais alors @ divisant & X b XcX d doit diviser le 2° membre &X b'X c'X d, donc il doit diviser l'un des facteurs (96).
Or, comme tous les facteurs sont premiers, il faut que l’un d'eux soit égal à a. à
Soit a = a ; alors il vient
bXcxd=bx0cx d On prouverait de même que D” doit être = b RE T.
99. Théorème —Un nombre divisible Par plusieurs autres premiers entre eux 2 à 2, est divisible par leur produit.
Soit P un nombre divisible par plusieurs autres a, b,c premiers entre eux.
P étant divisible par a donne P = «Q (1) en appelant Q le quotient,
Or b divise P done aussi son égal a Q ; et, comme il est premier avec « il doit diviser Q etl'onu: Q—=bQ d'où P=aQ = abQ en remplaçant Q par sa valeur.
De même c divise P donc aussi 4bQ’ et, comme il est premier avec a et b, et doit diviser Q et l'ona : Q'=cQ”
D'où enfin
P-abQ'=abc X Q” et P »
abe — Q ce qui montre que «a X b X c divise P
