ÉLÉMENTS DE LA THÉORIE DES NOMBRES

$S 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. Il est résulté de leurs travaux toute une science, connue sous le nom de Théorie des nombres ou d’Arithmétique supérieure. Fermat, Euler, Lagrange, Legendre, Gauss, Lejeune Dirichlet, Kummer, Kronecker, Hermite, 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 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.

études mathématiques en résumant, à leur usage, les 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é l'étude de cette science, je n’ai pas craint de faire appel à quelques notions ou propositions qui appartiennent aux éléments de l’Algèbre.

496. En particulier, je suppose le lecteur familiarisé avec les règles de calcul relatives à ces nombres. Sauf avis contraire, les mots plus grand, plus petit auront le sens de l’Algèbre.

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 polynomes entiers par rapport à une ou

plusieurs variables, on supposera essentiellement que les coefficients de ce

polynome sont des nombres entiers. | 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 b; il existe alors un nombre entier positif ou négatif c, tel que l’on ait a — bc; a est un multiple de b. |

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.

Li ce JE DSC

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

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

498. Si l'on compare à cette dernière suite un nombe entier & positit 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 bg 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 b, tombera entre bg et bg + bou

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

a = bq +r.

Lorsque a et b sont des nombres positifs, » est le reste de la division de A par b, 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 souvent au sens de la division exacte; 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 positifr, qui vient d'être défini d'une facon précise, comme le reste de a par rapport au module b, le mot module remplacant 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. b).

On vient de montrer comment le reste doit être défini quels que soient les signes de a et de b; 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 à aussi

a(rb—a)+r,

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 b soit un nombre impair; le nombre » 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 » 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 reconnait tout de suite qu'il est caractérisé par l'égalité et Les inégalités qui suivent, où on l'a désigné par 7’, b b DATE NES TER

499. Revenons au reste (positif) proprement dit. Les théorèmes d’Arithmé-

/ / À 490 LEÇONS D’ARIT HMÉTIQUE. STAR

tique qui reposent uniquement sur LÉRAE a bq +rel:sur ce, fait que,. de si l’on se donne les entiers a, b, 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 mul

tiple de ce nombre. Pour que la différence entre deux nombres entiers 4, b soit un multiple de c, il faut et il suffit que les restes de a et de b (mod. 6) soient égaux. Pour trouver le reste (mod. a) d’une somme de nombres

entiers où 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 par- . ticulier, 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 IT, 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 multi de. ci on écrit alors ù

a= 0 (mod. c)

et l’on énonce a congru à b, module € ou modulo c. Une pareille égalité s'appelle une congruence GE le module c. Deux nombres entiers sont … 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 €, ou écrire la congruence a = 0 (mod. c),

c'est dire que a est divisible par c. En se reportant à cette définition et aux théorèmes que l’on à 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 (t). On peut ajouter membre à membre deux ou plusieurs 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, . 715 les deux membres d'une congruence. 11150 Arrêtons-nous seulement sur le cas de la multiplication : dire que les

congruences s a= (mod. c), b=b! (mod. c)

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

PÉRIODICITÉ DES RESTES. 491 entraînent la congruence ab = ab! (mod. c),

c’est écrire sous une forme condensée ce théorème qu’on a rappelé tout à l’heure : on ne change pas le reste (mod. c) du produit de deux nombres entiers a, b, quand on substitue à ces deux nombres deux autres nombres entiers «/, b’ 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= b (mod. c)

entraine la congruence a— b=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 €, 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 polynome entier par rapport aux variables æ, y, 3, … et dont les coefficients soient entiers, c’est-à-dire une somme algébrique de monomes tels que

Ax”y8zT..…,

où le coefficient À est un nombre entier et les exposants «, fi, y, des entiers positifs ; si dans ce polynome on remplace successivement les variables x, y, z, … d’une part par le système de nombres entiers æ,, y, z, …, d'autre part, par un autre système de nombres entiers %, Ya, Z2, .. l'espectivement congrus aux précédents suivant un module m, les résultats des deux substitutions seront deux nombres entiers N,, N, congrus suivant le

