SS

41» 55* 75* 82, 88, 100, iio, 132, 150.

18îf. Nombres congrus pour un module^ Lorsque deux entiers a et 6, positifs ou négatifs, sont tels que leur différence a — 5 est divisible par un troisième nombre m^ on dit qu'ils sont congrus ou éqidvalents par rapport à m, et ce dernier s'appelle module. On exprime algébriquement cette propriété par l'égalité

= nombre entier,

ou, par

a = 6 ± un multiple de m.

Pour abréger, Gauss a employé la notation

a = b (mod. m) admise aujourd'hui, et cette formule se nomme congruence. D'après cette définition, on peut écrire

17 = 2 (mod. 5), 9 = — 5 (mod. 7), 16 = 0 (mod. 8)

puisque 17 — 2 est divisible par 5, 9 -|- 5 par 7, et 16 par 8. La formule de Gauss doit se lire : a congru à b pour le module m.

Divisons un nombre a par m ; en appelant q le quotient et r le reste,

il vient

a==qm-\-r

et r est compris entre o et m. Mais, on a aussi

ft = (g -|- i)m — {7)1 — r),

c'est-à-dire, qu'en augmentant le quotient d'une unité, on doit prendre pour

le reste — (m — r). Si r = — > m — r a aussi pour valeur — ; mais, si r est

plus grand que —j m — r est inférieur à — • Il en résulte qu'un nombre

quelconque admet toujours un reste positif ou négatif moindre, en valeur

absolue, que la moitié du module. On l'appelle reste ou résidu minimum.

Observons que, r étant le reste de la division de a par m, a — r est

divisible par m, et l'on peut toujours écrire pour chaque nombre

a^r (mod. m).

Par une extension du mot reste, les nombres a et 6 de la formule

a=.b (mod. m)

s'appellent quelquefois résidus l'un de l'autre pour le module m.

H importe d enumérer les transformations élémentaires que l'on peut faire

subir aux congruences. En premier lieu, si deux nombres sont congrus à un

troisième pour le même module, ils sont congrus entre eux; en d'autres

termes, les congruences

a = c (mod. m), b^c (mod. m)

entraînent la suivante :

a = b (mod. m);

car, si les quotients

sont entiers, il en est de même de leur différence.

Addition et soustraction. Etant données les congruences de même module

a^h (mod. ^«), a' ^^h' (raod. w), on aura aussi

a:ha^ = bdcb' (mod. wi).

En effet, si on ajoute et si on retranche les quantités

qui sont des nombres entiers, il vient a — & ± (a' — b')

m c'est-à-dire,

nombre entier,

a ■\- a' ^b -\' b\ a ^ a' = b — &' (mod. m).

Multiplication, élévation aux puissances. On peut multiplier les deux termes d'une congruence par un nombre quelconque n; car, si l'on a

a = b (mod. 7?î),

est un nombre entier, ainsi que ; donc

na=nb (mod. m).

Les congruences

a=b (mod. m), a' = b' (mod. m)

sont équivalentes aux égalités

a = 6 -j- un multiple de w, a' = b' ~\- un multiple de m.

En les multipliant, il vient

