ÉLÉMENTS DE LA THÉORIE DES NOMBRES

§ 1. — Périodicité des restes pour certaines suites de nonoJires 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 le nom de Théorie des nombres ou d'Arithmétique supérieure. Fermât, Euler, Lagrange, Legendre, Gauss, Lejeune Dirichlet, Kummer, Kronecker, M. Hermite, pour ne citer que les noms les plus illustres, ont largement contribué à Torganisation de cette science, qui compte un très grand nombre de propositions extrêmement belles par leur simplicité, et où les démonstrations, dues uux efforts 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 leurs

452 LEÇONS D'AUlTHMÉTIQUE.

études mathématiques en résumant, à leur usage, lès résultats les plus élémentaires et les plus importants de cette théorie. 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étudede cette science, je n*ai pas craint de faire appel à quelques notions ou propositions qui appartiennent aux éléments de TAIgèbre.

496. Ost, habituellement, au début de l'Algèbre que Ton 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, pins 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 de 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 entiers.

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

497. Un nombre entier 6 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 l'on ait a = bc; 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 diviseur de leurs valeurs absolues.

La suite des nombres entiers

... , O, «, 1, U, 1 f Cf •}, .. ,

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 h,

dans laquelle chaque terme se déduit du précédent en lui ajoutant 6; les termes de cette suite, quand an 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, on 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, lx)mbera entre 6^ et 6^ -f- 6 ou

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

a = bq -{-r.

Lorsque a et 6 sont des nombres positifs^ r est le reste de la division de a par 6, an 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 r, qui vient d'être défini dune 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 à 6, on écrira simplement reste de a (mod. b).

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'olfre 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 celte 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 le 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

^ à - 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 l'a 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 = 6g + r et sur ce fait que, si l'on se donne les entiers a, 6, il n'y a qu'un couple de nombres entiers g, r qui vérifient cette égalité, subsistent évidemment, que le nombre a soil positif ou négatif. Ainsi :

La somme ou la diCTé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 muUiple 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 muUiple 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émons! rai ion 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 son! incongrus suivant le module c si leurs restes (mod. c) sont inégaux. En par ticulier, 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 à celte définition et aux théorèmes que l'on a rappelés dans le numéro précédent, on aperçoit 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 plusieurs congruenccs 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 mulliplication : dire que les congruences

a^a^ (mod, c),

6^6' (mod.r)

1. Pour la division, il y a des précaution» à prendre sur lesquelles je reviendrai plus t*rd,n»5iî. ^

PÉRIODICITÉ DES RESTES. 455t

entraînent la congruence

ah^a'h' (mod. c),

c'est écrire sous une forme condensée ce théorème que Ton a rappelé tout à l'heure : on ne chanjçe pas le reste (mod. c) du produit de deux nombn s 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)

entraine 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, z, ... et dont les coefficients soient entiers, c'est-à-dire une somme algébrique do monômes tels que

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

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

et que l'on fasse correspondre fx 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 — 1 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 + 1» «+ 2, ..., 2a — 1, puis aux nombres 2a, 2a + I, 2a + 2, ..., 3a — 1, etc. ; c'étaient encore les mêmes nombres dans le même ordre pour les nombres négatifs — a, — a + 1, ..., — 2,-1 qui précèdent zéro, etc.

De mdme, si dans un polynôme quelconque entier par rapporl à la variable x, el à coefficients entiers,

Aca?»" + A,;ir"»-* + As,t"-« + ... + A^ . ,» + A« ,

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

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 x'^ -\- x-^- ij ^n 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, 1 ; la substitution des nombres?, 8, 6,10, il, 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 ax, ax-{ a'^ «', 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 111, résumées au n** 499. Il 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

..., — 3rt, — 2a, —a, 0, a, 2a, 3a, ...

ou, si Ton veut, la suite des valeurs que Ton obtient en remplaçant, dansox, X 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 :

PÉniODIClTÉ DES RESTES. 457

il n y en a, par hypothèse, ancun qui soit divisible par b; il en résulte que deux miiltiples de a obtenus en multipliant a par deux nombres dont la différence 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, ri 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. 5).

Si donc on considère la suite indéfinie des multiples de a

... —2a, —a, 0, 2a, 3a, ..., (A — i)a, ha, (h + i)a, ...

et si Ton divise les termes par 5, la suite des restes (mod. 6) sera périodique, la période contiendra A 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. 6), suivant que « et ^ sont congrus ou non (mod. h). En 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, 2Aa, 3^, ....

Nous rencontrons donc ce théorème :

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

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

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

6 = /ï«. ha = kb

entraînent la suivante :

Si donc a et.6 sont premiers entre eux, il faut que 9 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 première a, la période des restes contient 6 termes; les termes qui fournissent des restes nuls sont d'ailleurs connus : ce sont les multiples de ba. Les 6 multiples consécutifs de a

fournissent 6 restes distincts qui ne peuvent être que les nombres 0, 1, 2, ...^ 6—4 dans un certain ordre : le reste 0 est fourni par le terme 0; les termes a, 2a, 3rt, ..., (6 — i)a fourniront comme restes, dans un certain ordre, les nombres 1 , 2, ..., 6 — 1 . Cette proposition s'établit d'ailleurs très aisément quand on admet les

458 LEÇONS DARITHMÉTIQUE.

théorèmes fondamentaux sur la divisibilité, que Ton 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 "i ^^ d ^^^^ premiers entre eux; mais si l'on considère les deux suites

et qu'on prenne les restes (mod. b) 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 ; doue la périodicité des deux suites 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

'.^ puisque -j est premier a-^; on aura donc

j. ^ IL «*

" = j> /ta = T

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, 2rt, 3a, ..., ^^ — ija, fourniront, relativement au module 6, les restes

d, 2.^37, ...,Q- l)^ rangés dans un ordre convenable.

1. Ce mode de déftïonstration est dû à Poinsot (Journal de Liowille, l" série,!. X).