Preuves d'une opération par 3, par 9, par 11» etc

Supposons, par exemple, qu'il s'agisse de vérifier une addition. Nous prendrons les restes des diverses parties de la somme par 3 ; nous ferons la somine de ces restes, et nous prendrons le reste de cette somme relatif à 3. Si ce reste est le même que celui de la somme totale, il y aura présomption pour que l'opération soit exacte. Si l'on cherche de même les restes relatifs à 9 et à 11, et qu'à chaque fois le reste de la somme totale soit égal à la somme des restes des parties, la probabilité d'exactitude de l'opération sera augmentée.

L'inconvénient de ces sortes de preuves, en ce qui concerne l'addition, tient à ce qu'il faut faire usage d'opérations de nature plus compliquée que l'addition elle-même. Mais cet inconvénient est bien racheté par l'extrême simplicité de chacune de ces opérations, simplicité qui apparaît

£00 DIVISIBILITÉ f

d'autant mieux que Taddition h vérifier porte sur de plus grands nombres.

Cependant les opérations accessoires que nous indiquons ici exigent que le caractère de divisibilité du diviseur ou module employé soit très simple; c'est ce qui arrive pour les modules 3, 9 et il, et c'est ce qui fait que ce sont les seuls employés pour ces sortes de vérification.

Supposons maintenant qu'il s'agisse d'une soustraction. Nous prendrons les restes des deux parties, relatifs à l'un des trois modules signalés ; si le reste du plus grand nombre surpasse celui du plus petit, le reste de la différence sera la différence des restes ; sinon, on prend le complément au module employé de la différence des restes ; on devra trouver le même reste en opérant sur le résultat de la soustraction.

S'il s'agit d'une multiplication, désignons par A et B le multiplicande et le multiplicateur, par a et par b leurs restes relatifs à l'un des trois modules signalés, par exemple 9, nous aurons :

or nous avons vu que pour multiplier deux sommes entre elles, il suffit de les multiplier terme à terme et d'ajouter les résultats ; trois de ces produits partiels contiendront 9 en facteur, c'est-à-dire formeront un nombre divisible par 9, et nous aurons

AB = 9p -*- ab.

Donc le reste du produit par 9 s'obtient en prenant le reste du produit des restes, aà. Si ce reste est égal à celui trouvé directement pour le produit de la multiplication donnée, on en conclut que la vérification a réussi.

Exemple : Soit à vérifier la multiplication :

DIVISIBILITÉ iOi

599696 449772 374810 42578416 ; le reste relatif au module 3, donné parle multiplicande, est 1 ; celui du multiplicateur est i ; celui du produit doit donc être égal à 1, ce qui est. Les restes relatifs à 9 sont 1, i et 1. Les restes relatifs à 11 sont 8, 7 et 1 ; or 8X7 = 56, dont le reste est 1. Les trois vérifications ont donc réussi. S'il s'agit de la division d'un nombre B par un nombre A, cette opération a donné deux nombres entiers, Q et R, R étant plus petit que A, et qui doivent vérifier l'égalité B = AQ H- R. Désignons par i, a, q, r les restes de ces quatre nombres relatifs à l'un des modules 3, 9 ou 11, par exemple il; nous aurons

B = lliw+ft, A = iin-f.a,

Q = llm'+jr, R=lln'-hr;

or nous venons de voir que AQ =^ ilp H- aq. Donc la somme AQ + R est un multiple de 11 augmenté de a^ et r; le reste de cette somme divisé par 11 sera donc le reste de la somme aq-\-r; on devra trouver ainsi le nombre b pour que la vérification réussisse.

Exemple : Soit à vérifier la division 23496.08 I 4725 45960 I 497 34358 Prenons les restes relatifs à 11 ; ce sont, pour le dividende, 8, pour le diviseur, 6, pour le quotient et le reste, 2 et 7; 8 doit donc être le reste de la division par 11 de 6x24-7, ce qui est. Les restes relatifs à 9 sont 5, 0, 2 et 5; or 5=-0x2-4-5; donc la vérification réussit encore.

