Lemhe. — Si l'on multiplie les termes de la suite

par un entier a premier avec M, les produits obtenus

{2) «, 2^, 3fl, ..., (M — \]a

10 COURS d'algèbeb supérieure.

seront respeciwement congrus, suwant le module M, aux nombres (i), abstraction faite de l'ordre.

En effet, Tun des nombres (a), ma par exemple, ne saurait être divisible par M, puisque M est premier avec a et quMI est supérieur à m ; la même chose a lieu, à Tégard de la différence ma — m'a de deux termes de la suite (a), car cette différence est aussi un terme de la même suite.

11 résulte de laque, si Ton prend les résidus minima positifs des nombres (i), par rapport à M, ces résidus seront tous différents et aucun d'eux ne sera nul ; ce seront donc, dans un certain ordre, les nombres de la suite (i).

Corollaire, — Si le nombre M est premier à a, les termes de la progression arithmétique

sont respectiv^ement congrus, suis/ant le module M, quel que soit l'entier c, aux nombres

En effet, d'après le lemme précédent, les nombres (i) sont respectivement congrus à

r, c-4-1, cH-2, ..., c -h . M — i),

et il est évident que ces derniers sont congrus aux nombres (a), suivant le module M.

284. Nous emploierons le symbole 9 (M) pour désigner combien il y a de nombres premiers à M et non supérieurs kM, D'après cette déGnition, on a évidemment

TfléoRkME. — «Si M désigne le produit de plusieurs nombres a, b, ...^ l, premiers entre eux deux à deux,

on aura

SBCnolf III. CHAPITHB I. II

Prenons d'abord le cas de deux facteurs et soit

a et b désignant des nombres premiers entre eux. Les ab premiers nombres peuvent être disposés comme il suit :

(a— l)^H-i, (a— i)6h-2, ..., [a—i)b-\-^,.,., (a— i)ftH-A.

Considérons Tune des colonnes verticales de ce tableau, par exemple celle qui commence par Ar. Si k est premier avec by il en sera de même de tous les autres termes de la colonne ; au contraire, si k et b ont un diviseur commun autre que i, il n'y aura dans la colonne aucun nombre premier avec b. D'ailleurs, la première ligne du tableau renferme f(i) nombres premiers avec b; donc le tableau entier renferme 9 (£ ) colonnes verticales dont tous les termes sont premiers à by et qui épuisent tous les nombres de celte espèce non supérieurs à M. Supposons que k soit premier avec b ; la colonne verticale qui commence par k est une progression arithmétique dont les termes sont respectivement congrus, suivant le module a, aux nombres o, 1, 2, ..., {a — i); cette dernière suite contient f (a) nombres premiers à a, et, par conséquent, la colonne que nous considérons en renferme un pareil nombre. De tout cela il résulte que notre tableau renferme y(a)x9(i) nombres premiers à a et à &, c'est-à-dire premiers au produit ab ; on a donc

Passons maintenant au cas général où l'on a

M = abc. . . /,

la COTJRS d'algèbre supérieure.

a, i, Cy,.,, l étant des nombres premiers entre eux, deux à deux. On aura successivement

ce qui achève la démonstration du théorème énoncé.

285. Le théorème précédent fournit un moyen trèssimple de trouver la valeur de 9 (M).

Lorsque M est égal à un nombre premier />, il est évident que les nombres premiers à M = ^, et non supérieurs à oe nombre, sont

on a donc

Lorsque M est égal à une puissance p* d'un nombre premier /7, il est évident que la suite des p^* nombres

renferme tous les nombres non supérieurs à M qui admettent p pour diviseur; on a donc

9(M) =/>^ — /i^-> =:--/7^-» (/? - i), ou

Considérons le cas général; soient/?, y, r, ... les facteurs premiers inégaux de M, et supposons

SECTION JII. CHAPITRE I. ta

yfyHyXj... étant des exposants entiers. On aura (n** 284)

9W = ?{p']?(gnf[^)^"'^

d'ailleurs

donc

Il importe de remarquer que, si M est un nombre impair, on a

or cp(2)=^ I : donc

286. Il convient de remarquer encore le théorème suivant, qui nous sera très-utile dans la suite :

Théorème. — Si r/, rf', d'\ ... désignent la suite des diviseurs du nombre M, parmi lesquels figurent l'unité et le nombre M lui-même, on a

En effet, soit

p, y, r,... étant des nombres premiers inégaux; les diviseurs dj d'y d"j ... ne seront autre chose que les

I4 COURS d'algèbre SI^PÉRIEtTRB.

termes du polynôme égal au produit

L*un quelconque des termes du polynôme dont il s'agit a la forme p* q' r^. . .; d*ailleurs Tégalité

entraîne

f(d) = f{p*)f{q')f{rl)...;

donc la somme de toutes les quantités <^{d) sera le pro^ duit des polynômes

I -*- ? (7 ■ -^ ?(7*) H-- • • -♦- ?(9'')» l-hf{r) H-y[r«)-4-...H-y(r^),

Le premier de ces polynômes a pour valeur

i'-h{p-i][i-hp'hp*-h...-i'p^') = p%

et Ton voit de même que les polynômes suivants ont res* pectivement pour valeurs y»*, r^, . . . ; on a donc

f {d) -h f (d') -i- f [d") -h . . .=p^q^ r^ . , ,z=TA.

Des congruences en général.

287. La théorie des nombres résout sur les congruences le même problème que TAlgèbre ordinaire sur les équations; elle se propose, en particulier, de trouver les valeurs de x qui satisfont à une congruence telle que

/{jr)^=io (mod.Mj,

où^(x) désigne un polynôme entier et rationnel dont les coefficients sont des nombres entiers. Si Ton satis-

SECTION m. — châpithe i. i5

fait à cette congruence, en faisant x = a, on y satisfera

aussi y d'après une remarque précédente, en faisant, quel

que soit l'entier Ar, x = a -h kM; d'où il suit que chaque

solution en donne une infinité d'autres, mais qui sont

toutes équivalentes suivant le module M. Les diverses

solutions renfermées dans une même formule a + ArM

peuvent se déduire de l'une quelconque d'entre elles;

d'ailleurs, on peut disposer de l'entier Ar de manière que

« -.. . M M a-hkal soit compris entre — - et H > ou entre o

et M ; il n'y a donc lieu de s'occuper que des solutions comprises entre ces limites.

Cela posé, nous appellerons racines de la congruence

f{x) =:ho (mod. M^

les diverses valeurs de x comprises entre o et M, qui rendenty(x) divisible par M.

Une congruence est identique lorsque tous ses coefficients sont divisibles par le module, et elle est évidemment impossible lorsque ses coefficients sont divisibles par l'un des facteurs du module, à l'exception du terme indépendant de x.

Si F (j:) désigne un polynôme entier et rationnel, ayant pour coefficients des nombres entiers, on peut substituer à la congruence

/(a:)^o (mod. M) la congruence équivalente

/(x) -HMF(ar)=o (mod.M), et disposer ensuite des coefficients indéterminés de F(x), pour rabaisser au-dessous de M, et même de — si l'on veut, tous les coefficients de la congruence.

i6 CODAS d'algèbre svpérievee.

Des congruences du premier degré.