CHAPITRE IV

§ I. — DivisibUité.

70. DéflnitionB. — Lorsque deux nombres sont exactement diTisîbles Tun par Tautre, on dit que le second est un diviseur du premier et que le premier est un multiple du second.

Tout nombre plus grand que 1 admet au moins deux diviseurs, lui-même et Tunité. Le nombre zéro peut être considéré comme ayant tous les autres nombres pour diviseurs.

Lorsqu^un nombre n*a pas d'autre diviseur que lui-même et Tunité, on l'appelle nombre premier.

Dans la pratique du calcul, il est à chaque instant utile de savoir, sans longues recherches» si un nombre donné est divisible ou non par un autre, et quel est, dans le second cas, le reste de la division. De là le besoin d'avoir des caractères de divisibilitéf qui sont des moyens simples et rapides pour découvrir la possibilité de certaines divisions et pour calculer les restes de celles qui sont impossibles.

71. Tbéorèmes. — La recherche de ces caractères repose sur les théorèmes suivants :

I. Tout diviseur de plusieurs nombres divise leur somme. Ce théorème s'énonce encore : tout diviseur des différentes parties d'une somme est un diviseur de la somme.

II, Tout diviseur d'un nombre est un diviseur des multiples de ce nombre.

III. Si un nombre est formé de deux parties^ tout nombre qui est diviseur de l'une des parties sans l'être de Vautre n'est pas un diviseur de la somme. IjB reste de la division de cette somme par ce diviseur est le même que celui de la division^ par ce même diviseur j de la partie non divisible,

72. Caractères de divisibilité. — Voici les principaux caractères de divisibilité, ceux auxquels on a le plus souvent recours dans la pratique.

I. Pour qu'un nombre soit divisible par 2 qu par 5, il faut et il suffit que son chiffre des unités soit divisible par 2 ou par 5. Le reste de la division d'un nombre quelconque par 2 ou par 5 est le même que celui de la division par 2 ou par 5 de son chiffre des unités,

II. Pour qu'un nombre soit divisible par 4 ou par 25y il faut et il suffit que V ensemble des deux derniers chiffres à droite forme un nombre divisible par 4 ou par 25. Le reste de la division d'un nombre quelconque par A ou par 26 est le même que celui de la division^ par 4 ou par 25, du nombre formé par Vensemble de ses deux derniers chiffres à droite.

III. Pour qu'un nombre soit divisible par 8 ou par 125, il faut et il suffit que Vensemble de ses trois derniers chiffres â droite forme un nombre divisible par 8 ou par 125. Le reste de la division d'un nombre quelconque par 8 ou par 125 est le même que celui de la division^ par 8 ou par 125, du nombre formé par Vensemble de ses trois derniers chiffres à droite,

rv. Pour qu'un nombre soit divisible par 3 ou par 9, il faut et il suffit que la somme de ses chiffres soit divisible par 3 ou par 9. Le reste de la divisioyi d'un nombre quelconque par 3 ou par 9 est le même que celui de la division, par 3 ou par 9, de la somme de ses chiffres,

V. Pour qu'un nombre soit divisible par 11, il faut et il suffit que la différence entre la somme de ses chiffres de rang impair à partir de la droite et celle de ses chiffres de rang pair soit divisible par 11. Le reste de la division d'un nombre quelconque par 11 est le même que celui de la division par ii de V excès de

