NOMBRES PREMIERS A UN NOMBRE DONNÉ

quadratique, et ceux-là seuls. En particulier, les diviseur» premiers impairs de la forme a?' + y* sont les nombres premiers de la forme 4n + 1, les divisem^s premiers impairs de la forme x* — 3j/« sont les nombres premiers de la forme 12nd:l.

§ 6. — Sur le nombre de nombres premiers à nn nombre donné et non supérieurs à lui.

527. Nous avons vu au n- 515 comment, dans certaines questions d'Arithmétique, s'introduisait le nombre des nombres premiers à un nombre entier positif a et inférieurs à lui. Ce nombre, si a n'est pas un, se désigne par le symbole ^{a). Si a est égal à un, ç(a)= ç(l) est par définition égal à un. C'est pour embrasser le cas de a = 1 qu'on dit habituellement que ç(a) désigne le nombre de nombres premiers à a et non supérieurs à a, ^(rt) est une fonction numérique de a, c'est-à-dire que la valeur de ?(«) est déterminée quand on se donne le nombre entier

positif a. i.^ .

Le calcul de la valeur de cette fonction repose sur l'important théorème

que voici.

Si a, 6, sont des nombres entiers, positifs, premiers entre eux, on a

ç(a6) = 9(fl) X m-

Cette proposition est évidente quand l'un des nombres a, 6 est égal à un; excluons donc ce cas. Si l'on considère un nombre plus petit que a6 il pourra se mettre sous la forme ax + y.V étant le reste de ce nombre (mod. a) et x étant un nombre entier moindre que 6; réciproquement, tous les nombres plus petits que ab s'obtiennent en remplaçant dans l'expression précédente x par 0, 1,2, ...,6-1 et y par 0,1,2,..., a- !. Les nombres ax -| y ainsi formés qui sont premiers à ah sont ceux qui sont premiers à a et à 6; ceux qui sont premiers à a sont ceux pour lesquels y est premier à a. Donnons à y une des ç(a) valeurs moindres que a et premières ii a, et remplaçons ensuite dans ax +.y,x par les nombres 0, 1, 2, ..., 6 - i, on obtiendra ainsi un système complet de nombres incongrus (mod. 6), puisque h est premier à a; parmi ces nombres il y en a 9(6) qui sont premiers à h comme dans la suite 0, 1, 2, ..., 6 — 4, car un nombre est premier à 6 en même temps que son reste (mod. 6). Chaque valeur de y première à a fournissant ainsi ç(6) nombres premiers à a6, il est clair qu'on a

^{ah) = ç{a) X ç(6).

Cette proposition se généralise immédiatement : si. a, 6, c, d, par exemple, sont des nombres entiers, positifs, premiers deux à deux, on a

