Supposons qu'on ait

ma^mb (mod M),

ce qui signifie que m {a — b) est divisible par M; soit

-^ [a — b) sera divisible par ^, et, puisque ^ et ^ sont premiers entre

eux, a — b sera divisible par -r : donc

a = 6 (mod — ]•

On peut donc diviser les deux membres d'une congruence par un nombre m, à condition de diviser en même temps le module par le p. g. c. d. de m et M. On aura à appliquer cette proposition le plus souvent dans les cas particuliers suivants: 1° m est premier avec M, alors d = 1 ; 2^ m divise M , alors d = m. Supposons encore qu'on ait

oo' = 66' (mod M), a = & (mod M).

En multipliant la seconde congruence par a', il vient , en faisant attention à la première ,

ba' = bb' (mod M), donc

Ud^^

V dV

où d = (6, M) = (a, M), car il est clair que des nombres congrus ont même p. g. c. d. avec le module.

Si deux nombres sont congrus suivant le module M, ils seront congrus encore en prenant pour module un diviseur de M. Si deux nombres sont congrus suivant plusieurs modules A, B, C, . . . , L, ils seront congrus encore en prenant pour module le p. p. c. m. de ces nombres

M = l A,B,C, ....Lj.

Le cas particulier le plus intéressant est celui où les modules A, B, C, . . . , L sont premiers entre eux , alors M = ABC ... L.

4. On peut distribuer l'ensemble des nombres entiers en M classes , en considérant deux nombres comme appartenant à la même classe ou non , selon qu'ils sont congrus ou non suivant le module M. En prenant dans chaque classe un nombre , on obtient un groupe de M nombres , qu'on appelle un système complet de résidus. Un tel système jouit évidemment de la propriété qu'un nombre quelconque est congru à un et à un seul de ses nombres. Un nombre quelconque a pris dans une classe peut être considéré comme représentant la classe entière qui se

compose des nombres a + Ma;, a; = 0,±l,±2,±3, On désigne

ainsi souvent la classe par un quelconque des nombres qu'il renferme, et l'on peut ainsi remplacer un nombre par un nombre congru.

Tous les nombres d'une classe ont le même p. g. c. d. avec le module M, et ce p. g, c. d. peut être un diviseur quelconque d de M.

On peut , d'après cela , distribuer les classes en familles , en considérant diverses classes comme appartenant à une même famille , si elles ont le même p. g. c. d. avec le module M.

Combien de classes y a-t-il qui sont premières avec M? Il est clair qu'il y en a autant q'on trouve parmi les nombres

des nombres qui sont premiers avec M. Nous désignerons ce nombre par (p (M) , en sorte que

Le nombre des classes qui ont avec M le p. g. c. d. d est évidemment

le même que celui des nombres du groupe (A) qui ont d pour p. g. c d. avec M. Il faudra donc les chercher parmi les nombres

d, 2d, 3d, ..., kd, ..., ^ d.

Or, pour que (Ad, M) = d, il faut et il suffit que k soit premier avec-j- Le nombre cherché indique donc combien , parmi les nombres

il y en a qui sont premiers avec -^ , c'est-à-dire ce nombre est ç» (^)-

Il y a ainsi (p (^j classes qui ont d pour p. g. c d. avec M, le nombre total des classes étant M, on a

d parcourant tous les diviseurs de M. Il est clair qu'on peut écrire cette relation plus simplement ainsi

Il est facile de déduire de là la valeur de cp (M).

5. Supposons généralement que deux fonctions numériques /" et F soient liées par la relation

(i) F(u)=^nd),

d parcourant tous les diviseurs de M. Nous allons exprimer réciproquement la fonction /"au moyen de F.

Soit

la décomposition de M en facteurs premiers. On obtient l'ensemble des diviseurs d de M en développant le produit

et nous pouvons écrire d'une manière symbolique

On doit développer le produit du second membre et remplacer ensuite chaque terme d par f(d). En remplaçant M par M :p (donc a par a — 1) , on aura

En retranchant, il vient, si l'on fait usage dans le premier membre de la même notation symbolique

M En remplaçant M par — et retranchant , il vient ensuite

('-j)('4)l=^K'+.-+-+fJ-('+s+-+„^)l

En continuant ainsi , on obtient finalement

c'est l'expression cherchée ; on peut l'écrire plus explicitement

On rencontre souvent des fonctions numériques qui jouissent de la propriété

(3) f(ab)=f(a)xnb)

lorsque a et 6 sont premiers entre eux (voir Chap. I, n" 14). Il est clair qu'une telle fonction est parfaitement déterminée lorsqu'on connaît sa valeur pour les puissances des nombres premiers , mais ces valeurs-là peuvent être prises arbitrairement.

On voit facilement que, si la fonction /"qui figure dans la relation (1) jouit de cette propriété (3), on aura aussi, a et 6 étant premiers entre eux.

F(o6) = F(a)XF(6),

et l'on reconnaît maintenant par les formules (2) ou (2') que, réciproquement, si deux fonctions /" et F sont liées par la relation (l), et si la fonction F satisfait à la relation (4), la fonction /"satisfera à la relation analogue (3).

Le théorème, souvent utile, de ce numéro est dû à M, Dedekind (Journal de Crelle, t. 54, p. 21). On l'établit ordinairement par une simple vérification. En exprimant au second membre de (2') partout la fonction F par la fonction /", on constate qu'il ne reste que le terme /■(M) : tous les autres termes se détruisent.

6. En revenant au cas particulier de la fonction (p(M), F(M) = M, on trouve

<p OJL) = p"-^ q^-K . . u^-Up — l) iq — l) ■ ■ • (u — 1).

Ayant q}(ab) = q>(a) (p(b) lorsque a et 6 sont premiers entre eux, on peut remarquer que , a étant impair , on a , à cause de ç? (2) = 1 ,

gp (2 a) = g? (a).

A l'exception de ç» (1) = 99 (2) = 1 , q> (a) est toujours pair.

7. Dans la théorie des nombres , on se propose , sur les congruences, des problèmes analogues à ceux qu'on traite en Algèbre sur les équations.

Ainsi on pose la question de trouver les nombres x qui satisfont à une congruence , telle que

f{x) = 0 (modM), où le premier membre est un polynôme à coefficients entiers en x.

Si l'on satisfait à cette congruence en faisant x = Xq, Xq est une racine de la congruence. Il est clair que tout nombre congru à Xq suivant le module M satisfera alors aussi à la congruence , mais on a l'habitude de ne pas considérer comme différentes ces solutions. Aussi, si l'on dit qu'une congruence admet k racines, cela veut dire k racines incongrues, ou encore, ce qui revient au même, l'ensemble des nombres qui satisfont à la congruence se répartit en k classes. Il est clair , n 19

d'après cela, qu'on obtient toutes les racines d'une congruence, en essayant successivement tous les nombres d'un système complet de ré sidus, par exemple les nombres

0, 1, 2, ..., M-1, maïs ce moyen devient impraticable dès que M est un peu grand. Si tous les coefficients du polynôme f{x) sont divisibles par M, la congruence est identique, un nombre quelconque y satisfait. La congruence est impossible évidemment lorsque tous les coefficients de f{x) sont divisibles par M, à l'exception du terme indépendant de x.

Il est clair, du reste, qu'il est permis de remplacer un coefficient quelconque de f{,x) par un nombre congru suivant le module M.