DIVISIBILITE

On verrait de même que la vérification relative au module 3 réussit.

* 67. Restes négatifs. — Restes des nombres négatifs. —

Si Ton fait usage des nombres négatifs, il est facile d'étendre la définition du reste.

Nous appellerons reste de B par rapport au modale A, tout nombre, positif ou négatif, dont la valeur absolue soit inférieure

A, et qui, retranché de B, donne pour différence un multiple de A.

Lorsque B n'est pas divisible par A, il est compris entre deux multiples consécutifs de A, AQ et A(Q + 4). La différence entre B et un de ces deux multiples est évidemment inférieure à A, en valeur absolue, et peut servir de reste ; tandis que la différence entre B et tout autre multiple de A est supérieure, en valeur absolue, à A ; par conséquent, le nombre B a deux restes relatifs au module A et deux seulement.

Si nous comparons B au premier multiple, AQ, nous avons B = AQ -4- R, R étant un nombre positif inférieur à A ; R est donc le reste ordinaire de la division de B par A. Si, au contraire, nous comparons B au second multiple, A(Q-l-l), nous pouvons écrire, en tenant compte de l'égalité précédente, B = A (Q H- 1) — A -h R. Le nombre négatif, — A H- R ou — (A — R), est la différence entre B et le second multiple ; il est plus petit que A, en valeur absolue ; c'est donc le nouveau reste. On voit, en outre, que la valeur absolue du nouveau reste est le complément à A du reste ordinaire.

Tout nombre B, non divisible par A, a donc deux restes relatifs à A, l'un positif, l'autre négatif, et les valeurs absolues de ces restes sont complémentaires à A.

Exemple .'15 divisé par 8 donne les deux restes 7 et -—4.

Si A est pair, il peut arriver que les valeurs absolues des restes soient toutes deux égales à la moitié de A ; sinon la valeur absolue de l'un d'eux est supérieure à celle de l'autre, et celui des deux restes qui a la plus petite valeur absolue se nomme le reste minimum.

Exemples : Les deux restes de 59, relatifs au module 6, sont 5 et — l, — 1 est le reste minimum ; les restes de 55, relatifs au module 6, sont j et — 5, 1 est le reste minimum ; les restes de 57, relatifs au module 6, sont 3 et — 3 ; on peut prendre pour reste minimum celui que Ton veut.

Lorsque B est divisible par A, il n'y a qu'un seul reste, 0.

Les divers restes de toutes les divisions par A sont donc 1, 2, 3, A-1,

DIVISIBILITE 103

ËxamiDone maintenant le cas où le nombre B est négatif, le module A restant positif comme précédemment.

