NOMBRES PREMIERS ENTRE EUX

74. Lorsque deux nombres n'admettent pas d'autre commun diviseur que Tunité, ces deux nombres sont dits premiers entre eux.

Il est clair que deux nombres premiers entre eux ont Tunitc pour plus grand commun diviseur; si donc, en appliquant à deux nombres donnés Topération du plus grand commun diviseur, on trouve 1 pour dernier diviseur, il sera certain que les deux nombres donnés sont premiers entre eux. Ainsi, les deux nombres 1 4 et 9 sont premiers entre eux.

PLUS GRAND COMMUN DlVISCDIl.

SIUPLIFKATION.

75. La détermination du plus grand commun diviseur repose tout entière sur le théorème I. Je vais donner à ce théorème une signification plus étendue.

Théorème II. Les communs diviseurs de deux nombres ne changent jms^ quand on remplace lun de ces nombres par la différence entre ce nombre et un multiple quelconque de r autre.

Soient encore les nombres 312 et 1 08. Je prends la différence entre 312 et un multiple quelconque de 108, par exemple 108x3; je dis qu'on peut remplacer 312 parcelle différence 12 ; en d'autres termes, je dis que les communs diviseurs de 512 et de 108 sont les mêmes que ceux de 12 et de 108. En clfet, au moyen de l'égalité

on démontrera , comme précédemment , que les diviseurs communs de 312 et de 108 sont diviseurs communs de 108 et de 12 ; et que réciproquement les diviseurs communs de 108 et de 12 sont diviseurs communs de 312 et de 108; ainsi l'identité entre les deux sortes de diviseurs est bien démon Irée.

76. Je remarque maintenant qu'en divisant un nombre par un autre on détermine le plus grand multiple du diviseur contenu dans le dividende; le multiple suivant est plus grand que le dividende ; on a de la sorte les deux multiples consécutifs du diviseur qui comprennent le dividende. Les différences en Ire le dividende et ces deux multiples sont toutes deux plus pofitos que le diviseur, et leur somme est égale à la différence

dasdeux multiples, el par conséquent au diviseur lui-même. Ainsi, en divisant 39 par 7, on trouve que le dividende 39 est compris entre les deux multiples consécutifs 7x5, 7x6 du diviseur ; il surpasse de 4 le premier multiple et diffèro de 3 du second ; la somme des deux différences est précisé mant le diviseur 7. La première différence est donnée par la division elle-même, c'est le reste de la division ; on obtient la seconde différence en retranchant la première du diviseur. Ces préliminaires étant posés, je reviens à la recherche du plus grand commun diviseur de 312 et de 108. La division de 312 par 108 donne le reste 96 ; ce reste 96 est la différence entre le dividende et le multiple 108x2 du diviseur; la différence avec le multiple suivant est 108 — 96 ou 12 ; or, en vertu du théorème II, on peut remplacer 312 par Tune ou Tautre de ces différences ; on choisira naturellement la plus petite 12. De cette manière, les deux nombres proposés 312 et 108 sont remplacés par les nombres plus simples 12 et 108. Comme 12 divise 108, le plus grand diviseur cherché est 12. Ainsi :

Dans la recherche du plus grand commun diviseur^ si une di-vision donne un reste plus grand que la moitié du diviseur^ on remplace ce reste par V excès du diviseur sur ce reste.

J'applique ce procédé aux nombres 35676 et 25812.

Plus grand eominnii dlvlsenr de plaslears nombrea,

77. Première méthode. Lorsqu'on sait trouver le plus grand commun diviseur de deux nombres, il est facile de déterminer le plus grand commun diviseur d'autant de nombres qu'on veut. Soient, par exemple, les nombres 360, 600, 1368, 4212. Je considère d'abord les diviseurs communs des deux premiers

nombres 560 et 600 ; ces communs diviseui s, ainsi qu'il a clé démontre (n** 73), sont les diviseurs mêmes de leur plus grand commun diviseur 120.

Je considère maintenant les trois nombres 360, 600, 1368. Pour avoir leurs communs diviseurs, il faut, parmi les communs diviseurs des deux premiers nombres, ou parmi les diviseurs de 120, prendre seulement ceux qui divisent le troisième ; ainsi les communs diviseurs des Irois premiers nombres sont les communs diviseurs de 120 et de 1368. Je détermine le plus ^rand commun diviseur 24 de ces deux nombres; les communs diviseurs de 120 et de 1368, et par conséquent les communs diviseurs des trois nombres 360, 600, 1368 sont les diviseurs de 24. Ce nombre 24 est par conséquent le plus grand commun diviseur des trois premiers nombres.

