CHAPITRE VI

NOTIONS SUR LES PRINaPES DE LA THÉORIE DES NOMBRES.

Définitions.

158. Quand deux nombres divisés par un troisième donnent des restes ou des résidus és^SiUXj on dit que ces nombres sont congrus ou équiçalents par rapport au diviseur ou au module considéré.

Le signe ^ est employé pour exprimer la congruence ou Vequwalence de deux nombres.

Soient, par exemple, les nombres 40 et 61 qui, divisés par 7, donnent le même résidu 5. On exprimera leur équivalence par rapport au module;, en écrivant

61^40 (mod. 7).

Puisque 61 équivaut à 40 par rapport au module 7, la différence 61 — 40 est exactement divisible par 7 (93). Comme zéro est divisible par tous les nombres, on peut dire alors que 61 — 40 équivaut à zéro, et poser

61 — 40 ^o (mod. 7).

C'est Qoe autre forme de l'équivalence précédente.

Propriétés dos résidas des multiples.

i59. 1. a et m étant deux nombres premiers entre eux, si Von divise par m les (m — i ) premiers multiples de a, les résidus obtenus sont y dans un certain ordre, les (m — x) premiers nombres.

Considérons la suite des multiples

a, aa, 3^1,..., (m — i)a.

Aucun multiple de cette suite, tel que Xa, ne peut donner zéro pour reste par rapport au module m. En effet, m étant premier avec a ne peut di- ^'ser Xyi, car alors (140) il diviserait ^ < m.

Deux multiples de la même suite, tels que Aa et k'a^ ne peuvent être équivalents par rapport au module m. En effet, leur différence (A^—k)fi, qui est un terme de cette suite, serait dans ce cas divisible par m (93) et conduirait au reste zéro, ce qui est impossible d'après Talinéa précédent.

En résumé, on effectue (/»-— 1) divisions; les résidus obtenus, tous

inférieurs au diviseur m, sont inégaux et différents de zéro; ces résidus reproduisent donc, dans un certain ordre, la série des nombres

IGO. Remarque I. — Le calcul qui précède peut être fait de la manière suivante. Comme le dividende s'accroît de ^ à chaque division, le résida s'accroît également de celui de a. Seulement, quand ]a somme des deux résidus considérés surpasse le module m, on doit en soustraire ce module.

D'après cela, si l'on commence la série des multiples de a psr o.a et si on la poursuit au delà de ( m — i)a, on voit que, les deux multiples o.a et ma ayant zéro pour résidu commun, les deux multiples suivants a et (/7t + i)a donnent aussi le même résidu. Les multiples 2a et (m + a) ^ remplissent donc à leur tour la même condition, et ainsi de suite.

On peut dire, par conséquent, que les résidus o, i, a, 3, (m — i) se reproduisent périodiquement dans un certain ordre, lorsqiCon poursuit indéfiniment la série des multiples de a à partir de o.a.

Le nombre de termes de la période des résidus étant alors égal à iti, si le multiple ka donne un certain résidu par rapport au module /ti, le multiple (k-^lm)a^ où / représente un entier quelconque, donne le même résidu par rapport à m.

Les deux multiples ka et k'a, tels que /• -+- /'= m, donnent des résidus r et r' qui sont aussi complémentaires par rapport à m ; car, la somme de ces deux multiples égale à ma étant exactement divisible par /71, il faut qu'on ait r -h 7^= m. Il est d'ailleurs évident que les dividendes ka et k*a sont également éloignés des termes extrêmes dans la série des multiples A, 217, 3 a, ... , ( 772 — i) a ; il en sera donc de même des restes complémentaires dans la série des résidus.

161. Remarque II.— D'après ce qu'on vient de dire, si les nombres a et ^, premiers avec m, sont équivalents par rapport à ce module, l'ordre des résidus reste identique pour ces deux nombres. Il n'en est plus de même lorsque les nombres a et ^ ne sont pas équivalents par rapport au module choisi.

Si l'on divise a par m, on obtient un résidu r < m, qui est équivalent à a par rapport au module m ; en outre, si a est premier avec m, r l'est aussi en vertu de l'égalité a = mult. de m h- r. On peut donc toujours remplacer a par r, lorsqu'on veut appliquer le théorème du n" 1S9, c'està-dire lorsqu'il s'agit de former la série des résidus fournis par les (m — i) premiers multiples de a.

Pour chaque valeur possible de r, on obtiendra la série des résidus dans un autre ordre. Il y a donc autant d* ordres différents pour la série des résidus I, 2, 3, . . . , ( 77/ — I ), ou il y a autant de manières différentes d'obtenir cette série, qi£il existe de nombres inférieurs à m et premiers avec lui,

162. IL a et b étant deux nombres premiers entre eux et f un entier quelconque^ si Von divise par b les b dividendes

ARITHMÉTIQUE. q3