Lorsque le nombre négatif B n'est pas divisible par A, il est compris entre deux multiples négatifs consécutifs de A, — AU et — A(Q-hl); il diffère de chacun d'eux d'un nombre moindre que A, en valeur absolue ; car si l'on part de — AQ, il faut ajouter à ce multiple un nombre négatif, moindre que A, en valeur absolue, pour avoir le nombre B ; et si Ton part du second multiple, — A(Q-|-0> il ^aut lui ajouter un nombre positif, moindre que A, pour avoir B. On a donc

B = — AQ — R, d'où B=— A(Q + 4)+A — R; lesdenx restes sont donc — R et A — R, et l'on voit que leurs valeurs absolues ont pour somme A, c'est-à-dire sont complémentaires à A.

Tout autre multiple de A diffère de B d'un nombre positif ou négatif, supérieur à A, en valeur absolue ; car s'il est représenté par — AQ-4-AQ', il faut lui ajouter le nombre négatif

— AQ' — R, pour avoir B, et s'il est représenté par

— A(Q4-1)— AQ', il faut lui ajouter le nombre positif AQ' -I- A — - R, pour avoir B. Le nombre B a donc deux restes relatifs au module A et deux seulement.

Lorsque B est divisible par A, il n'y a qu'un seul reste, le nombre 0.

Les restes donnés par B sont les restes de — B, changés de signes, car si l'on a B = — AQ — R, on a — B = AQ-f-R (on sait que — B est la valeur absolue de B, quand B est négatif) ; la seconde égalité B = — A(Q-f-l)-l-A — R, se traite de la même manière, et donne — B = A (Q-h 1) — (A — R).

Nous n*enip1oierons jamais que des modules positifs, et nous venons de voir que tout nombre positif ou négatif B, a, par rapport à chacun d'eux, deux restes dont les valeurs absolues sont complémentaires au module, sauf dans le cas où B est divisible par le module, et où le reste unique est alors 0.

* 68. Caractère de divisibilité par 7. -^ Cherchons les restes successifs que donnent les unités des divers ordres du système décimal, divisées par 7. Pour cela, divisons l'unité, suivie d'un nombre indéterminé de 0, par 7. Nous aurons :

ooooao

404 DIVISIBILITE

Nous trouvons ainsi pour restes successifs 1, 3, 2, 6, 4, 5 ; à la droite de chacun d'eux, nous abaissons un 0 et Topération se continue ainsi ; la septième opération nous donne de nouveau pour reste 1, et, par suite, à partir de ce moment, les opérations se reproduisent indéfiniment, dans le même ordre ; les 6 restes précédents se reproduisent donc aussi indéfiniment et dans le même ordre. Mais, au lieu des restes 6, 4, 5, nous pouvons prendre les restes complémentaires — 1, — 3, — 2, et nous aurons alors la suite des 6 restes

ly 3, 2,-1, — 3| — 2| qui se reproduisent indéfiniment et dans le même ordre.

Gela posé, si nous considérons un nombre quelconque, N, que nous parcourions ce nombre de droite à gauche, et que nous appelions a, ô, c, d, e, f, g,, .. les chifl'res ainsi rencontrés, il nous est facile d'avoir le reste relatif au module 7. En effet, nous pouvons dire que ce nombre est la somme de a unités, 6 dizaines, c centaines, etc.. Or, a unités est un multiple de 7, augmenté de a ; & dizaines est un multiple de 7, augmenté de 3 b, car une dizaine est un multiple de 7, augmenté de 3; de même, c centaines est un multiple de 7, augmenté de 2 c; et ainsi de suite. En définitive, un nombre quelconque est un multiple de 7, augmenté de la somme algébrique que Ton obtient en parcourant ce nombre de droite à gauche, et en multipliant ses divers chiffres respectivement par 1, 3, 2, — 1, — 3,-2, 1, 3, 2 ; le reste, positif ou négatif, que l'on obtient en divisant cette somme algébrique par 7, est donc l'un des deux restes que donne le nombre N.

Exemple : Considérons le nombre

Au-dessous des chiffres de ce nombre, parcouru de droit i à gauche, écrivons les restes J, 3, 2, — 4, — 3, — 2, 1, 3. .... ;

183 7 0 6570 0 2 3864 231—2 — 3 — 1231—2 — 3 — 123 4, et multiplions respectivement chacun des chiffres du nombre par le reste placé au-dessous de lui, puis ajoutons les résultats obtenus, d'après les règles connues ; nous aurons la somme 69, qui n'est pas divisible par 7 ; donc le nombre donné n'est pas divisible par 7.

Cette méthode permet d'obtenir rapidement le caractère de divisibilité par 11. En effet, les restes que donnent ici les unités du premier, du second, du troisième, etc. ordi'e sont 4, — i,

1,^1, On aura donc le reste de la division d un nombre

par U, en formant la somme algébrique de ses chiffres, pris alternativement avec les signes plus et moins, et obtenus en

parcourant le nombre de droite à gauche. Le nombre précédent donne pour reste — 8 ou 3.

* 69. Caractère de divisibilité par un nombre quelconque positif A. — On divise l'unité suivie d'un nombre indéterminé de 0 par A et on a ainsi les divers restes que donnent les unités des divers ordres du système décimal^ divisées successivement par A. Si, à un certain moment, l'un des restes se reproduit, alors les opérations qui ont suivi se reproduisent indéfiniment et dans le même ordre. Or ceci arrive nécessairement, car les restes positifs relatifs à A sont en nombre limité, A — 1 ; donc, au bout d'un certain nombre d'opérations, on retombe forcément sur un reste déjà trouvé. A partir de ce moment, les restes qui suivent celui-ci se reproduisent indéfiniment et dans le même ordre ; la première partie des restes, celle qui précède celui dont on parle, ne se reproduit pas.

La décomposition d'un nombre quelconque en ses unités des divers ordres, et un raisonnement analogue à celui qui a été fait pour le module 7, nous montrent de suite qu'il suffit de placer au-dessous des chiffres du nombre étudié et parcouru de droite à gauche, les restes que nous avons obtenus dans l'ordre où ils ont été trouvés, de multiplier chaque chiffre par le reste placé audessous de lui, de faire la somme de ces produits partiels et de prendre le reste de cette somme relatif à A, pour avoir le reste demandé.

On peut remplacer certains des restes par les restes négatifs complémentaires, si cela est plus simple, et faire alors la somme algébrique des produits, comme cela s*est fait pour 7 et pour il.

Eccemples:he module 13 conduit aux restes 1, 10, 9, 12, 3, 4, qui se répètent indéfiniment dans cet ordre ; on peut prendre les restes 1, — 3, — 4, — 1, 3, 4.

Alors le nombre 47o628?3f03 donne pour somme algébrique à considérer 3— 4— 3 + 64-324-2 — 18 — 20 — 7-f-12 ou 3, dont le reste est 3.

Le module 17 conduit aux restes 1, 10, 15, 14, 4, 6, 9, 5, 16, 7,2,3,13,11,8,12 ou 1,-7,— 2, — 3, 4, 6, —8, 5,-1, 7, 2, 3, — 4| ^ 6, 8, — 5.

Le module 12 conduit aux restes 1, 10, 4, 4,. ..; les deux premiers ne se reproduisant pas, le reste 4 se reproduit indéfiniment.

^ Remarque. — Nous voyons donc qu'un caractère de divisibilité

I a pour but d'indiquer comment on trouve le reste d'un nombre

I donné relatif à un module déterminé, sans faire, la division du

nombre par le module. Pour qu'il y ait utilité dans la pratique à

106 DIVISIBILITE

faire usage de semblables procédés, il faut que le caractère de divisibilité indique des opérations faciles et plus courtes, dans leur ensemble, que la division indiquée. Cela a lieu pour certains modules simples, 2, 3, 4, 9, 11, dans le système décimal; mais il s'en faut que cela soit fréquent. Quoi qu'il en soit, il y avait un grand intérêt théorique à exposer les méthodes précédentes, et c'est surtout cela que nous avons eu en vue.

Quant au nom adopté de caractère de divisibilité^ il s'emploie surtout quand on a simplement pour but de savoir si un nombre donné est ou n'est pas divisible par le module, et, à ce point de vue, il y a d'autres procédés que les précédents, pour un grand nombre de modules. Nous en parlerons plus tard, quand nous arriverons à de pareils résultats.

* 10. Caractères de divisibilité dans un système de numé* ration quelconque. — Nous chercherons, s'il s'agit du module A, les restes obtenus en divisant les unités des divers ordres par A ; chacun des restes se déduit du précédent en le multipliant par la base du système de numération, et en divisant ce produit par A, car chaque unité se déduit de celle d'ordre immédiatement moindre en la multipliant par la base du système de numération. 11 est clair que ces diverses opérations ne peuvent pas donner des restes indéfiniment différents les uns des autres, puisque le nombre des restes positifs relatifs au module A est limité ; on finira donc après un certain nombre d'opérations par obtenir de nouveau un reste déjà obtenu, et, à partir de ce moment, le^ mêmes opérations se reproduiront indéfiniment dans le même ordre, ainsi que les restes auxquels elles conduisent. La suite des restes se compose donc de deux parties : une partie, placée au début, et qui ne se reproduit pas, et une partie périodique qui se reproduit indéfiniment ; la première partie peut, d'ailleurs, ne pas exister, et la partie périodique contenir tous les restes différents et commencer dès le début de la suite.

On écrit alors au dessous des divers chiffres d'un nombre quelconque, parcouru de droite à gauche, les restes que l'on a obtenus et dans Tordre où ils ont été obtenus, et l'on fait le produit de chacun de ces chiffres par le reste placé au-dessous, puis la somme de ces divers produits (n® 68) : il suffit alors de diviser cette somme par A pour avoir le reste que donne le nombre donné, divisé par A.

Exemples : Soit à trouver le reste de la division par K da nombre

écrit dans le système duodécimal.

L'unité ordinaire donne pour reste i ; l'unité du second ordre

donne le même reste que \2, c'est-à-dire 2; Tunîté du troisième ordre donne le même reste que 2 X 12 = 24,, c'est-à-dire 4 ; l'unité du quatrième ordre donne le même reste que 4 X *2 = 48, c'est-à-dire 3 ; l'unité du cinquième ordre donne le même reste que 3 X 12 = 36, c'est-à-dire 1. A partir de ce moment, les restes 1^ 2, 4, 3 se reproduisent indéfmiment et dans le môme ordre. Si nous remplaçons les restes 4, 3 par les restes négatif complémentaires à 5, — i, et — 2, nous avons k suite des restes

qui est périodique et dont la période se compose des quatre restes 4, 2, -i, -2

Écrivons maintenant ces divers restes au-dessous des chiffres du nombre donné, en commençant par la droite (voir no 68) : a 96P 0 578 — 2—12 1 —2 —12 1; rappelons-nous que a = f 0, P = H , formons le produi t de chacun des restes par le chiffre placé au-dessus de lui, et la somme algébrique de tous ces produits ; nous aurons

Le reste relatif à 5 est donc 1 .

Cherchons encore le reste de la division par 16 de ce môme nombre. Les divers restes que donnent les unités des divers

ordres divisés par 16 sont 1, 12, 0, 0, 0, , ou 1, —4, 0,0,

Le reste est donc le même que celui de la somme 8 — 28 = — 20. c'est-à-dire —4, ou 12.

Remarque. — Plus tard, nous trouverons, dans certains cas, des caractères de divisibilité plus simples que ceux-ci ; nous les indiquerons à ce moment.

EXERCICES

10 Montrer qu'on a le reste d'un nombre relatif au module 4, en multipliant par 2 le chiffre des dizaines, l'ajoutant au chiffre des unités, puis divisant cette somme par 4.

2« Le reste d'un nombre relatif au module 8 s'obtient en multipliant respectivement les chiffres des unités, des dizaines, des centaines par 1, 2, 4, formant la somme de ces produits et divisant cette somme par 8.

3° Caractères de divisibilité par 14, par iS. 4» Caractères de divisibilité par 19, par 21.

5» Caractère de divisibilité par 73. Montrer qu'on obtient le reste d'un nombre relatif au module 73, en le partageant en tranches de 4 chiffres, à partir de la droite, en prenant la différence entre la somme des tranches de rangs impairs et celle des tranches de rangs pairs, puis divisant cette différence par 73.

6» Dans les sy^Lèmes de base 4, 7, 13, etc., les caractères de divisibilité par ^ sont les mêmes que dans le système décimal.

7° Les caractères de divisibilité par 4 dans le système de base 5, par 5 dans le système de base 6, etc., sont les mêmes que le caractère de divisibilité par 9 dans le système décimal.

8» Trouver les caractères de divisibilité par 3, 5, 7, H, dans le système binaire.

9° Trouver les caractères de divisibilité par 8, 7, 13, dans le système duodécimal.

10* Caractère de divisibilité par 13 dans le système de base

4 1» Caractère de divisibilité par 37 dans le système de base

i2o Caractère de divisibilité par 23 dans le système de base 21.

13° Caractère de divisibilité par 73 dans le système de base 10000.

Énoncer chacun de ces caractères de divisibilité en supposant le nombre donné exactement divisible par le module.