même module m.

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

PAR NP RE DIUE À ET URE DIE. Ne | PEU

et que l’on fasse correspondre à chacun de ces nombres son reste par rapport à un module entier positif «, la facon 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, 4, 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, « + 1,a+ 2, …, 2a — 1, puis aux nombres 2a, 2a + 1, 2a + 2, …, 3a — 1, etc.; c'étaient encore les mêmes nombres dans le même ordre pour les nombres négatifs —u, — a +1,...,—2,— 1 qui précèdent zéro, etc.

De même, si dans un polynome quelconque entier par rapport à la variable æ, et à coefficients entiers,

AGE + Aa + Ag + + An 10 Am

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

A NS RM DM OS

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

Si l'on considère, par exemple, le polynome x? + x + 1, en mettant à la place de æ 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 nombres7,8, 6,10, 11,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 polynomes ax, ax + a!, x?, 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 II, résumées au n° 499. Il est remar- … quable que l'étude que nous venons d'indiquer puisse nous conduire très simplement aux propositions fondamentales du chapitre IV, qi sont beaucoup plus cachées.

502. Supposons d’abord, quoique cela ne soit pas nécessaire, que les deux nombres entiers a et b 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 «æ, æ par la suite des nombres entiers ; si l’on prend les restes des termes de cette suite par rapport au module b, ces restes se reproduiront périodiquement dé b en b; il en est ainsi en particulier du reste 0, qui correspondra certainement aux nombres ba, 2ba, …; il peut arriver que parmi les nombres

a, 24, 3a, …, (b—1)a il y en ait un qui donne, relativement au module b, le reste 0; soit, en général, À le plus petit nombre entier positif tel que Aa soit divisible par b ;

ha Sera le plus petit multiple commun de a et de b; parmi les multiples positifs de a inférieurs à ha, savoir

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

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

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

— 2a, — a, 0, 2a, 34, .…, (h —1)a, ha, (h + 1)a,

et si l’on divise les termes par b, la suite des restes (mod. b) sera périodique, la période contiendra h termes exactement, et À restes consécutifs sont toujours distincts; on peut dire encore que deux termes «a, fa de cette suite sont congrus ou non (mod. b), suivant que & et $ sont congrus ou non (mod. h). En particulier, si l’on 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, b est un multiple de leur plus petit commun multiple ha.

Puisque ba 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 à, 4 les quotients des divisions de b par À et de ha par b, les égalités

Do Ra D

entraînent la suivante :

Si donc a etb sont premiers entre eux, il faut que & soit égal à 1 et que À soit égal à b. 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 CEUX facteurs et qu'il soit premier avec l’un d’eux, il divise l’autre.

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

DR once la

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

ordre, les nombres 1.9 2, .…, b — 1.

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

ani LEÇONS D'ARITIHMÉTIQUE.

théorèmes fondamentaux sur la divisibilité, que l’on vient de démontrer à nouveau (1), par une voie qui montre bien le rôle que joue la périodicité. 903. Revenons au cas où la période des restes contient À termes. Soit

| oe do ; alors d le plus grand commun diviseur de a et de b, i et — sont premiers

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

Re SARA NES 71 ma DAME PO Al cl

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

d 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

b Rue .

restes (mod — ] des termes de la seconde, il est clair que l’on formera :

la périodicité des deux suites de restes est la même. Or la période pour la

première suite contient k termes, par hypothèse; la seconde en contient

D k b ARE à a? puisque à est premier à —:; on aura donc

b ab = —, ha = — d . dl et l'on 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 par les nombres

Da OS Me

rangés dans un certain ordre ; la période de la première suite de restes sera

donc composée des nombres

b 9 Re LL 0, d, 2d, pa G 1)d

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

fourniront, relativement au module b, les restes * b d, 24,84) G — 1)

rangés dans un ordre convenable.

1. Ce mode de démonstration est dû à Poinsot (Journal de Liouville, 1°° série, t. X).

A à à L < D PORT, Cr RS NE CR

se