la somme des chiffres de rang impair (augmentée au besoin d'un multiple de i\) sur la somme des chiffres de rang pair.

73. Méthode générale pour la recherche des caractères de divisibilité. — S'il est des procédés particaliers pour établir des caractères de divisibilité par certains nombres, il y a aussi des méthodes générales pour déterminer le caractère de divisibilité par un nombre donné quelconque. Elles consistent ordinairement à décomposer en deux parties tout nombre sur lequel on veut essayer la division par le nombre donné, de manière que celui-ci divise Tune de ces parties : s*il divise la seconde, il divise aussi le nombre considéré ; dans le cas contraire, le reste de la division est le même que celui de la seconde partie.

La méthode que nous indiquerons ici comme nous paraissant la plus simple est la suivante :

Supposons qu*il s'agisse de trouver un caractère de divisibilité par un nombre quelconque .n. En divisant par n les puissances successives de 10, ce qui se fait en effectuant la division par n d*un nombre formé de l'unité et d'une suite indéfinie de zéros, on arrive nécessairement après un maximum de n — i opérations à trouver un reste nul ou égal à l'un de ceux que Ton a déjà obtenus. Deux cas peuvent donc se présenter :

i"^ Si la division, après une, deux ou un plus grand nombre d'opérations, conduit à un reste nul, il s'ensuit que tout nombre peut être décomposé en deux parties. Tune divisible par n et contenant l'ensemble des unités exprimées par la première puissance de 10 divisible par n, l'autre comprenant toutes les unités des ordres inférieurs. Si la seconde'partie est divisible par n, le nombre envisagé est aussi divisible par n ; dans le cas contraire, il ne l'est pas et donne un reste qui est le même que celui de la seconde partie.

Les caractères de divisibilité par 2 et 5, 4 et 25, 8 et 125 rentrent dans ce cas et peuvent être établis ensuivant celte méthode. Prenons pour exemple la recherche des conditions de divisibilité d'un nombre quelconque, 57396 par exemple, par 8. On a d'abord :

OirZAT. — JiéTHODOL. i

10 = mult. 8-f-2; 400 = mult. 8 4-4; 1000 = mult. 8; 10000 = mult. 8; etc., puis 87396 = 6

90 ou mult. 8 -+-2x9 300 ou mult. 8 H- 4X3 -h 50000 ou mult. 8, ou 57396 = mult. 8-h(6-+-2x9-4-4x3).

Ce qui se traduit : Pour qu'un nombre soit divisible par 8, il faut et il suffit que la somme obtenue en ajoutant au chiffre des unités simples le double du chiffre des dizaines^ plus le quadruple de celui des centaines ^ soit divisible par 8.

Mais si Ton remarque qu'en ajoutant à l'expression (r)-H2x9 + 4x3) le multiple de 8, (8x9-4-96x3), on ne change pas les conditions de divisibilité, on obtient pour la seconde partie (6 -h 10 x 9 -h 100 x 3), ce qui revient à dire que pour qu'un nombre soit divisible par 8, il faut et it suffit que le nombre formé par ses trois derniers chiffres à droite soit divisible par 8 : c'est ce qu'on a énoncé plus haut (72).

Remarque. — De ce premier cas, on déduirait de même les caractères de divisibilité par 16 ou 2*, 32 ou 2*, etc., 625 ou 5*, 3125 ou 5% etc., et en combinant les facteurs 2 et 5, celui d'un nombre quelconque de la forme générale 2" x 5*.

2^ Si la division conduit à un reste déjà trouvé, les restes qui suivent sont la reproduction périodique et indéfinie des précédents à partir de celui qui se reproduit le premier. En exprimant alors par rapport à n les valeurs respectives de lunité seule, de la première puissance de 10, de la deuxième, de la troisième, etc., pour multiplier ensuite les deux membres de ces égalités respectivement par les chiffres successifs, en allant de droite à gauche, du nombre sur lequel porte Tessai^ le résultat fmalement obtenu en additionnant membre à membre ces dernières égalités donne la décomposition du nombre

proposé en deux parties, dont Tune est un multiple de n et Tantre celle qui permet de formuler le caractère de divisibilité. Cette méthode est celle dont on se sert généralement pour établir les caractères de divisibilité déjà donnés par 3, 9 et 11 . Appliquons-la à la recherche d*un caractère de divisibilité par6d'un nombre quelconque, 93872 par exemple. La division par 6 d'nn nombre formé de Tunité et d'une suite indéterminée de zéros donne le reste 4 qui se reproduit indéfiniment. On a donc :

iO = mult. 6-h4

100 = mult. 6 + 4

1000 = mult. 6+4

10000 = mult. 6 + 4

puis 93872 = 2

70 ou mult. 6 + 4x7 800 ou mult. 6 + 4x8 3000 ou mult. 6 + 4x3 90000 ou mult. 6 + 4x9, ou, enEn, 93872 = mult. 6 + [2 + 4(7 + 8 + 3 + 9)].

Ce qui se traduit ainsi : Pour qu^un nombre soit divisible pdr 6, il faut et il suffit que la somme obtenue en ajoutant au chiffre des unités le quadruple de la somme de tous les autres soit divisible far 6.

