LIVRE III. S4â

Ex. 4. Reconnaître si dans le système décimal 8798667 18 est divisible par 13.

On a â — — 3, et on ôtera ±13, chaque fois que faire se pourra.

Ainsi 8x( — 3)— |— 7 donne — 17 , ou — 4; qui X — 3 donne 12 et 9 font 21 ou 8; multipliant par — 3 et ajoutant 8, on a — 16 , ou — 3 ; multipliant par — 3 et ajoutant 5,... 1 4 ou 1 ; multipliant par — 3 et ajoutant 6, on a 3; 3x — 3+7 =: — 2 ; — 2x — 3+1 donne 7; +7x( — 3)+8 donne — 13. Le nombre est divisible par 1 3.

Remarque. Si le diviseur d est premier avec la base b, il y aura nécessairement une certaine puissance de la base qui divisée par d, donnera le reste 1 , et cette puissance est autre que b°. En effet de b" à bd—', il y aura d restes tous moindres que d. Aucun de ces restes ne saurait ctre nul : car d étant premier avec b, l’est avec toutes les puissances de b. Donc parmi ces restes tous positifs , moindres que d, et au nombre de d, il y en a au moins deux qui sont égaux. Soient A1, b™~ l~1' les deux puissances de 6, moindres que Ad, qui donnent le même reste r, soient q, q‘ les quotients. On aura

Ak ~ qd-\~r, 6,n-+-1 “ q 'd+r

retranchant, on a Al(Ara — 1) = ( q ‘ — q)d.

Celte égalité prouve que d divise le premier membre; mais d est premier avec Ak; donc il divise Ara — 1. Soit q“ le quotient, on aura bm — 1 —q“d, ou A,n =q“d-\-\. Donc m étant <^d , bm divisé par d donnera le reste 1.

Cela posé soit un nombre N : on déterminera 6“ et on partagera N en tranches de m chiffres à partir de la droite ; A„, AlfcAa étant les tranches, ce nombre sc mettra sous la forme

N = A0+A,6m+A,6,n,+A363”+ . . . Kbim ou N = A, (Am 1 )+A,(6,m — 1 )+A3(63m — 1 )+ . . . +A i(6,,n — 1 ) +A<+A,+Aa+Ar4- etc. +A,.

Or bm — 1 est par hypothèse divisible par d; en général b"" — 1 ou (A™)' — (1)' est divisible par b"' — 1 (I. I , p. 22) , et par con-

ALoiiBBE.

séquenl par d; donc des deux parties dont se compose N, la première k,(Jbm — 1)— |— A ,(6”° — l)+...+Aj(&'“ — 1) est divisible par d, et si la seconde A„+A,+ ...+Aj,qui contientla somme des tranches ajoutées en valeurs absolues , est divisible , le nombre N le sera.

Ex. Reconnaître si 55987689375786 est divisible par 7.

On trouve que 10*’ divisé par 7 donne le reste 1. On partage donc le nombre en tranches de 6 chiffres, tranches qu’on ajoute, en supprimant 7 à mesure qu’il se présente. On peut même sur le champ diminuer de 7 tous les chüFres plus grands que 7 , et 305016 sera réduit à reconnaître si 515501 est divisible 210612 par 7 . A cet effet on applique le moyen ci-dessus, c’est-à- 55 dire qu’on calcule c0-f-c,<J-H;2dJ ..., on trouve pour 515606 résultat 0. Ainsi le nombre est divisible par 7.

S’il existe une puissance de b qui divisée par d donne le reste — 1 , soit b'"' celte puissance. On mettra N sous la forme

N = A0— p- A ,6m J— A36a“'/— H A363nl/— f- ...

ou N = A.^'+^+A,^1”'— 1 )-+- A3(63,m 1)-|- ...

Et pour que N soit divisible par d, il faut et il suffit que la somme des tranches de rang impair , diminuée de celle des tranches de rang pair soit divisible parti. L’analogie de ces caractères avec ceux qui ont été donnés pour b — 1 et 6+1 , est manifeste.

Corollaire. E<‘S calculs précédents peuvent servir aussi à trouver le reste de la division de N par d.

PROPOSITION VI. — PROBLÈME

Déterminer le nombre des diviseurs d’un nombre N.

Soit a, le plus petit nombre premier qui divise N; on divisera N par a,; soit q le quotient, de sorte que N — a.q; si q est encore divisible par a, , soit q — a,q‘, de même q‘ — a,q" , . . ce qui donne N = a.’t/' = a,3q“ . . . Supposons qu’on trouve ainsi Nrra^'N, , N, n’étant pas divisible par a,. Soit a, le plus