DES CONGRUENCES

§ I. — Premières notions sur les congruences.

98. La notion de congruence, ou plutôt la notation par congruences et leur analogie avec les équations, est due à Gauss. Voici en quoi elle consiste :

On dit que deu\ nombres a et b sont congrus par rapport à un module n quand la différence a — b est divisible par n. Cette congruence s'indique de la façon suivante :

a~b (mod n).

Lorsqu'il nj a pas d'ambiguïté à craindre, on peut supprimer

le module et écrire

Il y a, entre les congruences et les égalités, des analogies dont nous allons parler et qui sont mises en lumière par la notation précédente.

99. On peut ajouter, soustraire, multiplier membres à membres des congruences prises par rapport à un même module.

Soient, par exemple, les congruences

a t> t m imI n i,

il I)' { IllOll II).

Elles sont équivalentes aux égalités

a' — b' ■+■ nh',

h et h' étant des nombres entiers.

54 < Il vl*. III. — DES CONGRUENCES.

\joutons ces égalités, nous obtenons

fl + o'=i + J'+n(A+ h' i.

a -+- a' b ■ b' (mod n).

La démonstration s'étendrait au cas d'un nombre quelconque de congruences.

( )n \iiii d'i façon analogue que l'on peut soustraire membres

à membres deux congruences.

On peut aussi multiplier deux congruences membres à membres. En effet, des égalités (i) et (2) on lire

an' — bb' -+■ n(/ib' -r- h' b H- nhk').

Donc aussi

an' l)l>' ( mod // ).

Ce théorème s'étend sans peine, de proche en proche, à un nombre quelconque de congruences. En particulier, on peut élever les deux membres d'une congruence à une même-puissance.

100. Si l'on combine entre eux. les résultats précédents, on arrive sans peine à l'énoncé général suivant :

Si Von a

<i n' (mod n),

h = b' (mod n),

c = c' (mod // 1.

on a aussi

fia, b,C, ... 1 /(«', //. c', ...),

f étant une fonction rationnelle entière à coefficients entiers.

101. On ne peut pas. en général, diviser les deux membres d'une congruence par un même nombre. I l'abord, cette opération n'a de sens que si les deux membres sont divisibles par le diviseur en question; ensuite, cette condition étant réalisée, l'opération n'esl permise que si le diviseur est premier avec le module.

En effet, soit

a b (mod n),

d'où

(3) '/ — i^o ( mod n .

PREMIERES NOTIONS SUR LES CONGRUENCES. 5j

Soit d un diviseur commun à a et b, et par suite diviseur

de a — b, et soit

a — b = dd' .

Diviser les deux membres de la congruence (3) par d revient à écrire la congruence d' = o (mod n). Or, de ce que n divise dd', on n'a le droit d'en conclure qu'il divise d' que s'il est premier avec d.

Si, après avoir divisé les deux membres d'une congruence de module n par un même nombre <:/, on veut encore obtenir une congruence sûrement exacte, il faut diviser le module n par le plus grand commun diviseur de n et de d.

Exemple. — Soit la congruence

270 =h 60 (mod 14).

On peut diviser les deux membres par io, parce que ia est premier avec le module i4, et l'on obtient la congruence exacte

18 = 4 (mod 14).

Mais, si l'on divise les deux membres par G qui n'est pas premier avec i4, on obtient une congruence inexacte

45 = 10 (mod 14 )■

Pour obtenir une congruence exacte, il faut diviser le module i4 par le plus grand commun diviseur de 6 et de i4, qui est 2, et l'on

obtient ainsi

45 = 10 (mod 7 j.

102. Congrueiices à module premier. — Ici se dessine, pour la première fois, le caractère plus simple des congruences à modules premiers. Supposons, en effet, que le module n soit. un nombre premier absolu. Alors, pour qu'on puisse diviser les deux membres d'une congruence par un de leurs diviseurs communs <r/, il suffit que d ne soit pas divisible par n, autrement dit que d ne soit pas congru à zéro (mod/*). L'analogie des congruences avec les égalités est ainsi plus grande.

Quoi qu'il en soit, dans ce cas, comme dans celui du module non premier, il subsiste encore cette différence avec les équations que d doit être un diviseur commun des deux membres de la congruence. Nous allons supprimer cette restriction.