ÉLÉMENTS DE LA THEORIE DES NOMBRES

§ 1. — Périodicité des restes pour certaines suites de nombres entiers.

495. Depuis l'antiquité jusqu'à nos jours, presque tous les grands mathématiciens se sont adonnés à l'étude des propriétés des nombres entiers. 11 est résulté de leurs travaux toute une science, connue sous Je nom de Théorie des nombres ou d'Arithmétique supérieure. Fermât, Ëuler, Lagrange, Legendre, Gauss, Lejeune Dirichlet, Kummer, Kronecker, M. Hermile, pour ne citer que les noms les plus illustres, ont largement contribué à l'organisation de cette science, qui compte un très grand nombre de propositions extrêmement belles par leur simplicité, et où les démonstrations, dues aux eiforls des plus grands géomètres, sont arrivées souvent à un rare degré de perfection.

La théorie des nombres se trouve d'ailleurs souvent avoir les liens les plus étroits avec les théories de l'Algèbre et de l'Analyse et son étude est indispensable à celui qui veut pénétrer un peu profondément dans ces sciences. Je crois être utile à ceux des lecteurs qui veulent poursuivre leur»

i52 LEÇONS D'ARITHMÉTIQUE.

études mathématiques eh résumant, à leur usage, les résultats les plus élémentaires el les plus importants de cette théocie. Beaucoup des pages qui suivent auraient pu être rédigées sans supposer aucune connaissance en Algèbre; mais comme elles ne seront sans doute lues que par des lecteurs ayant déjà commencé Tétude de celte science, je n'ai pas craint de faire appel à quelques notions ou propositions qui appartiennent aux éléments de l'Algèbre-

A96. C'est, habituellement, au début de TAlgèbre que l'on introduit la notion de nombres affectés de signes, de nombres positifs ou négatifs. Je supposerai le lecteur familiarisé avec les règles de calcul relatives à ces nombres. En particulier, désormais, sauf avis contraire, les mots plus grand, plus petit auront le sens de l'Algèbre. On regardera comme un nombre entier tout nombre positif ou négatif dont la valeur absolue est un nombre entier.

Dans ce qui suit, il sera presque uniquement question dénombres entiers positifs ou négatifs. Aussi, toutes les fois qu'il sera question d'un nombre dont on ne dira pas expressément que c'est une fraction, il s'agira d'un nombre entier. De même, lorsqu'il s'agira de polynômes entiers par rapport à une ou plusieurs variables, on supposera essentiellement que les coefficients de ce polynôme sont des nombres entière.

Ces suppositions, qui doivent être toujours présentes à l'esprit du lecteur, seront d'ailleurs rappelées de temps en temps.

497. Un nombre entier b est un diviseur du nombre entier a si la valeur absolue de a est divisible par la valeur absolue de 6 ; il existe alors un nombre entier positif ou négatif c, tel que Ton ait a = 6c; a est un multiple de 6.

Le plus petit multiple commun, ou le plus grand commun diviseur de deux ou plusieurs nombres est le plus petit commun multiple ou le plus grand commun divisetir de leurs valeurs absolues.

La suite des nombres entiers

Q 9 \ 0 i OQ

doit maintenant être regardée comme illimitée dans les deux sens ; il en est de même de la suite des multiples successifs d'un nombre entier ft,

dans laquelle chaque terme se déduit du précédent en lui ajoutant 6; les termes de cette suite, quand on parcourt la suite de gauche à droite, vont en augmentant si 6 est positif, en diminuant si 6 est négatif.

498. Si l'on compare à cette dernière suite un nombre entier a positif ou négatif, ou bien ce nombre sera égal à quelque terme de cette suite, ou bien il tombera entre deux termes consécutifs; dans tous les cas, désignons par bq le plus grand terme de la suite qui soit égal ou inférieur à a, en sorte que a, s'il n'est pas un multiple de 6, tombera entre hq ei bq + b on

PÉRIODICITÉ DES RESTES. tô3