flft' = bb' -{- un multiple de w,

aa' = bb' (mod. m).

Si l'on a encore une troisième congruence de même module

ft" = b" (mod. m), on écrit aussi

a" = 6" -|- "^ multiple de m.

Par la multiplication de cette égalité avec la précédente on trouve

aa'a" = hVh^' ■\- un multiple de m\ donc,

aa'a" = bb'b" (mod. w),

et ainsi de suite. Il est donc permis de multiplier entre elles les congruences de même module.

En posant a = a' = a", 6 = 6' = 6", on a aussi

a' = 6' (mod. ;;i), a^ = b' (mod. m)

et, en général,

a^^^k (mod. 7n).

Division. Pour diviser les deux termes d'une congrucnce par un nombre ?î, il faut que ce nombre soit premier avec le module. Soit la congruence

na = n6 (mod. m),

et k un entier; on peut écrire

na = nb -\-km;

d'où

km a =sb -\

Si n est premier avec m, il faut que A; soit divisible par w; nous aurons ainsi

a == 6 -j- un multiple de m, ou bien

a = 6 (mod. m).

Quand il existe un facteur commun entre n et le module, on peut remplacer

la fraction — par la fraction — r obtenue en supprimant le facteur commun ; n n'

il vient alors

et A: devrait être divisible par n'; il en résulterait alors une congruence d'un autre module m\

Nous allons faire l'application de ces propriétés à la démonstration de deux théorèmes importants de la théorie des nombres : le théorème de Fermât et celui de Wilson.

189. Théorème de Fermât. Si p est un nombre premier et a un nombre quelconque non divisible par p, la différence a^~^ — i est un multiple de p, c'est à'dire que Von a la congruence

flP-i = I (mod. p).

En effet, nous avons vu que les entiers de la suite

donnent pour résidus relativement à p les nombres

dans un certain ordre. Chaque nombre de la première suite est donc congru à un certain nombre de la seconde suivant le module;?; par suite, le produit des premiers nombres sera congru au produit des autres et l'on a :

a . 2ft . 3» . ... (p — i)ft = I .2 . 3 ... jo — I (mod. p) ou bien

ftP~' (i . 2 . 3 ... jo — i)= I . 2 . 3 ...p — I (mod.;^).

Si on divise par le produit i .2.3.../) — i qui est premier avec le

module, il vient

aP~^ = I (mod. p),

II résulte de cette propriété que, si a est un entier quelconque, et p un nombre premier, la différence a^ — a est divisible par p; car, on a :

aP — a = a{a^~^ — i) ;

si ;) divise a, la propriété a lieu; si jo ne divise pas a, il divise alors le

second facteur.

Le théorème de Fermât est susceptible de généralisation. Désignons par a

et m deux nombres premiers entre eux et par \ç{m) l'indicateur de m; on a

aussi

a9<'") = i (mod. w).

Pour le démontrer, représentons par

(a) I, 6, c, dy ..., /

les nombres premiers à m et plus petits que m; en multipliant par a, il vient

((5) a, ab, aCj ad, ..., al

et aucun de ces nombres n'est divisible par m, puisque a est premier à m et b, c, d .... inférieurs à m. Si on les divise par w, tous les résidus seront différents; car, en admettant que les nombres ac et arf, par exemple, divisés

par m donnent le même reste, leur différence a{c — d) serait divisible par w, ce qui est impossible; on obtiendra donc ^[m) résidus différents qui seront précisément les termes de la suite (a). Chaque nombre de ()S) est congru à un certain nombre de (a), et le produit des nombres de la seconde suite sera congru au produit des nombres de la première. Il vient donc

a . ah . ac ... al = h . c . d .., l (mod. nt)f ou bien,

a'^^^'^Q) .c.d,..l) = {b.c.d ... l) (mod. m) ;

En divisant par le produit b . c . d ... l qui est premier à m, il reste

Donc, si a et m sont premiers entre eux, la di/férence a^'^"'^ — i est divisible par m.

18B. Théorème de Wilson. Si p est un nombre f rentier, la somme I . 2 . 3 ... (p — i)-\- i est divisible par p, c'est'à-dire que l'on a :

I . 2 , ^ ... (p — i)-|-iEEo (mod. p). En effet, considérons la suite des nombres inférieurs à p (y) I, 2, 3, 4, ..., p~i,

et soit 71 l'un quelconque d'entre eux. Formons avec 7i la seconde suite

0) n, in., 3%, 4%, ..., [p — i)n.

Tous ces nombres divisés par p donnent pour résidus ceux de la première suite; un seul sera congru à l'unité; désignons-le par kn-, on aura

kti = I (mod . p) .

Les nombres k et n sont différents l'un de l'autre à moins que 7i soit i ou p — I, les termes extrêmes de la suite (y). En effet, posons k^-= n; conformément à la congruence, la différence n^ — i ou {n — i) {n -|- i) doit être divisible par p, et cela n'est possible que pour ?^ = i ei 7i = p — i. Il en résulte qu'en laissant i et jo — i, les autres nombres de la suite (y) sîivoir :

2, 3- 4' 5» •••» P — 2 peuvent se grouper deux à deux de manière que le produit des nombres de chaque groupe soit congru à l'unité ; en multipliant les congruences correspondantes à tous les groupes, il viendra