on obtient pour résidus, dans un certain ordre, les h nombres

En effet, deux quelconques des dividendes considérés, ka-^-fetk'a -h/, ne peuvent donner des résidus égaux, sans quoi leur différence (/'—/■) a serait divisible par b\ ce qui est impossible, puisque b est premier avec a et plus grand que k'— k.

Les b résidus obtenus, étant inégaux et inférieurs à b, forment nécessairement la suite indiquée. ,

163. Remarque.— Lorsqu'un des dividendes XaH-/est premier avec 6, le résidu r qui lui correspond l'est aussi, et réciproquement. C'est ce que montre immédiatement l'égalité Xï?-h/= mult. de i -h r.

Il y a donc autant de nombres premiers apec b dans la suite des dioi" dendes que dans celle des résidus, et ces nombres se correspondent deux à deux.

De plus, tous ces dipidendes sont ou non premiers apec a, suipant que fêta sont ou non premiers entre eux,

164. m. Calculer le nombre des nombres premiers apec un nombre donné et inférieurs à ce nombre.

n est commode de représenter, avec Euler, par le symbole «p(N), le nombre des nombres premiers et inférieurs à N.

En adoptant cette notation, nous partagerons notre démonstration en quatre parties.

1** Soient a et b deux nombres premiers entre eux. Nous établirons d abord la formule

ff(ab) = ^(a).<f{b).

Les ab premiers nombres peuvent être écrits de manière à former un tableau composé de b lignes horizontales contenant chacune a nombres consécutifs. On a ainsi

aûH-i,

|)éH-I,

iù-

■i)fl-*-3,...,

ba.

Les nombres premiers avec le produit ab sont à la fois premiers avec a et premiers avec b ( 142 ).

Tons les nombres premiers et inférieurs à a sont compris dans la première ligne horizontale du tableau formé. Cette ligne renferme donc 7 (a) nombres premiers avec a. D'ailleurs, si /est un nombre premier avec a, tons les nombres de la colonne verticale commencée par / remplissent la même condition ; et, si / n'est pas premier avec a, aucun nombre de cette

q4 AniTHftCÉTIQUE.

colonne ne Test lui-même ( 163). Les b lignes horizontales du tableau ren< ferment donc toutes le même nombre^ (a) de nombres premiers avec a.

11 reste maintenant à découvrir parmi ces nombres ceux qui, étant en outre premiers avec A, le sont avec le produit ab.

Or (162, 163) chacune des <p(a) colonnes verticales considérées renferme le même nombre de nombres premiers avec b que la suite o, 1,2, 3,..., (b — i), c'est-à-dire qu'elle en comprend nécessairement y ( 6). Par conséquent, le nombre des nombres premiers avec le produit ab et inférieurs à ce produit est précisément 7(a).<p(^) ; ce qui démontre la formule proposée.

a*" On peut étendre immédiatement cette formule au cas d'un nombre quelconque de facteurs.

Soient, par exemple, ^, ^, c, d quatre nombres premiers entre eux deux à deux. On a, d'après ce qui précède (1°) et en employant un artifice connu (i41 ),

ff(abcd] = 9[a).^[bcd)^

ff{bcd) =(p(6).(p(ré/),

ff(cd) ='î)(r).(j)(rf),

d'où, en multipliant toutes ces égalités membre à membre et en simplifiant,

^[abcd) = f^[a).ff[b) .f^{c) .ff[d).

3° Gela posé, admettons d'abord que le nombre donné N renferme un seul facteur premier, et soit N = a*. Formons la suite

Si, dans cette suite, on barre tous les nombres qui contiennent a comme facteur ou tous les nombres multiples de a, les nombres restants seront les nombres premiers avec N et inférieurs à ce nombre. Les nombres de la suite multiples de a sont évidemment les seuls nombres

a. a a, oa, . . . , — a,

N dont la quotité est -• Par conséquent on a, dans ce cas particulier,

4"* Soit, enfin, un nombre quelconque N qui, décomposé en facteurs

premiers, donne

N = û*. b^, cl.

Nous aurons à la fois (a° et 3")

iRITHMÉTIQUB. q5

II en résulte donc ?(N)=N(.-i)^.-j)(,-l)=«-.iM.,T-'.(„,)(S,)(r,).

465. Bemarque I. — Si N est un nombre impair^ a est premier avecN. D'ailleurs 7(2) = 2*= i. On a donc dans ce cas

466. Remarque II. — Si N = i , on a 7 (N) = o. Mais, le nombre quelconque a étant égal à a x i et premier avec i , on aurait alors

An lieu de 7(1) = o, on est donc conduite admettre ta relation (p(i) = i. Pour faire concorder celte relation avec ce qui précède, il suffit de modifier la définition de ?(N), en disant que ce symbole représente le nombre des nombres premiers et non supérieurs à N. En effet, i est premier avec 1 et ne lui est pas supérieur.