^{abcd) = ç(a6c)ç(d) = 9(a6)ç(c)ç(d) = ç(a) 9(^)9 Wç(^-

528. Supposons maintenant qu'on se donne un nombre A décomposé en facteurs premiers

a, 6, c, ... étant des nombres premiers distincts; on aura

ç(a) = ç(a«) X ç(6^) Xç(ci^)x...,

et on est ramené à calculer des quantités telles que ç(a*), a étant premier. Tout d'abord, on a évidemment ^(a) = a — 1, puisque les nombres premiers à a et inférieurs à lui sont 1, 2, ..., a — 1. Les nombres premiers à a* et moindres que a* sont ceux des nombres

qui ne sont pas divisibles par a; les multiples de a qui sont contenus dans cette suite sont

leur nombre est o*"**; le nombre des termes de la suite 1,2, 3, ..., «• qui ne sont pas divisibles par a est donc o» — a»~' = a^^^{a — i); on a donc

ç(a«) = a^-^{a — l) et, par conséquent,

529. Soient 1, d, d', d'\ ..., A les diviseurs de A, diviseurs que Ton a appris à former au n" 165, on a

A := 9(1) + ç((i) + ?W + ... + ç(A), égalité que Ton écrit souvent sous la forme symbolique

A = ï9{rf) ;

le signe £ indique que le second membre est une somme de termes analogues à ç(d), et il est entendu que d doit être remplacé successivement par chacun des diviseurs de A, y compris 1 et A.

La vérification de ce théorème est très facile en partant de l'expression donnée au nM65 pour les diviseurs d'un nombre décomposé en facteurs premiers, et de l'expression précédente de la valeur de la fonction ç. En voici une démonstration purement arithmétique.

Le plus grand commun diviseur d'un nombre quelconque et de A est un des nombres l,rf,d', ..., A. Séparons les nombres 1,2, 3, ..., A en groupes; dans chaque groupe mettons ceux qui ont avec A un môme plus grand

commun diviseur, d par exemple. Tous ces nombres, si on les divise par

J, donneront des quotients premiers à -i, et non supérieurs à •-^; inver-

sèment tout nombre non supérieur à -^, premier à -5, si on le multiplie

par df acquiert avec A le plus grand commun diviseur d. Donc, il y a dans le groupe considéré ç( ^ ) nombres; donc ou a, en employant la notation précédemment expliquée,

étant entendu que d doit être remplacé successivement par tous les

diviseurs de A ; mais les nombres -r que Ton obtient ainsi ne sont autre

chose, dans leur ensemble, que les diviseurs de A; on peut donc écrire tout aussi bien

§ 7. — Des cong^raences à une Inconnue.

530. On a déjà traité des congruences à une inconnue, dans le cas où ces congruences étaient du premier degré, ou de la forme très spéciale

a?' = D (mod. p),

p étant un nombre premier.

Dans le cas général d*une congruence de la forme

/•(a;) = Aa?"4- Aia?""* + ... +A„ia?+ A„=hO (mod. m),

où A, A., ..., A ..A sont des nombres entiers, je me suis borné à définir ce qu*il fallait entendre par racine d'une telle congruence et par racines distinctes (n* 506). Le cas où le module m est un nombre premier offre un intérêt particulier et je vais bientôt m'y m'arréter. Mais il convient de dire quelques mots sur la façon dont les autres cas se ramènent àcelui-là. Supposons d'abord que le module m soit un produit de nombres entiers premiers deux à deux a, 6, c, ..., je vais montrer que l'on saura résoudre la congruence

(i) f(x) =0 (mod. m)

si Ton sait résoudre chacune des congruences

f{x) = 0 (mod. a),

(2) f{x) = 0 (mod. 6),

f(x) = 0 (mod. c),

Il est bien évident d'abord que chaque racine de la congnience (i) est une racine des congruences (2) ; car si pour une valeur entière de x, le nombre f{x) est divisible parm, il sera divisible par a, 6, c, ...; réciproquement, je vais montrer comment la connaissance de nombres a, p, y,... qui vérifient respectivement les congruences (2) entraîne la connaissance d'une racine de la congruence (1). Pour cela, je résoudrai le problème suivant:

531. Étant donnés les nombres entiers a, 6, c, ... premiers entre eux deux a deux, et les nombres entiers *, p,^, ..., trouver un nombre x qui soit congru à « suivant le module a, à p suivant le module 6, à ^ suivant le module c, etc..

En désignant par m, comme plus haut, le produit a6c..., cherchons d'abord des nombres A, B, C,... respectivement divisibles par les nombres

entiers-, ^, - , ... et congrus au nombre 1, suivant les modules respec-

tifs a, 6, c, .

congruences

il suffira de résoudre par rapport à A', B', C, ... les

(mod. a), (mod. 6), (mod. c),

ce qui est possible, puisque- =6c... est premier à fl, que -r-est premier à 6, etc.. ; on prendra ensuite

le nombre

To = A« + Bp + Cy + ...

satisfera aux conditions imposées : en effet, B, C, ... étant divisibles para, on a

a?o ^ Aot

(mod. a).

etc.. Tout autre nombre x satisfaisant aux mêmes conditions s'obtiendra en ajoutant à a?0 un multiple de m, puisque la différence x — x^^ doit être divisible par a, 6, c, ... et, par suite, par m. Cette méthode a cet avantage que le calcul des nombres A, B, C,... ne dépend pas de «, p, f» —i mais seulement de a, 6, c, ... .

532. Ceci posé, revenons à la première question : les nombres «, p, y. .-

DES CONGRUENCES A UNE INœNNUE. 41)1

étant respectivement des racines des congruences (2) et le nombre Xq étant pris comme on vient de l'expliquer, on a

A^o) = A») ^ 0 (mod. rt),

