APPLICATIONS DES THÉORÈMES PRÉCÉDENTS

MS. Problème I. — Trouver le reste de là division d*un nombre A par un diviseur d, sans faire la division.

Soit aef . . . kl le nombre A de n-|- 1 chiffres^ écrit dans une base quelconque 6, on a

A = ab'' + eb''^+.:.kb+l; tout revient à trouver le reste r de la division de b par d. En

effet, les restes de la division de 6', è^, . . . 6" par d, s'obtiendront en multipliant successivement, r par r, r^ par r^

r* par r . . . etc. On aura ensuite le reste de A en multipliant les restes obtenus, respectivement, par les chiffres de ce nombre, l,k, . . ,e^ bf ajoutant les produits, et.cherchantle reste de la somme.

Prenons, pour exemple, le diviseur 7, et supposons le nombre écrit dans la base fO. L*unité donnera pour reste 1, 10, pour reste 3, 100 pour reste 3x3 ou 2, en retranchant immédiatement un multiple de 7; 1000 donnera ensuite pour reste, 2x3 égal à 6, ou — 1 eu prenant le reste négatif; puis 10000, donnera pour reste (— l)x 3 ou —3; 100000, —3x3 ou — 2 ; î 000000, — 2 X 3, c'est-à-dire — 6 ou 1. A partir de là, les six restes 1 , 2, 3, — 1, — 2, — 3 se reproduisent périodiquement dans le même ordre.

MG. Théorème I. — a* — b"* esttoujours divisible par a — b. En effet, la différence des deux nombres aetb étant divisible par a — ft, les deux nombres donnent le même reste r quand

on les divise par a — b (284). a^ et b^ donneront donc le même

reste r"* dans la division par a — b (280), et par suite a* — 6"* sera divisible par a — b (283).

»d7. Théorème IL — oT + *"* ^st divisible par a -f- b, quand m est impair^

En effet a et — è ayant leur différence a + & divisible par a -|- è donnent le même reste r, quand on les divise par

ft + b. a"* et (— 6)"* donneront donc pour reste r^ et, par suite, a* — (— b)^ sera divisible par a + 6. Mais comme m est impair a*" — (- 6~ est égal à a~ + è*" , et le théorème est démontré.

998. Théorème III. — a"* —6"* est divisible par a-|-l> quand m est pair.

La démonstration est toute semblable-àlaiprécédeûte,

989. Problème IL — Trouver le reste de la division d'un nombre donné A par un . diviseur d que la base b surpasse d'un nombre c.

A étant un nombre de n -|- 1 chiffres, posons, comme au n^ 285.

A = aft"-}- efc'*"' + . . . A6-f i. ^ ^

En ajoutant et retranchant un même nombre, on a imraédiat^nent

