DES CONGRUENCES

1. Si la différence des deux nombres a et b est divisible par un nombre M, a et b sont dits congrus par rapport à M; le diviseur M est appelé le module; a et b sont résidus l’un de l’autre suivant le module M. Pour exprimer cette relation, on écrit, d’apres la notation de Gauss,

a = b (mod M);

cette formule est une congruence. Il y a avantage, dans cette théorie, à admettre, pour a et b, non seulement les valeurs entières positives, mais aussi les valeurs entières négatives.

Si r est le reste de la division de a par M,on a

a="r (mod M); le reste r est ordinairement un des nombres

CE PE PS VE à . . . M M ee. a. + mais on pourrait le prendre aussi entre — og t+S: d'où il suit que tout nombre a un résidu qui ne surpasse pas en valeur absolue la moitié du module. C’est là le résidu minimum.

2. Nous allons indiquer ici les propriétés les plus élémentaires des congruences, il sera à peine nécessaire d’insister sur les démonstrations. Si l’on n'indique pas le module, il sera sous-entendu que ce module est toujours M.

Si l’on a

a =, a =, a” =b"’, RER on aura ainsi a+a+a'+...=b+b+b'+..., ma—=m b.

De même, on aura

aa’ —ba —bb

et plus généralement au"... =000 ..., a” = b", Ainsi fa,y,2,.:.)= D Amnp. TM Y"2P. “4 étant un polynôme à coefficients entiers, on aura

f{a, a’, a,...)=f(, db’, b”,...).

3. Supposons qu'on ait ma—=mb (mod M), ce qui signifie que m (a — b) est divisible par M; soit (m, M)=d,

ae— b) sera divisible par ga’ °t; puisque 7 et 7 sont premiers entre nn M

eux, a — b sera divisible par = : donc

ie M a = (mod a)

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

aa’ —bb (mod M), a = b (mod M).

En multipliant la seconde congruence par 4’, il vient, en faisant attention à la première, ba’ =bb! (mod M),

a’ =D (mod a)

où d—=(b, 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

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+ Mx,x—0,+1,+2,+38,.... 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

FRANS RO ee.

des nombres qui sont premiers avec M. Nous désignerons ce nombre par (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

Or, pour que (kd, M) = d, il faut et il suffit que & soit premier avec:

Le nombre cherché indique donc combien, parmi les nombres

à , F M ; M il y en a qui sont premiers avec +, c est-à-dire ce nombre est y a)

Il y a ainsi ) classes qui ont d pour p. g. c d. avec M, le nombre

total des classes étant M, on a

Eo()=x

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 y (M).

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

M éme, cuir Re > (0),

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

Soit

M=p"qlr...u?

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

Mt Hate + (Hotte (Ent i)

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

1 1 1 1 1 1 M(14+2 ++ (+) fl + ++) 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

ne 0. 1 1 1 1 1 \| —)= +, +++... +). (+4 +...+—)!:

F()=r us + Het +) (+++) En retranchant, il vient, si l’on fait usage dans le premier membre de

la même notation symbolique

FH =r

morte +

M 1. : x En remplaçant M par F + retranchant, il vient ensuite

pis

En continuant ainsi, on obtient finalement

af D(1-3} (3 ren

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

(2) . ra=ran— YF (5)+ pr-Er (+.

=" (+++). (1 +itet à)