A^o) - AP) - 0 (mod. 6);

le nombre flx^) étant ainsi divisible par a, 6, c, ... est divisible par m: ainsi Xq est une racine de la congruence (1). On remarquera que tou( nombre x congru respectivement à «, p» y» ••• suivant les modules respectifs a, 6, c, ..., fournira la même racine que x^^, puisque ce nombre sera congru à Xq (mod. m). Inversement t§ute racine Xq de la congruence (i) fournissant un système de solutions (toutes égales àa?o) des congruences (2), on voit que le procédé précédent fournira certainement toutes les racines de la congruence (i), pourvu qu'on l'applique à tous les systèmes de nombres «> P> ïf ••• <l"i vérifient respectivement les congruences (2).

On observera que deux systèmes distincts «, p, y> •••» «'» P'» ï'> ••• ^^ solutions des congruences (2), c'est-à-dire tels qu'on n'ait pas à la fois

a ^ a' (mod. a),

p ^ p' (mod. 6',

Y = y (mod. c),

conduisent à deux solutions distinctes Xq^ x'^i on ù, en effet, par exemple,

Xo — iri ^ a — «' (mod. a) ;

si donc Xo — ^0 ^^a»* divisible par m, « — a' serait divisible para, de même P"— p' serait divisible par 6, etc ...; or nous venons de supposer qu'il n'en était pas ainsi.

On peut donc, en décomposant en facteurs premiers le modale m d'une congruence

f{x) = 0 (mod. w),

où f^x) est un polynôme entier en a? à coefficients entiers, ramener sa résolution à la résolution de congruences de la forme

f{x) ^^ 0 (mod. p**),

p étant un nombre premier.

533. Observons que toute racine de cette dernière congruence est une racine de la congruence

f{x) ^0 (mod. p'^-*).

Supposons qu'on sacbe résoudre cette dernière congruence; cbaque racine de la première congruence devra être congrue (mod. p" - *) à quelque

racine de la seconde; si donc on désigne par Xq une de ces dernières racines, on devra poser

y étant un nombre entier que Ton cherchera à déterminer par la congruencc

AiCo + P""V)-0 (mod.p«);

le lecteur un peu familier avec rAlgèbre reconnaîtra sans peine que la résolution de cette congruence se ramène en général à la résolution d'une congruence du premier degré.

Si donc on sait résoudre la congruence

f(x) = 0 (mod. p),

on saura résoudre la congruence

f{x) = 0 (mod. p«),

puis la congruence