Soit encore la recherche d'un caractère de divisibilité par 7 'd'uh nombre quelconque, 2345689 par exemple. La division pv 7 d'un nombre formé de l'unité et d'une suite indéterminée de zéros donne la série des restes 3, 2, 6, 4, 5, 1, qui se reproduit indéfiniment. On peut donc écrire :

10= mult. 7 + 3;

100 = mult 7+2;

1000 = mult. 7 + 6, ou mult. 7 + 7 — 1, ou mult. 7 — 1 ;

10000 = mult. 7 + 4 ou mult. 7 — 3 ;

100000 = mult. 7 + 8 ou mult. 7 — 2 ;

1000000 = muU. 7 + 1;

d'où il vient

80 ou mult. 7 + 3x8

600 ou mult. 7 -+-2x6

5000 ou mult. 7 — 1x5

40000 ou mult. 7—3x4

300000 ou mult. 7 — 2x3

2000000 ou mull. 7 h- 1 X2,

ou, enfin, 2 345689 = mult. 7

H- [(9 + 3X8 + 2X6) — (Ix5 + 3x4-h2x3) + {lx2)].

Ce qui se traduit : Pour quun nombre soit divisible par 7, il faut et il suffitf après ravoir partagé en tranches de trois chiffres à partir de la droite^ avoir additionné dans chaque tranche le chiffre des unités, le triple de celui des dizaines et le double de celui des centaines^ avoir fait ensuite la somme, d^une part des résultats des tranches de rang impair, d'autre part des résultats des tranches de rang pair^ que la différence de ces deux sommes soit divisible par 7 .

Comme ce caractère de divisibilité comporte un assez long calcul, on le présente généralement sous une forme plus simple, en partant de celte remarque que les puissances de 1000 sont des multiples de 7 plus ou moins 1, suivant qu'elles sont paires ou impaires. On peut donc écrire :

1000 = mult. 7 — 1; 1000000 = mult. 7 + 1; 1 000000000 = mult. 7 — 1 ; etc.

De sorte qu'un nombre tel que 6329580471 peut se décomposer ainsi qu'il suit :

d'où 6329580471 = mult. 7 + [(471 -+- 329) — (580 + 6)].

Ce résultat s'énonce : Pour quun nombre soit divisible par 7,

il faui et il suffit^ après Vavoir partagé en tranches de trois chiffres en allant de droite à gauche^ que la différence entre la somme des tranches de rang pair et celle des tranches de rang impair soit divisible par 7.

Remarque. — Celte méthode ne conduit pas toujours à des fonnules simples de caractères de divisibilité ; cependant en Toici quelques-unes qui ne sont pas très compliquées : // faut et il suffty pour qu'un nombre soit divisible : 1® par 33, après l'avoir partagé en tranches de deux chiffres à partir de la droite^ que la somme de ces tranches soit divisible par 33 ;

2* par 27 ou 37, après l'avoir partagé en tranches de trois chiffres à partir de la droite, que la somme de ces tranches soit divisible par 27 ou 37 ;

3» par 13, après Vavoir partagé en tranches de trois chiffres à partir de la droite, que la différence entre la somme des tranches de rang pair et celle des tranches de rang impair soit divisible par 13.

Ce dernier caractère est analogue au second de ceux que nous avons donnés pour le nombre 7.

74. Autres théorèmes relatifs à la divisibilité. — Les théorèmes suivants sont les principaux de ceux qui complètent cette première partie de la divisibilité des nombres.

I. Tout nombre qui en divise deux autres divise leur différence.

II. Tout nombre qui en divise deux autres divise le reste de leur division,

m. Deux nombres qui^ divisés par un troisième^ donnent le même reste, ont leur différence divisible par ce troisième^ et réciproquement.

\S. Le reste de la division d'une somme par un nombre est égal à celui que fournit le total des restes des différentes parties de la somme, respectivement divisées par ce même nombre.

V. Le reste de la division d'une différence par un nombre est égal à celui qu'on obtient en divisant le premier terme de cette différence par ce nombre^ diminué de celui qui résulte de la division du second terme par ce même nombre. Si le premier de