entre bq et bq — b, suivant que b sera positif ou négatif; le nombre 6g sera le seul terme de la suite qui soit inférieur ou égal à a, et tel que la différence a — bqy qui est positive ou nulle, soit moindre que la valeur absolue (le 6; on voit donc qu*il existe un couple (et un seul) de nombres entiers q et r, dont le second est nui ou positif et inférieur à la valeur absolue de 6, tels enfin que Ton ait

Lorsque a et 6 sont des nombres positifs^ r est le reste de la division de u par 6, au sens de la théorie des nombres entiers. Il n*est guère conforme aux habitudes de conserver au mot division ce sens lorsqu'il s*agit de nombres positifs ou négatifs ; le mot division s'entend alors d'ordinaire au sens de la division exacte (n"202) ; en outre, l'emploi du terme diviseur opposé à dividende donne lieu à des confusions, en raison même du sens spécial de ce mot qu'on vient de rappeler. Pour toutes ces raisons, il convient de changer un peu la terminologie.

Je désignerai le nombre positif;*, qui vient d'être défini d'une façon précise, comme le reste de a par rapport au module 6, le mot module remplaçant ici le mot diviseur dans le sens opposé à dividende.

Pour abréger le langage et l'écriture, au lieu de dire le reste de a par rapport à b, on écrira simplement reste de a (mod. 6).

On vient de montrer comment le reste doit être défini quels que soient les signes de a et de 6; toutefois, pour ce qui est des restes, la considération des modules négatifs n'offre aucun intérêt; si l'on a en effet

a:= bq -{- r, on a aussi

en sorte que le reste demeure le môme quand on change le module de signe; aussi regardera- t-on désormais le module comme positif. Le lecteur reconnaîtra d'ailleurs sans peine que cette supposition n'est nullement impliquée dans beaucoup des théorèmes qui suivent. Supposons que le module 6 soit un nombre impair; le nombre r ne sera

jamais égal à - < il sera ou plus petit ou plus grand : suivant qu'on se trouve

dans un cas ou dans l'autre, le nombre positif r ou Je nombre négatif r — b est ce qu'on appelle le reste minimum de a (mod. b); le reste minimum est

positif ou négatif suivant que le nombre entier approché de la fraction

r à - près est approché par défaut ou par excès. On reconnaît de suite

qu'il est caractérisé par l'égalité et les inégalités qui suivent, où on Ta désigné par r,

a = bq' + r\ — ^<r'<^ 499. Revenons au reste (positif) proprement dit. Les théorèmes d'Arithmé-

tique qui reposent uniquement sur Tégalilé a = bq -*- r et sur ce fait quo, si l'on se donne les entiers a, 6, il n'y a qu'un couple de nombres entiers q, r qui vérifient cette égalité, subsistent évidemment, que le nombre a soit positif ou négatif. Ainsi :

La somme ou la différence de deux multiples d'un nombre est un multiple de ce nombre. Pour que la différence entre deux nombres entiers a, h soit un multiple de c, il faut et il suffit que les restes de a et de 6 (mod. r soient égaux. Pour trouver le reste (mod. a) d'une somme de nombres entiers ou d'un produit de nombres entiers, on peut remplacer chacun de ces nombres par un autre qui n'en diffère que d'un multiple de a, en particulier, par le reste de ce nombre (mod. a),

500. Ces diverses propositions, dont le lecteur se rappelle bien que la démonstration est immédiate, et qui résument ce qu'il y a d'essentiel dans le chapitre III, prennent une forme particulièrement simple quand on adopte la notation que je vais expliquer, et qui est due à Gauss.

On dit que deux nombres entiers a, b sont congrus suivant le module c quand leurs restes relativement à ce module sont égaux, ou, ce qui revient au même, quand la différence de ces deux nombres est un multiple de c: on écrit alors

a^b (mod. c)

et l'on énonce a congru à 6, module c ou modulo c. Une pareille égalité s'appelle une congruence suivant le module c. Deux nombres entiers sont incongrus suivant le module c si leurs restes (mod. c) sont inégaux. En particulier, dire qu'un nombre a est congru à 0 suivant le module c, ou écrire la congruence

a ^ 0 (mod. c),

c'est dire que a est divisible par c. En se reportant à celle définition et aux théorèmes que l'on a rappelés dans le numéro précédent, on aperroil immédiatement la vérité des propositions qui suivent :

Deux nombres congrus à un troisième sont congrus entre eux.

On peut ajouter un même nombre entier aux deux membres d'une congruence; on peut aussi en retrancher un même nombre entier; on peut en multiplier les deux membres par un même nombre entier ('). On peut ajouter membre à membre deux ou plusieui-s congruences relatives au même module; on peut multiplier membre à membre deux ou plusieurs congruences suivant le même module. On peut élever au carré, au cube, ...« les deux membres d'une congruence.

Arrêtons-nous seulement sur le cas de la multiplication : dire que les congruences

a^a' (mod. c),

b^b' (mod. c)

I. Pour la division, il y a des précautions à prendre sur lesquelles je reviendrai plus tard, n« 512.

entraînent la congruence

ab^a'b' (mod. c),

c'est écrire sous une forme condensée ce théorème que l'on a rappelé tout à l'heure : on ne change pas le reste (mod. c) du produit de deux nombres entiers a, 6, quand on substitue à ces deux nombres deux autres nombres entiers a% h' qui n'en diffèrent que par des multiples de c. Remarquons encore que, d'après ce qu'on vient de dire, la congruence

a^6 (mod. c)

entraîne la congruence

a— 6 = 0 (mod. c),

et réciproquement; ce n'est que la répétition, sous forme condensée, de la proposition fondamentale : pour que la différence entre deux nombres entiers a, b soit divisible par c, il faut et il suffit que les restes de ces deux nombres, relativement au module c, soient égaux.

En réunissant ces diverses propositions et en les appliquant autant de fois qu'il est nécessaire, on arrive à la proposition suivante :

Si l'on considère un polynôme entier par rapport aux variables a?, y, s, :.. et dont les coefficients soient entiers, c'est-à-dire une somme algébrique de monômes tels que

Aaî*yP2T...,

où le coefficient A est un nombre entier et les exposants «, p, y» ••• d^s entiers positifs ; si dans ce polynôme on remplace successivement les variables .r, y, s, ... d'une part par le système de nombres entiers x^, y,, 2,, ..., d'autre part, par un autre système de nombres entiers ar^, j/j» ^» ••• respectivement congrus aux précédents suivant un module m, les résultats des deux substitutions seront deux nombres entiers Nj, Nj congrus suivant le même module m.

501. Si Ton considère la suite des nombres entiers négatifs et positifs

et que l'on fasse correspondre & chacun de ces nombres son reste par rapport à un module entier positif a, la façon dont ces restes se suivent est évidente : ils sont les mêmes pour deux nombres entiers dont la différence est a, ils se reproduisent donc périodiquement de a en a ; ces restes pour les nombres 0, 1, 2, ..., a — i sont ces mêmes nombres rangés dans le môme ordre, ils se reproduisent dans le même ordre quand on passe aux nombres a, a + I, a + 2, ..., 2a ~ 1, puis aux nombres 2a, 2a + I, 2a + 2, ..., 3a — i, etc. ; c'étaient encore les mêmes nombres dans le même ordre pour les nombres négatifs — a, — a + I, ..., — 2,-1 qui précèdent zéro, etc.

De même, si dans un polynôme quelconque entier par rapport à la variable x, et à coefflcients entiers,

on remplace x par deux nombres entiers dont la différence soit a, les deux résultats seront congrus suivant le module a; si donc, dans ce polynôme, on remplace x par la suite des nombres entiers négatifs et positifs

Ôy ^~~ ébf —^ 1, V, 1, <b, O, ■••

et qu*on prenne les restes par rapport au module a des résultats, ces restes se reproduiront encore périodiquement de a en a, La période des restes pourra d'ailleurs se décomposer en périodes plus courtes.

Si Ton considère par exemple le polynôme aî* + a? + 1, en mettant à la place de x successivement les nombres 0, 1, 2,3, 4, 5, 6, et en calculant les restes par rapport au module 7, on trouve successivement 1, 3, 0, 6, 0, 3; la substitution des nombres 7, 8, 9, 10, H, 12, 13 donnerait des nombres respectivement congrus à ceux-là, etc.

L'étude de ces suites périodiques de restes pour des cas très simples, en particulier pour les polynômes «a:, aaî4 a'» ac'» va nous conduire à des résultats très importants.

Observons d'ailleurs que, jusqu'ici, nous n'avons invoqué que les propositions fondamentales du chapitre IIl, résumées au n' 499. 11 est remarquable que l'élude que nous venons d'indiquer puisse nous conduire très simplement aux propositions fondamentales du chapitre IV, qui sont beaucoup plus cachées.

502. Supposons d'abord, quoique cela ne soit pas nécessaire, que les deux nombres entiers a et 6 soient positifs , et considérons la suite des multiples de a

ou, si l'on veut, la suite des valeurs que l'on obtient en remplaçant, dans ox, a; par la suite des nombres entiers ; si l'on prend les restes des termes de cette suite par rapport au module 6, ces restes se reproduiront périodiquement de 6 en 6; il en est ainsi en particulier du reste 0, qui correspondra certainement aux nombres 6a, 26a, ... ; il peut arriver que parmi les nombres

il y en ait un qui donne, relativement au module 6, le reste 0; soit, en général, h le plus petit nombre entier positif tel que ha soit divisible par 6 ; ha sera le plus petit multiple commun de a et de 6; parmi les multiples positifs de a inférieurs à Aa, savoir :

il n y en a, par hypothèse, aucun qui soit divisible par 6; il en résulte que deux multiples de a obtenus en multipliant a par deux nombres dont la différjence est moindre que h ne peuvent donner le même reste (mod. 6); car s'ils fournissaient le môme reste, leur différence serait divisible par 6, et cette différence s'obtiendrait en multipliant a par un nombre moindre que h.

D*un autre côté, deux multiples de a obtenus en multipliant a par deux nombres dont la différence est h donnent le môme reste (mod. 6).

Si donc on considère la suit^e indéfinie des multiples de a

... — 2a, — a, 0, 2tt, 3w, ..., (h — l)a, ha, (/i+ !)<*» •••

et si l'on divise les termes par 6, la suite des restes (mod. 6) sera périodique, la période contiendra h termes exactement, et h restes consécutifs sont toujours distincts; on peut dire encore que deux termes «a, pa de cette suite sont congrus ou non (mod. b), suivant que a et p sont congrus ou non (mod. h), ICn particulier, si Ton ne s'occupe que des multiples positifs, il est clair que les seuls multiples de a qui donneront un reste nul seront les termes de la suite 0, ha, 2ha, 3ha, ....

Nous rencontrons donc ce théorème :

Tout multiple commun des nombres a, 6 est un multiple de leur plus petit commun multiple ha.

Puisque 6a fournit un reste nul (mod. b), il faut, d'après ce qu'on vient de dire, que b soit un multiple de h.

Désignons par à, h les quotients des divisions de b par h et de ha par 6, les égalités

b = h^, ha = A*6

entraînent la suivante :

Si donc a et 6 sont premiers entre eux, il faut que $ soit égal à 1 et que h soit égal à 6. Donc, les seuls multiples communs de deux nombres premiers entre eux sont des multiples du produit de ces deux nombres. En d'autres termes encore, si un nombre divise un produit de deux facteurs et qu'il soit premier avec l'un d'eux, il divise l'autre.

Si 6 est premier à a, la période des restes contient b termes; les termes qui fournissent des restes nuls sont d'ailleurs connus : ce sont les multiples de 6a. Les 6 multiples consécutifs de a

.0, a, 2rt, ...., (6 — i)a

fournissent 6 restes distincts qui ne peuvent être que les nombres 0, 1, 2, ..., 6 — 1 dans un certain ordre : le reste 0 est fourni par le terme 0 ; les termes a, 2a, 3a, ..., (6 — l)a fourniront comme restes, dans un certain ordre, les nombres 1, 2, .... 6 — I.

Cette proposition s'établit d'ailleurs très aisément quand on admet les

théorèmes fondamentaux sur la divisibilité, que ron vient de démontrer à

nouveau ('), par une voie qui montre bien le rôle que joue la périodicité.

503. Revenons au cas où la période des restes contient h termes. Soit

alors d le plus grand commun diviseur de a et de ^> j ^t - sont premiers

entre eux; mais si l'on considère les deux suites

et qu'on prenne les restes (mod. 6) des termes de la première suite, les

restes |mod. -^j des termes de la seconde, il est clair que Ton formera

ainsi deux suites de restes et que chaque terme de la première suite s'obtiendra en multipliant par d le terme correspondant de la seconde ; donc la périodicité des deux suiles de restes est la même. Or la période pour la première suite contient h termes, par hypothèse ; la seconde en contient

-1, puisque -i Gsl premier a-^; on aura donc

.5 , ab

A = -;» fia = -r

et Ton retrouve ainsi le théorème sur la composition du plus petit commun multiple de deux nombres. En outre, on voit que la période de la seconde suite de restes est fournie parles nombres

rangés dans un certain ordre ; la période de la première suite de restes sera donc composée des nombres

rangés dans un ordre convenable. En particulier, les multiples de a,

a, 2a, 3a, ..., (-^ — 1 ja, fourniront, relativement au module 6, les restes

(/, 2d, 3rf, ..., /^g — 1^ rangés dans un ordre convenable.

f . Ce mode de déinoDStration est dâ k Poinsot {Journal de Liowille^ {'• série, t. X).