f{x) — 0 (mod. p% etc.

Cette méthode, avec de légères modifications dans le cas où p est égal à 2, s'applique aux congruences de la forme

x» — D = 0 (mod. p"),

eu supposant que p soit un nombre premier qui ne divise pas D. Je me contenterai d'énoncer les résultais.

534. Si p est un nombre premier autre que 2, qui ne divise pas D, la condition nécessaire et suffisante pour que la congruence

a?» — D s 0 (mod. p*»)

soit possible, est que la congruence

«- — D = 0 (mod.p)

le soit-elle même. On reconnaît d'ailleurs directement que la congruence proposée ne peut avoir que deux racines incongrues (mod./)"). La congruence

jP»— D^O (mod. 2"),

où D est un nombre impair, admet pour solutions tous les nombres impairs, si n est égal à un ou à deux : elle admet donc une solution dans le premier cas, deux dans le second.

La congruence

x^ — D^O (mod. 8),

où D est an nombre impair, n'admet de solution que si D est con^u à un (mod. 8). Si cette dernière condition est vérifiée, la congruence admet quatre racines distinctes, savoir 1, 3, 5, 7. La congruence

a;« — D = 0 (mod. 2»),

où D est un nombre impair et n un nombre plus grand que 3, n'est possible que si Ton a D s i (mod. 8) (*).

Si cette condition est vérifiée, la congruence proposée a quatre racines distinctes.

D'après ces résultats partiels, il est aisé de reconnaître si la congruence

x' = D (mod. m),

où D est un nombre premier à m et où m est de la forme p^gV—» ou 2"p'gV**'> est possible ou non, et de calculer le nombre de ses solutions distinctes : p, 9» r, ... désignent des nombres premiers autres que 2.

§ 8. — Des congrruences à ane incoiinae. Cas où le modale est an nombre premier.

535. Arrivons maintenant aux congruences prises suivant un module premier p. Mais auparavant faisons quelques remarques générales sur les nombres congrus suivant un module premier p.

En général, quand on considère un module quelconque m premier ou non, les nombres congrus suivant ce module peuvent être regardés comme équivalents, en ce sens qu'ils peuvent se substituer les uns aux autres dans les opérations faites sur des nombres entiers, qui ne comportent que des additions, soustractions et multiplications, à condition, bien entendu, qu'on néglige dans les résultats les multiples de m. Cela revient à dire que les congruences, prises toujours suivant le même module m, peuvent être traitées comme des égalités. En ce sens, les multiples de m doivent être regardés comme équivalents à 0. Toutefois, lorsque m n'est pas premier, il s'introduit une différence capitale avec les théories ordinaires ; c'est que, en effet, un produit de facteurs peut être divisible par m sans que l'un des facteurs soit divisible par m. En d'autres termes, un produit peut être congru à 0 (mod. m) sans que l'un de ses facteurs soit congru à 0, tandis qu'un produit de nombres entiers ne peut être nul que si l'un de ses facteurs est nul.

Au contraire, lorsque le module est un nombre premier p, cette analogie

1. Cest dans co cas qu*il y a lieu do modifier la méthode générale; pour déduire une racine x de la congruence proposé© d'une racine j?o de la congruence a?» = D (mod. i^ v, on posera x = xt + *"~*y> «^ l'on cherchera à déterminer y de manière k satisfaire & la proposée.

subsiste. Si Ton convient de dire, en réservant essentiellement cette façon déparier au cas où le module est premier, d'un nombre congru à O(mod.p), qu'il est nul (*) (mod. p), on peut dire : Un produit de facteurs ne peut être iml (mod. p) sans que Tun de ses facteurs le soit. Dans le même ordre d'idées, en supposant toujours qu'il ne soit question que de congruences prises suivant le module premier p, il serait naturel de remplacer l'expression congrus (mod. p) par l'expression égaux (mod. p). Je conserverai toutefois le mode de langage habituel. En ce sens il n'y aurait que p nombres distincts, savoir 0, 1,2, ...,p— 1, tous les autres étant congrus (mod. p) à ceux-là.

536. Étant donnés deux nombres a, b dont le second n'est pas nul (mod. p), il y a un nombre et un seul, si Ton néglige toujours les mulliples de p, qui :'érifie la congruence

bx --a (mod. p).

Il serait naturel, ainsi que Gauss l'a proposé, de regarder ce nombre comnx^ le quotient (mod. p) de a par 6 et de le représenterpar le symbole -r (mod. p;. Seule, la division par le nombre 0 demeure impossible. Ces fractions symboliques -r (mod. p), qui représentent en réalité des nombres entiers,

pourraient être soumises à des règles de calcul pareilles à celles des fractions ordinaires : on pourrait multiplier leurs deux termes par uu même nombre non nul (mod. p), etc..

637. Dans le môme ordre d'idées, il est naturel d'appeler identiquement congru à zéro (mod. p) un polynôme dont les coefficients sont nuls (mod. p), c'est-à-dire tout polynôme qui peut élre mis sous la forme p'Kx), ^x) étant un polynôme entier eux à coefficients entiers. Deux polynômes à coefficients entiers seront identiquement congrus (mod. p) si leur différence est un polynôme identiquement congru à zéro. On reconnaît de suite que, si on fait des opérations d'addition, de soustraction, de multiplication sur divers polynômes à coefficients entiers, on peut remplacer dans ces opérations ces polynômes par d'autres polynômes qui leur soient identiquement congrus (mod.p). Les deux séries d'opérations fourniront deux polynômes identiquement congrus (mod. p). Si dans un polynôme entier en x, à coefficients entiers, on appelle terme du plus haut degré le terme du plus haut degré dans ce polynôme dont le coefficient ne soit pas nul (mod. p), si Ton définit de môme le terme du plus bas degré, on reconnaît de suite que dans le produit de deux polynômes entiers en ar, à coefficients entiers, les coefficients des termes de plus haut degré et de plus bas degré sont respectivement congrus (mod. p) aux produits des coefficients des termes du plus haut degré d'une part, et des termes du plus bas degré de l'autre, en sorte que

1 . Je dois à M. Borel cotte expresuion, ainsi que la forme donnée à quelques-unes des idées qui sont exposées ici.

le produit ne sera certainement pas identiquement congru à zéro, si Tun des deux facteurs n'est pas lui-même identiquement congru à zéro. Ce théorème 9*étend immédiatement au produit d'autant de polynômes qu'on voudi^a. On voit aussi qu'en appelant degré d'un polynôme le degré du terme le plus élevé défini comme plus baut, on peut dire que le degré du produit de deux polynômes entiers en x est égal à la somme des degrés des deux facteurs. Enfin étant donnés deux polynômes entiers en X, f[x) ei^ (x), on dira que f[x) est divisible (mod. p) par ^{x) s'il existe un polynôme Q{x) entier en x, tel que le polynôme f[x) soit identiquement congru au produit des polynômes 4'(x), Q(a:). Le lecteur qui connaît la théorie du plus grand commun diviseur algébrique reconnaîtra sans peine que cette théorie s'étend, ainsi que ses conséquences les plus importantes, à la divisibilité (mod. p). Je laisserai de côté ce sujet, malgré son importance, pour m'arrèter sur quelques résultats d'ordre plus élémentaire.

538. Si un polynôme f{x) entier en x devient nul (mod. p) quand on y remplace x par le nombre entier «, c'est-à-dire si f{a) est divisible par p, le polynôme f(x) est divisible (mod. p) par x — a.

En effet f{x) — f{a) est algébriquement divisible par [x — a) et le quotient est un polynôme à coefficients entiers ^(x)\ on a donc identiquement

mais, f[a) étant, par hypothèse, un nombre divisible par p, la proposition est évidente.

Réciproquement, il est clair que, si le polynôme f{x) est divisible (mod. p) par X — a, a étant un nombre entier, le résultat de la substitution de a à X dans f[x) est nul (mod. p).

539. Si, a, 6, c, ... étant des nombres entiers dont deux quelconques ne sont pas congrus (mod. p), le polynôme f{x)y entier en a?, est divisible (mod. p) par x — a, par x — 6, par x — c, ..., il est divisible (mod. p) par le produit [x — a){x — b){x — c)... .

En effet f(x) étant divisible (mod. p) par a? — a, on peut écrire identiquement

r[x) = [x — à)U[x) -^ pk^y

A, étant un nombre entier et f^[x) un polynôme entier en x à coefficients entiers; en remplaçant dans le résultat x par 6, on obtient, puisque ^(6) esf divisible par p,

(6- rt)A(6) ^0 (raod.p);

puisque 6 — a n'est pas nul (mod. p), on a donc

f^[h) :^ 0 (mod. p) :

on en conclut que ^(x) est divisible (mod. p) par a? — 6, de même par x — c, etc.; ou peut donc écrire identiquement

f^[x) = {x- b)yx) + pA.,,