ces deux restes est inférieur à l'autre^ on l'augmente du diviseur pour faire la soustraction,

VI. Le reste de la division d'un produit de plusieurs facteurs par un nombre est égal à celui que fournit le produit des restes des divers facteurs respectivement divisés par ce nombre.

Remarque. — Ce dernier théorème trouve son application immédiate dans la preuve par 9, ou par tout autre nombre, de la multiplication et de la division. Le nombre employé dans cette preuve prend généralement le nom de module,

§ II. — Plus grand commun diviseur.

75. Définitions. — Tout diviseur de plusieurs nombres s'appelle diviseur commun à ces nombres. Plusieurs nombres, quels qu'ils soient, admettent au moins un diviseur commun, l'unité. Le plus grand des diviseurs communs à plusieurs nombres porte le nom de plus grand commun diviseur de ces nombres.

Deux nombres qui n*ont pas de diviseur commun autre que Tunité sont dits premiers entre eux; et plus de deux nombres qui sont dans le même cas sont dits premiers dans leur ensemble.

Si plusieurs nombres sont tels que pris deux à deux, de toutes les manières possibles, ils n'admettent pas de diviseur commun, on dit qu'ils sont premiers deux à deux.

Les nombres 3, 4, 5, 6 sont premiers dans leur ensemble, et les nombres 4, 5, 7, 9 sont premiers deux à deux.

On appelle quelquefois nombres premiers absolus les nombres premiers qui n'admettent comme diviseurs qu'euxmêmes et Tunité, pour les distinguer de ceux qui, comme les ■précédents, sont seulement premiers les uns par rapport aux autres.

76. Reclierche du plus grand commun diviseur de deux nombres. — Soient deux nombres A et B, A étant plus grand que B. Si B divise A, tous les communs diviseurs de A et de B sont les diviseurs de B. Si B ne divise pas A, on sait

que tout commun diviseur de A et de B est un diviseur du reste C de Leur division, et par conséquent un commun diviseur de B et de G. On démontre aussi que, réciproquement, tout commun diviseur de G et de B est un diviseur de A et par conséquent un commun diviseur de A et de B : il en résulte que les deux séries de communs diviseurs de A et de B, d'une part, et de B et de G, d'autre part, sont absolument identiques. Si C divise B, tous les communs diviseurs de B et de G sont les diviseurs de G. Si G ne divise pas B, en représentant par D le reste de leur division, et en raisonnant comme précédemment, on arrive à conclure que les deux séries de communs diviseurs de B et de G, d'une part, et de G et de D, de Tautre, sont absolument identiques. En continuant ainsi, on est amené à un dernier couple de nombres H et K, tel que K divise H, car les restes vont sans cesse en décroissant et il arrive nécessairement un moment où Tun d'eux est nul, même lorsqu'on trouve le reste 1, parce que ce reste devient le dernier diviseur et amène un reste égal à zéro. Mais, d'après notre raisonnement, les communs diviseurs de H et de K, qui sont les diviseurs de K, sont communs au couple de nombres précédents et, en remontant de couple en couple, sont communs diviseurs de A et de B; comme aussi les communs diviseurs de A et de B sont réciproquement communs aux divers couples suivants jusqu'à H et K, et sont les diviseurs de K. De sorte que tous les diviseurs de K sont rigoureusement tous les communs diviseurs de A et de B; et notre raisonnement démontre que pour deux nombres A et B quelconques et difTérents de zéro^ il existe toujours un nombre K qui satisfait à ces conditions. Gomme K est à lui-même son plus grand diviseur, il est par suite le plus grand commun diviseur de A et de B.

La rè^le à suivre pour trouver le plus grand commun diviseur de deux nombres est dès lors la suivante :

On divise le plus grand nombre par le plus petite et si l'opé^ ration se fait exactement, le plus petit nombre est le plus grand ccmmun dioiseur cherché. S'il y a un reste ^ on divise le plus

jfelit nombre par ce reste, et si cette seconde opération se fait ernctement, le reste est le plus grand commun diviseur cherché. S'il y a un deuxième reste^ on divise le pi'emier reste par le deuxième y et Von continue ainsi jusqu'à ce qu'on trouve un reste nuL Le dernier diviseur employé est le plus grand commun diviseur des deux nombres proposés.

