NOMBRES PREMIERS A UN NOMBRE DONNÉ

quadratique, et ceux-là seuls. En particulier, les diviseurs premiers impairs de la forme æ? + y? sont les nombres premiers de la forme 4n + 1, les diviseurs premiers impairs de la forme x? — 37? sont les nombres premiers . de la forme 12n +1.

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

527. Nous ayons 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 « n’est pas un, se désigne par le symbole g(a). Si a est égal à un, (a) — (1) est par définition égal à 4. C'est pour embrasser le cas de a — 1 qu'on dit habituellement que œ(a) désigne le nombre de nombres premiers à & et non supérieurs à 4. (a) est une fonction numérique de «, c’est-à-dire que la valeur de (a) est déterminée quand on se donné le nombre entier positif «a.

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

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

p(ab) = œ(a) X pb).

Cette proposition est évidente quand l’un des nombres 14, b est égal à 1; excluons donc ce cas. Si l’on considère un nombre plus petit que ab, il pourra se mettre sous la forme ax + y, y étant le reste de ce nombre (mod. a) et æ étant un nombre entier moindre que b; réciproquement, tous les nombres plus petits que ab s’obtiennent en remplaçant dans l'expression précédente æ par 0,1,2, .…,b—1 et par 0,1,2,...,a—1. Les nombres ax + y ainsi formés qui sont premiers à ab sont ceux qui sont premiers à a et à b; 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 à a, et remplaçons ensuite dans ax + y, x par les nombres 0, 1, 2, …, b — 1, on obtiendra ainsi un système complet de nombres incongrus (mod. b), puisque b est premier à a; parmi ces nombres il y en a @(b) qui sont premiers à b comme dans la suite 0,1, 2, .….,b—1,car un nombre est premier à b en même temps que son reste (mod, b). Chaque valeur de y première à a fournissant ainsi +(b) nombres premiers à ab, il est clair qu'on a

p(ab) — œ(a) X (b).

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

glabcd) = glabc)e(d) — glab)e(c)p(d) = ea) #(ble(c)e(d).

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

À = dbrors.

a, b,e,.… étant des nombres premiers distincts ; on aura

g(A) = pla”) xX e(bt) x gler) x …,

et on est ramené à calculer des quantités telles que la“), a étant premiei. Tout d'abord, on a évidemment œ@(a) — a — 1, puisque les nombres Presses à aet inférieurs à lui sont 1, 2, ..…., a — 1. Les nombres premiers à a* et moindres que a“ sont ceux des mo

qui ne sont pas divisibles par a; les multiples de a qui sont contenus dans cette suite sont M, 00, 14, 20 06 mind,

leur nombre est a*—!; le nombre des termes de la suite 1, 2, 3, …, a* qui ne sont pas divisibles par a est donc a% — a%—1 — g®—l{(a — 1); on a donc

| g(a®) = a*T {a — 1) et, par conséquent,

A) = af te ter La "1h = Di pe

= (he CD

529. Soient 1, d, d’, d'', …, À les diviseurs de À, diviseurs que l'on a appris à former au n° 144, on à

A = q(1) + g(d) + &(d') + … + (A), égalité que l’on écrit souvent sous la forme symbolique À — xe(d);

le signe x 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. 2 La vérification de ce théorème est très facile en partant de l'expression. donnée au n° 144 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 JA et de A est un des sobres d. d, d', .…, À. Séparons les nombres 1,2, 3, …, À en groupes; dans chaque groupe mettons ceux qui ont avec À un même plus grand

DES CONGRUENCES A UNE INCONNUE. | 52% commun diviseur, d par exemple. Tous ces nombres, si on les divise par

’ A A d, donneront des quotients premiers à a et non supérieurs à —; inver-

ie ,; À A pe sement tout nombre non supérieur à nr. premier à —, si on le multiplie par d, acquiert avec A le plus grand commun diviseur d. Donc, 1l y à dans

ER NES le groupe considéré g(-— } nombres; donc on a, en employant la notation

précédemment expliquée,

étant entendu que d doit être remplacé successivement par tous les A d chose, dans leur ensemble, que les diviseurs de A; on peut donc écrire tout aussi bien

diviseurs de À ; mais les nombres — que l’on obtient ainsi ne sont autre

À = Ed).

& 7. — Des congruences à 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

x? =D (mod. p),

p étant un nombre premier. Dans le cas général d’une congruence de la forme

fa)= Ac" + Am" ++ A; ;m+ A,=0 (mod. m),

où A, A4, ……, À,,, À, 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 Ja 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 4, b, c, …, je vais montrer que l’on saura résoudre

a congruence (1) f(x) = 0 (mod. m)

si l’on sait résoudre chacune des congruences

Il est bien évident d’abord que chaque racine de la congruence (1) est une racine des congruences (2); car si pour une valeur entière de æ, le. nombre f(x) est divisible par m, il sera divisible par à, b, c, ..….; réciproque-. ment, je vais montrer comment la connaissance de nombres &, f, y... qui vérifient respectivement les congruences (2) entraine 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, b, c, .… premiers entre eux deux A à deux, et les nombres entiers æ, B,y, …, trouver un nombre æ qui soit congru à x suivant le module a, à g suivant le module 6, à + suivant lé module ce, etc... 7500

En dia par m, comme plus haut, le prodais He D rehou . d’abord des nombres À, B, C,... respectivement divisibles par les nombres kb

entiers % . ne et congrus au nombre 4, suivant les modules respec- " tifs :@ bc, ...5 il suffira de résoudre par rapport à À, B, CE les ; congruences AI ET | (mod. a), : | FB=1 (mod.b), | TC=1 (mode),

m à ce qu est possible, puisque = — = bis lest premier à a, que

rs est premier

à b, etc... ; on prendra ensuite