Aj étant encore un nombre entier et f^(x) un polynôme entier en a?, à coefficients entiers ; en remplaçant dans (x — «(/i{x) + pA,, /;{«) par cette valeur, on en conclut qu'on peut écrire identiquement

ii(x) étant un polynôme entier en x du premier degré, à coefficients entiers. En remplaçant dans cette identité x par c, on en conclut, puisque f(c) est divisible par p,

0 =; (c — a)(c — by^ic) (mod. p);

comme aucun des nombres c — a, c — 5 n*est nul (mod.p), on en conclut que fi{c) est nul (mod. p), ou, si l'on veut, que f^{x) est divisible (mod. p) par X — c. Le raisonnement se continue; on pourra, dans Tidentité

fix) = (x - a)(aî - 6)A(x) + pU^),

remplacer f^x) par un polynôme de la forme (x — c)f^(x) + pA„ f^(x) ayant encore ses coefficients entiers et A, étant un nombre entier; on obtiendra une identité de la forme

flx) = (a? — a)(x — b){x — c)f^{x) + p+,(a?),

où ^^{x) est un polynôme entier en a?, à coefficients entiers, du second degré, et cette identité montre bien que le polynôme f(x) est divisible (mod.p) par (a? — a}{x — b){x — c). En général s'il y a r nombres a, 6, c, ... , on mettra f (x) sous la forme.