Si ce dernier diviseur est Tuniléy les deux nombres sont premiers entre eux.

77. Tb^orèmes relatifs au plus grand commua diviseur de deux nombres. — De la théorie qui précède découlent les propriétés suivantes :

I. Tout nombre qui en divise deux autres divise leur plus grand commun diviseur , et réciproquement.

II. Si l'on multiplie ou si Von divise deux nombres par un troisième^ leur plus grand commun diviseur est multiplié ou divisé par ce troisième.

III. Les quotients de deux nombres par leur plus grand cofnmun diviseur sont premiers entre eux,

78. Recherche du plus grand commun diviseur de plus de deux nombres. — Pour la recherche du plus grand commun diviseur de plus de deux nombres, on part de cette proposition

4'acile k démontrer, d'après la théorie précédente, qu'on ne change pas les résultats de la recherche du plus grand commuât diviseur de plusieurs nombres en remplaçant deux de ces nombres par leur plus grand commun diviseur, et Ton en tire la règle suivante :

Le plus grand commun diviseur de plusieurs nombres s'obtient en cherchant le plus grand commun diviseur de deux de ces nombres, puis le plus grand commun diviseur du résultat obtenu et d'un troisième des nombres proposés, puis le plus grand cornmun diviseur de ce deuxième résultat et d'un quatrième des nombres proposés, et ainsi de suite jusguà ce que tous les nombres donnés soient épuisés. Le dernier plus grand commun diviseur obtenu est le plus grand commun diviseur cherché.

Remarque. — Dans la recherche du plus grand commun

dîTiseur de plusieurs nombres, on abrège les opérations en commençant par les plus petits de ces nombres.

79. Théorèmes relatifs an plus grand commun diviseur de plusieors noaibres. — Les propriétés suivantes résultent de ce qui précède :

I. Tout nombre qui en divise plusieurs autres divise leur plus grand commun diviseur, et réciproquement.

II. Si Fan multiplie ou si l'on divise plusieurs nombres par un autre^ leur plus grand commun diviseur est multiplié ou divisé par cet autre.

III. Les quotients de plusieurs nombres par leur plus grand commun diviseur sont premiers dans leur ensemble.

Ces théorèmes sont la généralisation de ceux qui ont été donnés plus haut relativement au plus grand commun diviseur de deux nombres.

Le dernier établit Vexistence (/e^rouj[)(?5 de nombres premiers entre eux dans leur ensemble.

§ III. — Plus petit commun multiple.

80. Définitions. — Tout nombre divisible par plusieurs autres nombres est un commun multiple de ces nombres. Tels sont les résultats, en nombre infini^ de la multiplication du produit des nombres considérés par d'autres nombres quelconques.

Le plus petit de tous les communs multiples de plusieurs nombres s'appelle le plus petit commun multiple de ces nombres.

81. Recherche du plus petit commun multiple de deux nom- Iw^. — Soient deux nombres A et B; représentons par D Surplus grand commun diviseur, et par A', B' leurs quotients respectifs par ce plus grand commun diviseur (ces quotients sont premiers entre eux). Appelons M un commun multiple des deux nombres A et B ; on a, d'une part,

M = AxQ,

OU, comme A est égal à A' x D, (1) M = A'xDxQ.

D'autre part, le nombre B ou B'xD divise son multiple M, c'est-à-dire le produit A'xDxQ, d'où il suit que B' divise A'xQ; mais comme on démontre que <ou^ nom&rc (jjui divise un produit de deux facteurs et qui est premier avec l'un d'eux divise Vautre^ il en résulte que B' premier avec A' divise Q. On a donc

Q = B'xQ'

et, en remplaçant dans (1), Q par sa valeur B' xQ', il vient, avec un changement d'ordre des facteurs,

M= A'xB'xDxCK.

Ainsi, tout multiple commun aux deux nombres A et B est divisible par le produit A'xB'xD, et comme ce produit est aussi un multiple de A et B, puisque divisé par A il donne le quotient B', et divisé par B le quotient A', il s'ensuit qu'il est le plus petit commun multiple des deux nombres A et B.

Or, ce plus petit commun multiple peut s'écrire

A'xDxB'xD AxB