PLUS GRAND COMMUN DIVISEUR PLUS PETIT COMMUN MULTIPLE
§ 1. — Plus grand commun diviseur.
133. Un nombre admet plusieurs diviseurs parmi lesquels figurent toujours un et le nombre lui-même ; par exemple, 1, 2, 3, 6 sont les diviseurs de 6. Le nombre des diviseurs de a est limité, puisque les diviseurs sont tous, sauf Tun d'eux, inférieurs à a.
Il y aurait exception si a était nui ; tout nombre peut être regardé comme un diviseur de zéro, zéro peut être regardé comme un multiple d'un nombre quelconque. En raison du caractère exceptionnel
du nombre zéro, nous Texclurons de ce qui suit : en parlant des diviseurs d'un nombre, nous supposerons que ce nombre n'est pas nul ; en parlant des multiples d'un nombre, nous entendrons parler des multiples qui ne sont pas nuls.
Ëtant donnés plusieurs nombres a, 6, c, ... différents de zéro, il peut exister plusieurs nombres qui les divisent tous : un est toujours un pareil nombre ; ces nombres s'appellent les communs diviseurs de a, (, c, ... Leur nombre est limité, car aucun d'eux ne peut dépasser le plus petit des nombres a, i, c, ... ; il y en a un qui est plus grand que tous les autres : c'est le plus grand commun diviseur des nombres a, b, c, ...
La notion du plus grand commun diviseur est capitale en arithmétique; son importance tient surtout à la proposition suivante, dont la démonstration va nous fournir en même temps un moyen pratique pour calculer le plus grand commun diviseur :
Les diviseurs communs de deux ou plusieurs nombres sont les mêmes que les diviseurs de leur plus grand commun diviseur; en d* autres termes : tout diviseur de deux ou plusieurs nombres est un diviseur de leur plus grand commun diviseur.
134. Considérons d'abord le cas de deux nombres a, b. Si a est divisible par 6, tout diviseur de b est un diviseur de son multiple a, donc les communs diviseurs de a et de b sont les mêmes que les diviseurs de b.
Supposons maintenant qu'aucun des deux nombres a, b ne soit divisible par l'autre ; les deux nombres a, b sont alors différents ; supposons a > ô.
Les diviseurs communs kaeih b sont les mêmes que les diviseurs communs à 6 et au reste c de la division de a par b.
Soit, en effet, q le quotient de la division de a par (, on aura
a = bq -{- c.
Tout nombre qui divise a et 6 divise aussi bq : il divise une somme a et l'une de ses parties bq : il divise donc l'autre c. Tout nombre qui divise ^ et c divise aussi bq : il divise les deux parties bq et c d'une somme, il divise donc cette somme qui est égale à a. Ainsi les communs diviseurs de a et de i sont des communs diviseurs de b et de c; les communs diviseurs de 6 et de c sont des communs diviseurs de a et de b. Si l'on range dans un premier tableau tous les communs diviseurs de a et de & et dans un second tableau tous les communs diviseurs de b et de c, tout nombre qui figure dans le premier tableau figure dans le second, tout nombre qui figure dans
le second tableau figure dans le premier ; les nombres qui figurent dans un des tableaux sont les mêmes que ceux qui figurent dans Tautre. Le théorème est démontré.
Si c divise 6, les diviseurs communs de c et de 6 sont les mêmes que les diviseurs de c ; puisque les diviseurs communs de a et de 6 sont les mômes que ceux de c et de b, ils sont aussi les mêmes que les diviseurs de c.
Si c ne divise pas b, on a fait cependant un pas, puisque c est plus petit que b et que, ainsi, la recherche des communs diviseurs de a, b est ramenée k la recherche ^des communs diviseurs des deux nombres plus petits b et c. Soit alors d le reste de la division de b par c; les communs diviseurs de & et de c sont les mêmes que les communs diviseurs de c et de c? ; si d divise c, les communs diviseurs de c eide d sont les mêmes que les diviseurs de d] si d ne divise pas c, soit e le reste de la division de c par d, les communs diviseurs de c et de d sont les mêmes que les communs diviseurs de d et de e ; si e divise d^ ils sont les mêmes que les diviseurs de e ; si e ne divise pas (2, on continuera de la même façon.
Les restes successifs c, (/, e,... vont en diminuante chaque fois, on ne peut en trouver qu'un nombre limité ; mais d'un autre côté, on ne peut être arrêté dans la suite de ces opérations que si Ton rencontre un reste qui divise le précédent : cette circonstance se présentera donc nécessairement. Elle pourra se présenter, en particulier, dans le cas, d'ailleurs remarquable, où Ton parvient à un reste égal à 1 ; ce reste divise certainement le précédent. Soit, dans tous les cas, h le reste qui divise le resle précédent g. Les communs diviseurs de a et de b sont les mêmes que ceux de b et de c, qui sont les mêmes que ceux de c et de d, qui sont les mêmes que ceux de d et de e, ..., qui sont les mêmes que ceux de ^ et de A : et ces derniers sont les mêmes que les diviseurs de h.
Donc les diviseurs communs de a, b sont les mêmes que les divi-* seurs de h (*).
Étant donnés deux nombres a, i, différents de zéro, il existe un nombre h tel que les diviseurs communs de a, b soient les mêmes que les diviseurs de h; ce nombre y qui peut s'obtenir par les opérations précédentes, s'appelle le plus grand commun diviseur de a, b, nom qui est évidemment justifié puisque h est le plus grand diviseur dé h.
I. M. Vacquant, inspecteur général do l'Université, a bien voulu appeler mon attention sur U convenance qu'il y a à insister tout d'abord sur cet énoncé et A ne faire intervenir que plus tard la notion de plus grand commun diviseur. Cette observation acquiert toute sà portée dan^ la théorie du plus grand commun diviseur algébrique, qui est, au fond, identique à celle qu'on vient d'exposer» ' ' ~- ' .
Tanmsry. 8
lU
Considérons, par exemple, les nombres 360 et 172; en divisant 360 par 172, on a pour quotient 2 et pour reste 16; en divisant 172 par 16, on a pour quotient 10 et pour reste 12 ; en divisant 16 par 12, on a pour quotient 1 et pour reste 4; en divisant 12 par 4, on a pour quotient 3 et pour reste 0.
Les diviseurs communs de 360 et de 172 sont les mêmes que les diviseurs communs de 172 et de 16, qui sont les mêmes que les diviseurs communs de 16 et de 12, qui sont les mêmes que les diviseurs communs de 12 et de 4, qui sont les mêmes que les diviseurs de 4, puisque 12 est un multiple de 4. On adopte souvent la disposition suivante pour les calculs, disposition qui montre Tenchaînement des divisions ; au lieu de placer les quotients au-dessous des diviseurs, on les a placés au-dessus, aQn de laisser la place libre pour les restes; d'ailleurs ces quotients n'ont ici aucune importance :
4 est le plus grand commun diviseur.
135. On peut pronter de quelques simplificalions pour cette recherche.
Remarquons d'abord que pour démontrer que les diviseurs communs de a et de b étaient les mêmes que ceux de b et de c, on s'est fondé uniquement sur régalité
qui n'implique pas que c soit plus pelit que 6, qui n'implique donc pas que c soit le reste de la division de a par b ; cette supposition n'est intervenue que plus tard, quand on a remarqué que les restes successifs allaient en diminuant; mais, dans tous les cas, rien n'empêche, pourvu que a, 6, c soient liés par une relation telle que la précédente, de substituer la recherche du plus grand commun diviseur de 6 et de c à la recherche du plus grand commun diviseur de a et de 6.
11 en serait évidemment de même si a, 6, c étaient liés par une relation
telle que
a = bq — c,
car rien n'empêcherait de reprendre sur cette égalité, en les modifiant à peine, les raisonnements que Ton a faits sur l'égalité a := bq + c.
Or, en supposant toujours que c soit le reste de la division de a par 5, on a évidemment «
» b — c est plus petit que c, ii sera avantageux de le substituer à c dans \a recherche du plus grand commun diviseur; c'est ce qui arrivera si Ton a b < 2 c; ainsi dans l'exemple précédent, au diviseur 12 on pourra substituer le diviseur 16 — i2 = 4, et supprimer une division.
136. Règle. — Pour trouver le plus grand commun diviseur de deux nombres dont aucun n'est nul, on divise le plus grand par le plus petit; si la division se fait exactement, le plus petit est le plus grand commun diviseur cherché ; sinon on divise le nombre employé comme diviseur par le reste de la division; puis, le nombre employé comme diviseur dans cette nouvelle division par le reste qu'elle fournit, et ainsi de suite, jusqu'à ce qu'une division réussisse. Le nombre employé alors comme diviseur est le plus grand commun diviseur cherché. Pour simplifier cette recherche, on peut d'ailleurs utiliser les remarques précédentes.
137. Considérons maintenant le cas de plusieurs nombres a,b^€,d^,., : puisque les diviseurs communs k deux de ces nombres a, à sont les mêmes que les diviseurs de leur plus grand commun diviseur D, il est clair que les communs diviseurs de a, é, c, e/,... seront les mêmes que les communs diviseurs de D, c, (/,... ceux-ci sont les mêmes que les diviseurs communs de D', cf..., en désignant par D' le plus grand commun diviseur de D et de c, etc. ; on fînira par n'avoir plus que deux nombres et les diviseurs communs à a, A, c, rf,... seront évidemment les mêmes que les diviseurs du plus grand commun diviseur de ces nombres-là. Ëtant donnés autant de nombres que l'on voudra, il existe donc un nombre dont les diviseurs sont les mêmes que les diviseurs communs des nombres donnés; on lui donne le nom de plus grand commun diviseur de ces nombres; on ramène la recherche de ce plus grand commun diviseur au cas de deux nombres, en s'appuyant sur ce qu'on ne change pas les diviseurs communs de plusieurs nombres en substituant à deux de ces nombres leur plus grand commun diviseur. — 11 est d'ailleurs évident qu'on pourrait aussi bien remplacer trois, quatre,... de ces nombres par leur plus grand commun diviseur.
Soient, par exemple, les nombres 360, 180, 54, 372. 180 est le plus grand commun diviseur de 360 et de 180; le plus grand commun diviseur des quatre nombres est le même que le plus grand commun diviseur de 180, 54, 372; le plus grand commun diviseur de 180 et de 54 est 18; celui de 372 et de 18 est 6 : le plus grand commun diviseur des quatre nombres est 6, et les communs diviseurs de 360, 180, 54, 372 sont les mêmes que les diviseurs de 6.
Dans la pratique, quand on a à chercher le plus grand commun
diviseur de plusieurs nombres, il est généralement avantageux de commencer par les plus petits.
138. Quand on multiplie deux ou plusieurs nombres par un même fadeur, leur plus grand commun diviseur est multiplié par ce facteur. On entend par là que le plus grand commun diviseur des nouveaux nombres est égal au plus grand commun diviseur des anciens nombres multiplié par le facteur par lequel on les a multipliés eux-mêmes.
Dans le cas de deux nombres, cette proposition résulte du procédé exposé pour obtenir le plus grand commun diviseur de deux nombres. Reprenons les notations du n"* 134 : soient a, b les deux nombres proposés, c le reste de la division de a par 6, d le reste de la division de b par e, ..., A le plus grand commun diviseur.
Si Ton multiplie les nombres a et 6 par un facteur m, c'est-à-dire si on substitue aux nombres a, b les nombres am, 6m, le reste osera aussi multiplié par m, c'est-à-dire que cm devra remplacer c; de même le reste de la division de bm par cm sera dm ; tous les restes seront multipliés par m : le plus grand commun diviseur, qui est le dernier de ces restes, sera aussi multiplié par m.
Ainsi le plus grand commun diviseur de 360 et de 172 est 4 : celui de 360 X 5 = 1800 et de 172 X 5 = 860 sera 4 x 5 = 20.
Considéroji^ maintenant le cas de trois nombres a^b^c; soient D le plus grand commun diviseur de a, b et D' le plus grand commun diviseur de D et de c, c'est-à-dire le plus grand commun diviseur de a, 6, c; je dis que le plus grand commun diviseur de am, 6m, cm est D'm ; en effet le plus grand commun diviseur de am et de bm est Dm; le plus grand commun diviseur de Dm et de cm^ ou le plus grand commun diviseur de am, bm, cm, est D'm.
Du cas de trois nombres on s'élève successivement au cas de quatre, cinq, ... nombres. La proposition est générale.
139* Quand deux ou plusieurs nombres sont divisibles par un même nombre m il en çsf de même du plus grand commun diviseur; si on effectue les divisions, le plus grand commun diviseur est lui-même divisé par le nombre m ; c'est-à-dire que le plus grand commun diviseur des nouveaux nombres est égal au plus grand commun diviseur des anciens divisé par m.
On peut démontrer cette proposition de la même façon. que la précédente; on peut aussi observer qu'elle en résulte.
Considérons, par exemple, les trois nombres a, b, c divisibles par m; soit D leur plus grand commun diviseur; soient a',. 6', cf les résultats de la division dea, 6,.c par m^ et soit D' leur plus grand
commun diviseur : le plus grand commun diviseur de ma\ mb\ me' sera, en vertu de la proposition démontrée en premier lieu, égal à mD' ; on aura donc D = 7wD', en d'autres termes D' est le quotient de la division de D par m,
140. En particulier, si l'on divise les nombres a, (, c,... par leur plus grand commun diviseur D, le plus grand commun diviseur des
quotients a', 6', c',... sera --ou un. Les quotients n'auront pas de
diviseur commun autre que un. Réciproquement si les nombres a', b\
c',... ont pour plus grand commun diviseur Tunité et si D est un
nombre quelconque, le plus grand commun diviseur des nombres
a'D, 6'D, c'h^.,,, obtenus en multipliant par D les nombres a', 6',c',...,
sera le produit de un par D, c'est-à-dire D.
Lorsque le plus grand commun diviseur de deux nombres est un,
on dit que ces deux nombres sont premiers entre eux\ ainsi 8 et H
sont premiers entre eux. On peut donc dire : Quand on divise deux
nombres par leur plus grand commun diviseur^ les quotients sont
. .360 ^^ 172 ,^ ^ premiers entre eux\ amsi -7- = 91) et -r- = 43 sont premiers entre
eux; réciproquement quand deux nombres sont premiers entre eux et quon les multiplie par un troisième nombre, ce troisième nombre est le plus grand commun diviseur des produits (*).
On dit que plusieurs nombres sont premiers entre eux deux à deux lorsque chacun de ces nombres est premier à chacun des autres. Ainsi 3, 8, 1 1 sont premiers entre eux deux à deux; 10, 12, 7 ne sont pas premiers entre eux deux k deux, quoique le plus grand commun diviseur de ces nombres soit égal à un.
Remarquons en passant que lorsque deux nombres sont premiers entre eux, tout diviseur de l'un est premier avec tout diviseur de l'autre; car, si ces deux diviseurs étaient multiples d'un même nombre, il en serait de même des deux nombres proposés.
141. Les propositions qui ont été établies au n' 140, bien qu'elles ne soient qu'un cas particulier du théorème du numéro précédent, sont très importantes et il n'est peut-être pas inutile de remarquer que la proposition
1. Ces façons do parler s'ôtendraient d'elles-mêmes au cas de plusieurs nombres, si Ton conTcnait de dire que plusieurs nombres a, b, r, ... sont premiers entre eux quand leur plus grand convnun diviseur est un. A ce sujet le langage vorio un peu suivant les auteurs : quelques-uns disent, dans ce cas, que les nombres sont premiers entre eux, pris dans leur ensemble ; d'autres n'appellent nombres premiers entre eux que ceux que nous appelons premiers entre eux deux à deux. Pour éviter toute confusion, quand il s'agira de plusieurs nombres, je dirai : nombres dont le plus grand commun diviseur est Tunité.
directe résulte immédiatement de ce que le plus grand commun diviseur de plusieurs nombres est le plus grand de leurs communs diviseurs.
Si on désigne encore, en effet, les nombres donnés para, 5,c,..., par D leur plus grand commun diviseur, para', 6',c',... les résultats obtenus en divisant a, 6, c,... par D, je dis que a', 6', c',... ne peuvent avoir d'autre diviseur commun m que l'unité ; si l'on avait en effet
puisque l'on a
on aurait
a = a"mD, b = 6"mD, c = c"mD,... ;
en sorte que les nombres a, b, c auraient pour commun diviseur le nombre mD, qui serait plus grand que D si m était plus grand que un.
Quant à la réciproque, elle deviendrait évidente de la même façon si Ton admettait que tout diviseur commun à plusieurs nombres a, 6, c,... est un diviseur du plus grand D des communs diviseurs de ces nombi^es. Cette proposition a été démontrée plus haut en s'appuyant sur l'opération même qui fournit le plus grand commun diviseur, elle le sera autrement un peu plus bas.
142. On ne change pas le plus grand commun diviseur de deux nombres en multipliant tun d'eux par un facteur premier à Cautre,
Soient en effet a, b les deux nombres; soit m un nombre premier à 6 : je dis que le plus grand commun diviseur de a et de 6 est le même que le plus grand commun diviseur de ma et de b.
Il faut montrer que les diviseurs communs de a et de A sont les mêmes que les diviseurs communs de ma et de 6 : les diviseurs communs de a et de 6 sont évidemment des diviseurs communs de ma et de 6; il suffit donc de montrer que les diviseurs communs de ma et de b sont des diviseurs communs de a et de 6, c'est-à-dire qu'ils divisent a ; or le plus grand commun diviseur de 6 et de m est 1 ; le plus grand commun diviseur de ba et de ma sera donc a; mais tout nombre qui divise b et ma divise aussi ba et ma ; il divise donc leur plus grand commun diviseur a, ce qu'il fallait démontrer.
Inversement, on n'altérera pas le plus grand commun diviseur entre deux nombres a, b en divisant l'un d'eux par un nombre premier à Tautre. On suppose essentiellement que la division se fasse exactement.
Cette proposition est au fond identique à la précédente : dire, en supposant que m soit premier à b, que le plus grand commun diviseur de a et de ^ est le même que le plus grand commun diviseur
de ma et de 6, ou dire que le plus grand commun diviseur de ma et de 6 est le même que le plus grand commun diviseur de a et de 6, c'est dire la même chose.
143. On obtient deux conséquences importantes de ce théorème en supposant successivement que &, que Ton regarde toujours comme premier à m, divise le produit ma ou soit premier avec a.
1^ Si b divise le produit ma^ il est le plus grand commun diviseur de b et de ma, et par suite de b et de a, puisqu'il esl premier avec m : il divise donc le nombre a. Par suite :
Si un nombre divise un produit de deux facteurs et qu'il soit premier avec l'un d'eux, il divise Vautre.
Par exemple, 6 divise 60 = 12x5; il est premier avec 5, il divise donc certainement 12 ; 15 divise aussi 60, il ne divise aucun des facr teurs 12,5, mais il n'est premier avec aucun d'eux.
2* Si b est premier avec a comme avec wi, il est premier avec ma, puisque le plus grand commun diviseur de b et de ma doit être 1, comme le plus grand commun diviseur de b et de a. Donc :
Tout nombre qui est premier avec les deux fadeurs d'un produit est premier avec ce produit.
La première proposition est une des propositions les plus importantes de ] arithmétique, et c'est la facilité avec laquelle elle se déduit de la considération du plus grand commun diviseur qui est la raison de l'ordre adopté dans la présente théorie.
La seconde proposition se généralise comme il suit :
144. Si un nombre est premier avec tous les facteurs d'un produit, il est premier avec ce produit.
Le théorème est démontré quand le produit ne comprend que deux facteurs ; supposons qu'il en contienne trois, p,q, r, et supposons le nombre a premier avec chacun des nombres j[),ç,r : je dis qu'il est premier avec le produitjoçr ; en effet, étant premier avec p, q, il est premier avec pq ; étant premier avec pq et r, il est premier avecp^' X r=pj'r. Du cas de trois facteurs, on passe au cas de quatre, cinq,... facteurs. La proposition est générale.
Si -deux produits sont tels que chaque facteur de Vun soit premier avec chaque facteur de C autre, les deux produits sont premiers entre eux.
Soient en effet abc, pqrs les deux produits ; supposons que a, b, c soient respectivement premiers avec p,q,r,s : a sera premier au produit pqrs, de même ^ et e; pqrs étant premier k a, kb, k c, sera premier à leur produit abc.
Ainsi 3 est premier avec 4, 5, 7, il sera premier à leur produit 140 ;
3 et 13 sont premiers à chacun des nombres 4, 5, 7 : le produit 3 X 13 = 39 sera premier au produit 4x5x7 = 140.
Comme cas particuliers des théorèmes précédents, on aura, en supposant les facteurs égaux dans chaque produit, les théorèmes
suivants :
Si deux nombres sont premiers entre eux, Vun d'eux est premier avec toute puissance de Vautre; toute puissance de F un sera première avec toute puissance de Cautre.
Ainsi 7 et 5 sont premiers entre eux : il en est de même de 7 et de 5^ = 125, de 5' et de 7* = 2401 (*).
145. Quand un nombre est divisible par plusieurs autres qui sont premiers entre eux deux à deux, il est divisible par leur produit.
Supposons que le nombre À soit divisible par les nombres a, A, premiers entre eux ; soit q le quotient de A par a, on aura
k = aq;
le nombre b, premier à a, divise le produit a^; il doit donc diviser le facteur q; si q^ est le quotient, on aura
q = bq\ et par suite
A. = aq:=a {bq') = abq\
ce qui montre que A çst divisible par ab et que le quotient de la division est 7'.
Supposons maintenant que A soit divisible par les nombres a, 6, c, premiers entre eux deux à deux : A étant divisible par les deux nombres a, 6, premiers entre eux, est divisible par leur produit ab, mais ce produit est premier au troisième nombre c (n'» 144), puisque c est premier à chacun des facteurs a, 6; A étant divisible par les deux nombres ab et e, premiers entre eux, est divisible par leur produit abc.
Du cas de trois nombres a, 6, c, on passera au cas de quatre nombres, a,b,c,dy etc. : la proposition est générale. Il convient de la rapprocher du théorème du n* 104, en vertu duquel on obtiendra le môme quotient final en divisant successivement le nombre A par les difiFérents facteurs du produit, ou par le produit.
1. L'ordre que j'ai adopté dans les numéros précédents (142-14i) a été indiqué par Lejeune Dirichlet. (V. Dedekind, Vorlesungen ûher Zahlentheorie.)