fj^x) étant un polynôme entier en a?, dont le degré est n — r si le degré du polynôme f[x) est w, et dans lequel le coefficient de la plus haute puissance de x est le même que dans /*(a?), ainsi qu'il résulte de la théorie de la division algébrique. Quand à ♦^i(aî), c'est un polynôme entier en x de degré r — 1 .

540. Il résulte de là qu'un polynôme du degré n ne peut pas s'annuler (mod. p) pour plus de n valeurs de la variable, incongrues deux à deux (mod. p).

Si, en eiîet, dans l'identité précédente, on suppose que les nombres a, 6, c, ..., /, incongrus deux à deux, soient en nombre n, on peut écrire identiquement, en désignant par K le coefficient de x" dans f{x)

/(x) = K(x — a)(x — 6)(x— c)...(x — /)+p4.„j(x), ♦n-i étant un polynôme à coefficients entiers : si f[x) pouvait s'annuler

(mod. p) pour un nombre entier a?o incongru (mod. p) à a, 6, ..., /, on voit, en faisant x = x^ dans Tidentité précédente, qu'on aurait

K(a?o — a) {Xq — b) (xq — c) ... (^o — /) s 0 (mod. p),

ce qui est impossible.

Ainsi, une congruence du degré n à une inconnue

f{x) = 0 (mod. p),

c'est-à-dire une congruence dans laquelle le premier membre f{x) est un polynôme entier en x de degré égal à n, ne peut avoir plus de n racines distinctes. Si elle admet n racines distinctes et que Ton connaisse ces n racines, on pourra mettre le premier membre sous une forme spéciale, comme on Ta vu au numéro précédent.

541. Il est clair qu'on obtient une congruence équivalente à la proposée en remplaçant son premier membre par un polynôme qui lui soit identiquement congru (mod. p). Supposons en particulier que ce premier membre soit identiquement congru (mod. p) au produit de deux polynômes ^{x), 6(jp) entiers en or, on aura, quel que soit le nombre entier a:',

f[^')=^*{^)^{x') (mod.p);

d'ailleurs, pour que le nombre entier f{x') soit nul (mod. p), il faut et il suffit que Tun des nombres entiers ^{x'), 6(a?0 soit nul (mod. p); on en conclut que les racines de la congruence

(i) m^O (mod.p)

sont les mômes que les racines, prises dans leur ensemble, des con« grueuces

tW = 0 (mod. p), ^ ^ 0(jr) — 0 (mod. p).

Si, en particulier, f{x) est de degré égal à n et si la congruence (1) a n racines distinctes, la somme des degrés des polynômes ^{x)y 0(x) sera égale a n ; donc chacune des congruences (2) aura exactement autant de racines distinctes qu'il y a d'unités dans son degré.

Par exemple, la congruence

.rP-* — i = 0 (mod.p)

a p — 1 racines distinctes, d'après le théorème de Fermât, à savoir les nombres 1, 2, ..., p — i ; on a d'ailleurs identiquement, en supposant P>2,

xP-'— 1= (oj 2 — i){x ^ +1); donc les congruences

(mod. p),

(mod. p)

Tannrrt. 32

ont chacune" racines distinctes; c'est ce qu'on savait déjà; les ^-5 —

racines de la première sont les restes quadratiques de p, les ^—- — racines

de la seconde sont les non-restes.

Donnons maintenant une application du théorème du n* 539. La congruence de degré p — 1

x^ " * — i =0 (mod. p)

admet p — 1 racines distinctes, par exemple les nombres 1, 2, ... , p — i ; il en résulte que le polynôme a^"* — 1 est divisible (mod. p) par le produit (x — i){x — 2).,.(x — p + 1), et comme le coefficient de la plus haute puissance de x est un, on peut écrire identiquement

a* - » - 1 = (X - 1 ) (a: - 2) . . . (X - p + 1 ) + p^ix), ^(x) étant uu polynôme entier en x, à coefficients entiers; il en résulte que tous les coefficients du polynôme

sont divisibles par p; en d'autres termes, si Ton veut, ce polynôme est identiquement congru à zéro (mod. p). Le terme indépendant de a?, en particulier, est — 1 — i.2...(p — i); on a donc