Le raisonnement que Ton vient de faire peut être répété indéfiniment. Pour avoir les communs diviseurs des quatre nombres 360, GOO, 1368, 4212, il faut, parmi les communs diviseurs des trois premiers nombres, ou parmi les diviseurs de 24, prendre seulement ceux qui divisent le quatrième ; ainsi les communs diviseurs des quatre nombres sont les communs diviseurs de 24 et de 4212. Je détermine le plus grand commun diviseur 12 de ces deux nombres ; les communs diviseurs de 24 et de 4212, et par conséquent les communs diviseurs des quatre nombres, sont les diviseurs de 12. Ce nombre 12 est par conséquent le plus grand commun diviseur des quatre nombres proposés. De ce qui précède on conclut :

Règle. Pour trouver le plus grand commun diviseur de plus'eurs no7nbres donnés^ on cherche d'abord le plus grand commun diviseur des deux premiers nombi^es; on cherche ensuite le plus grand commun diviseur du nombre ainsi obtenu et du troisième nombre, puis le plus grand commun diviseur du nombre ainsi obtenu et du quatrième nombre, et ainsi de suite ptsqu^à ce qtCon ait épuisé tous les nombres donnés; le dernier plus grand commun diviseur calculé est le plus grand, commun diviseur cherché.

76 LIVRE H. - CIIAPITHE 111.

Les raisonnements qui précèdent conduisent à cette conclusion générale : les diviseurs communs de plusieurs nombres sont les diviseurs mêmes de leurphis grand commun diviseur.

Pour simplifier autant que possible le calcul, il est bon de commencer les opérations par les plus petits nombres.

78. Deuxième méthode. Celte seconde méthode n-est que l'extension des théorèmes démonirés sur deux nombres à autant de nombres qu'on veut. Et d'abord :

Lemme. Lorsque plusieurs nombres sont tels que le plus petit divise tous les autresy les communs diviseurs des nombres proposés sont les diviseurs du plus petit nombre^ et par conséquent ce plus petit nombre est le plus grand commun diviseur.

On voit, en effet, que tout diviseur commun aux nombres proposés est diviseur du plus petit, et que, réciproquement, tout diviseur du plus petit divise les autres nombres qui sont des multiples du plus petit.

Théorème lit. Les communs diviseurs de plusieurs nombres ne changent pas^ quand on remplace Vun d^eux par la différence entre ce nombre et un multiple de Vun des autres.

Soient les nombres 560, 600, 1368, 4212. Je dis qu'on peut remplacer 600, par exemple, par la différence 120 entre 600 et un multiple 360x2 du premier. En effet, il a été démontré (n** 75) que les communs diviseurs de 360 et de 600 sont les mêmes que ceux de 360 et 120; or, pour avoir les communs diviseurs des quatre nombres proposés, il faut, parmi les communs diviseurs de 360 et de 600, ou, ce qui est la môme chose, de 360 et de 120, prendre ceux qui divisent 1368 et 4212; ce sont précisément les communs diviseurs de 360, 120, 1368, 4212.

En divisant 1368 par 360 et prenant la plus petite différence 72, on pourra de même remplacer 1368 par 72 ; en divisant 4212 par 360, on remplacera aussi 4212 par 108. De celte manière, les quatre nombres proposés sont remplacés par les quatre nombres plus simples 360, 120, 72, 108.

Nous pouvons de même diviser les trois nombres 360, 120, i 08, par le plus petit 72, et les remplacer par les plus petites différences. Mais ici on observe que, 360 étant divisible par 72, on peut supprimer 360, parce que les diviseurs communs de 360 et de 72 sont les diviseurs de 72 ; on n'a plus alors à considérer que trois nombres 24, 72, 36. Comme 72 est divi-^ sib!c par 24, ces trois nombres se réduisent à deux, 24 eto6; opérant sur ces deux nombres comme précédemment, on les remplace par 24 et 12 ; 24 étant divisible par 12, l'opération est terminée ; 12 est le plus grand commun diviseur cherché.

Règle. Pour trouver le plus grand commun diviseur de plu* sieurs nombres donnés^ on divise par le plus petit d^ entre eux tous les autres nombres^ on remplace chacun des nombres divises par la plus petite différence correspondaîite ; on opère de la même manière sur les nouveaux nombres ainsi obtenu^^ et ainsi de suite. Lorsqu'un nombre est divisible par un autre, on le supprime. Lopération sera terminée quand il ne restera plus quhin nombre; ce nombre restant est le plus grand commun rfiviseur cherché,

Yoilà la règle générale; mais il arrive souvent qu'on aperçoit une combinaison particulière qui simplifie beaucoup l'opéralion. Ainsi, dans l'exemple proposé, on remarque que le quatrième nombre moins sept fois le second donne une différence 12; on remplace alors le quatrième nombre par 12; comme 12 divise les trois premiers,-.12 est le plus grand commun diviseur cherché.

Propriétés du plus g^rand commun dlYlsear*

79. Lemme I. Si Pon multiplie le dividende et le diviseur par un même nombre, le quotient ne change pasj et le reste est multiplié par le même nombre.