DES CONGRUENCES
Des nombres congrus ou équwalents,
281 . Si la différence des deux nombres entiers a et i, positifs ou négatifs, est divisible par un troisième nombre positif M, a et i sont dits congrius ou équivalents par rapporta M; le diviseur M est appelé le module; a et i sont résidus l'un de l'autre suivant le module M.
Pour exprimer que n cl b sont congrus suivant le module M, il suffît d^ccrire
a = bzh un multiple de M;
mais nous adopterons la notation plus commode de Gauss, et nous écrirons
arzrb (mod. M);
cette formule sera dite une congruence.
Si r désigne le reste de la division de a par M, on a
a^zizr (mod. M);
le reste r est, si Ton veut, compris entre o et M, ou
entre et H » d ou il suit que tout nombre a un
résidu inférieur en valeur absolue à la moitié du module.
On le nomme résidu minimum; mais, si Ton ne veut considérer que les résidus positifs, les limites seront
o et M, et le résidu minimum pourra surpasser — •
282. La notation de Gauss, pour représenter les congruenccsy a Tavantage de mettre en évidence l'analogie qui existe entre les congruences et les égalités, sans qu'il y ait pourtant de confusion à craindre. Nous allons faire voir que la plupart des transformations que Ton peut ' faire subir aux égalités peuvent être appliquées aux congruences.
Additiow et soustraction. — Si Ton a
aznb (mod. M), a! r.-y (mod. M), on aura aussi
a-±,a^—h±h' (mod. M).
Les congruences proposées expriment, en effet, que
a := b + un multiple de M,
^' iir: ^' H- un multiple de M ;
donc
adia' =ih±b* + un multiple de M,
ou
a±:a'^b±b' (mod. M),
ce qu'il fallait démontrer.
Multiplication. — On peut multiplier une congruence par un nombre entier quelconque ; car soit
aE3b (mod. M),
c'cst-à-dirc
a-^jz b-^jxa multiple de M,
on aura aussi, quel que soit Tentier m,
ma =- /it6 + un multiple de M,
SECTION III. CHAPITRE i# 7
oa
ma^=mb [mod. M).
On peut aussi multiplier entre elles plusieurs congruences de méihe module. Soient, en effet, deux con-
gruences
a ^b (mod. M),
a' = b' (mod. M),
ou
a = 6 + un multiple de M,
af =:b* + \m multiple de M.
On aura, en multipliant,
aa^ = bb' + un multiple de M,
ou
aa'^bb' (mod. M),
ce qu'il fallait démontrer.
On voit généralement que, si Ton a
' (mod. M),
on aura aussi
aa! ,.,a^'^)E^bb\., b^^^ (mod. M).
Élévation aux puissances — On peut élever à une même puissance les deux membres d'une congruence. Cela résulte immédiatement de ce que nous venons de dire au sujet de la multiplication. Si donc on a
a 1=12 b (mod. M),
on aura aussi
am^lm (mod. M),
D'après cela, si
/(x) = Aa:"'4-Ba:'»4-...
est une fonction entière et rationnelle de Xj dont les
coefficients A, B, ... soient des nombres entiers, et
que Ton ait
a-:=ih (mod. M),
on aura aussi
f[a)^f[h) (mod.M;.
Division. — On peut diviser une congruence par un nombre quelconque premier avec le module. Soit, en effe*, la congrucnce
ma EU mh ( mod. M ) ou
ma =r mh H- M X Ç,
on aura, en divisant par m,
a^=zh -\ ^,
et, si Ton suppose m premier avec M, q devra être divisible par m, et Ton aura
a -= ^ + un multiple de M,
ou
a-=B.h (mod. M).
Mais ce résultat ne subsiste pas quand le nombre m et le
module M ont un diviseur commun; car soit — r la frac-
m lit
tioD irréductible équivalente à -9 on aura
cela exige seulement que 9 soit divisible par wln, et Ton
aura
a^zzb (mod.M').
On peut aussi diviser une congrucnce par une autre, pourvu que les membres de la seconde soient premiers
avec le module. Soient, en efTet, les deux congruences
(i) aci — hV (mod. M),
(2) azL^ib (mod. M).
Désignons par r le résidu minimum de la diflerence d — V^ on aura
(3) a'~.Vz±.r (mod. M),
et, en multipliant les congrucnccs (a) et (3) l'une par l'autre,
(4) aa!^hy±hr (mod. M).
Des congrucnces (i) et (4) on déduit
hr^ziQ (mod. M):
or M est premier avec J, par hypothèse ; donc
r-znQ (mod. M), ou
puisque r^M. On a par conséquent
a'^b' (mod. M), ce qu'il fallait démontrer.
Du nombre qui exprime combien il y a de nombres premiers à un nombre donné et non supérieurs à ce nombre.