A = a(è" - c") +.e(fc"-* - c--^) + . . . A(ft c) + ac" + ec"~' + . . . 4- *c + /.

Le nombre contenu dans la première ligne du second membre est divisible par 6 — c ou d (266), le reste de la division du nombre A par d sera donc le reste de la division par d du nombre contenu dans la seconde ligne. Il ne s'agit plus que de donner une règle pour calculer ce nombre. Cette règle est la suivante :

Multipliez le premier chiffre à gauche a du nombre donné par c, ajoutez au produit le chiffre suivant e, multipliez la somme par c et ajoutez le chiffre suivant f, multipliez de nouveau par c, et ainsi de suite, en t&i^minant l'opération par r addition de 1.

La vérification de cette règle n'offre aucune difficulté.

t90. Problème IIL — Trouver le reste de la division d'un nombre A par un diviseur d qui surpasse la base b du nombre c.

En ajoutant et retranchant une même quantité au nombre A représenté, comme tout-à-l'heure, et supposant d'abord n impair, on a

A = a(fc" + c") +^(fc""^ -O +...^k{b + c) — ac -{- ec" . . . .••^kC'{-l.

Mais les binômes 6" -f c", 6"~ — c**" etc., sont divisibles par fc -f- ^ ou ^ '287 et 288), le reste de la division de A par d est donc le même que celui du nombre de la seconde ligne.

Si n avait été pair, on aurait commencé le second membre

para(6** — c").

La règle pour calculer le nombre dont il faut déterminer le reste est toute semblable à celle qui a été donnée dans le pro*blême précédent. La seule. différence, c'est que les chiffres du nombre doivent être pris alternativement avec les signes -fet — , en commençant par le signe -j-. ou le signe —, suivant que le nombre des chiffres du nombre est impair ou pair.,

»»■. Problème IV. — Trouver le caractère de divisibilité d'un nombre par un multiple de la base diminué d'une unité.

Soit pb — 1 le diviseur donné : A étant toujours représenté de la même manière, on aura

398 QUESTIONS D'ALGÈBRE ÉLÉMENTAlKii.

Ap" = aipbf + epipbf + . . . + A/"' (P*) + ^Z^"- Si ensuite on ajoute et retranche un même nombre, il vient

Ap' = a{{pbT -\) + epiipbr' - 1) + . . . AA' {pb -l) + a + «/) + /jo'+... + kp""^ 4- Z/.

Je dis maintenant que la condition nécessaire et sufiRsante, pour que A soit divisible par pb — 1 , est que le nombre de la seconde ligne soit lui-même divisible par pb ^ \.

En ejffet, représentons le nombre de la seconde ligne par B. On voit que si le diviseur pb — 1 divise A, comme il divise la première ligne du second membre (287), il divisera aussi B : la condition énoncée est donc nécessaire. Elle est aussi suffisante,

car si le diviseur pb — \ divise B, il divisera aussi Ap**, et,

comme il est premier avec/)**, il divisera le nombre A.

On calculera B par une règle toute semblable à ceUe du n° 289, seulement on commencera les opérations par la droite au lieu de commencer par la gauche.

ses. Problème V. — Trouver le caractère de divisibilité d'un nombre par un multiple d'j la base augmenté d'une unité.

On opère une transformation du nombre, semblable à celle qu*on a faite dans le problème précédent, et pour obtenir le nombre dont la divisibilité par le diviseur remplace celle du nombre donné, on fait un calcul analogue à celui du no (290) ; seulement, on commence les opérations par la droite au lieu de la gauche.

Je vais maintenant doiiner encore quelques théorèmes qui sont d'une grande importance dans la théorie des membres.

Z9S. Théorème I. — a et 6 étant des riombres premiers entité -eux, les multiples de a, que l'on formé en multipliant ce nomhrepar les h -- 1 nombi^es 1, 2, 3 ... b — 1, donnent des restes différents quand on les divise par b.

En effet, s'il en est autrement, soient ma et na deux des mul;fiples qui donnent le même reste ; leur différence {m—n)a sera; alors divisible par b (283). Mais, comme b est premier avec a, il devrait diviser le nombre m — n qui est plus petit que lui, ce qui est absurde. : .

Corollaire. — Quand on divise les nombres a, 2a., 3a, ....

THÉORÈMES ET PROBLÈMES SUR LES NOMBRES. 39g

(b -r- 1) a par 6, on trouve dans un certain ordre les b -^ \ restes, 1,2, 3 , . . 6— 1.

aei. Théorème IL — xhéorème de rei-maf . — Si un

nombre premier- b ne divise pas a, il divise nécessairement

Les br-l nombres a, 2a, 3a... (b -^ l)a donnent pour

restes, dans un certain ordre, 1, 2, 3 {b~\) (Cor. 293). Lé

produit a X 2a X 3a X {b—\)a donnera donc pour reste

J^ 2: . 3 . . , . . (6—1) (279), et par suite, la différence entre ces •deux nombres

sera divisible par b (283) .

Mais là différence peut s'écrire ainsi :

(a*~*-.l)Xl .2.3 (ft— 1),

«t ou voit que le nombre 6, qui est premier avec le facteur 1.2.3 (6 — 1), divisera nécessairement a*"* — 1.

99&. Théorème III. — Xhéorème de li^irileon. — Aï b

est U7% nombre premier, le nombre 1.2.3.4 (br— 1)4-1

est divisible par b.

. Mettant à part les deux nombres 1 et 6 ~ 1, je dis que les

autres nombres 2,3,4 (6— 2) peuvent être associés, deux à

deux> de manière que le produit de leurs restes, dans la division par 6, soit égal à 1. En effet, h désignant l'un quelconque

des nombres 2,3 b — 2 nécessairement premiers avec 6 on

sait (279) que, si Ton multiplie h successivement par les

nombres 1,2,3 (6—1), on trouvera un nombre et un seul, A,

tel que le produit hk donnera pour reste l'unité quand on le divisera par b. On remarque, d'ailleurs, que k n'est égal à aucun des trois nombres 1, 6 — 1, /i. Cela est évident pour les deux premiers nombres, car h X 1 donne pour reste /?, et b{b — 1) donne pour reste — A ou 6 — ^, nonabre supérieur à 1 puisque h est inférieur k b — 1. Mais si nous supposons k égal à h le nombre Ji^ divisé par b devrait donner pour reste I, et, par suite h^ — \ serait divisible par 6. Le nombre premier 6 diviserait donc /i — 1 ou A + 1, ce qui est impossible, puisque h est plus grand que 1 et plus petit qne 6^1.

: Cela posé, dans le produit 1,2,3,4.. .(6—1) associons les facteurs 1 et 6 — ^ 1, puis les autres facteurs, par groupes de den%

400 QUESTIONS D'ALGÈBRE ÉLÉMENTAIRE. j

facteurs dont le produit divisé par b donne pour reste (

Tunité. Le reste du produit des derniers facteurs sera égal '

à 1 (279) et le reste des deux facteurs 1 et p — 1 sera p • 1 :

ou — t. Appliquant encore le théorème (279), on voit que le I

reste de la division par b du produit 1 . 2 . 3 . 4 . • . (6—1) '

est — 1, et, par suite, que le nombre 1.2.3.4... (é— i)+l ) est divisible par b.

Remarque I. — Le théorème conPrav^e est vrai. Si le nombre b * n'est pas premier, il ne divise pas 1 . 2 . 3 . 4 . .. • (& — l)+t- En effet, soit d un diviseur de 6 : ce nombre divisera néœssairement le produit 1 . 2 . 3 . 4 . . . (fc — 1) dont il sera l'un i des facteurs ; mais comme il ne divise pas 1 , il ne peut diviser le nombre donné. j

Remarque IL — Le théorème de Wilson et le théorème ■ contraire permettent de reconnaître si un nombre est premier ' ou ne Test pas. ' '

«9e. Théorème IV, — Étant donnés deux nombres sl eth premiers entre eux et un troisième c, on peut trouver une infinité de multiples des deux premiers nombres dont la différence soit égale au nombre c. ' ;

Il s'agit de prouver en d'autres termes que, si l'on désigne ' par a, i, c trois nombres entiers et positifs, dont les deuî » premiers sont premiers entre eux, on pourra toujours ré- ; soudre, en nombres entiers et positifs, d'une infinité de ma- j nières, l'équation

(1) . ax — by = c. , On distinguera deux cas.

!• c < é. — De l'équation (1) on déduit

(2) ax=by + c,

et, sous cette forme, on voit qu'il s'agit de prouver qu'on peut , toujours obtenir une infinité de multiples de a qui donnent c pour reste quand on les divise par b.

On a d'abord une première solution du problème, ainsi posé, en appliquant le théorème I, (293); car en multipliant succès- .

sivement a par les nombres 1, 2, 3, 4 (*— 1)> ^^ obtien- 1

dra nécessairement un multiple de a qui, divisé par 6, donnera pour reste c. Mais, d'après le théorème VI (274), on aura une infinité d'autres valeurs de x et, par suite, de y, en ajoutant à la première valeur de x un multiple quelconque de b.

2** c > 6. — Soit q le quotient de c par 6 et r le reste correspondant. L'équation (2) pourra s'écrire ainsi :

aar = è(y + <7) + r,

ou si l'on pose y + (/ égal à y'

ax = by' -f- r.

Cette dernière équation rentre dans le premier cas et elle est satisfaite par une infinité de valeurs entières et positives pour x et y'. Soit (a, p) une solution, on a

et, par suite,

x = a, yz=p^q.

Comme l'équation en x et y' peut être résolue en nombres entiers et positifs, aussi grands que Ton veut, on aura une infinité de valeurs de |3 — q qui seront positives, l'équation proposée a donc encore une infinité de solutions entières et positives.

)M9. Résolution en nombre» entiers de l'équation du premier degpré et deux inconnues» — * La démonstra*

tioh.du théorème précédent conduit à une méthode qui a été donnée par M. Sturm dans son cours du collège Rollin. Soit d'abord l'équation

(1) ax--by = c,

dans laquelle les coefficients de x et y sont de signe contraire. Si un facteur était commun aux trois nombres a, b, c, on commencerait par le supprimer. Il faut alors que a et 6 soient premiers entre eux, car un facteur, ^ui leur serait commun, diviserait c, ce qui est contre l'hypothèse. (Le raisonnement précédent s'appliquerait également au cas où by serait précédé du signe +.)

Cela posé, comme a et b sont premiers entre eux, on pourra trouver une infinité de solutions, ainsi qu'on l'a vu dans la démonstration du théorème précédent. Prenons, par exemple, l'équation

(2) 7x — by = 39.

On aura d'abord

Multiplions maintenant 7 successivement par les nombres