Définition Soient un entier et
.
On dit que est congru à modulo s'il existe
un
tel que . On écrit alors
ou ou mod
Remarque 17
On a
si et seulement si
et ont le même reste dans la division euclidienne par
. En effet, si nous avons et , alors
et
. Réciproquement,
si et
et que , alors
et par l'unicité de la division euclidienne, il s'ensuit
que (et ).
Exemple 18
Nous avons
car
.
Notons que a effectivement le même reste que
pour la division euclidienne par car
.
Lemme
a)
La relation est une relation d'équivalence.
b)
Si
et
, alors
et
.
Dans ce cas, on a aussi
pour tout
.
c)
Les nombres
forment un système
de représentants des classes par rapport à .
Démonstration. a) La relation est réflexive car nous avons
pour tout
. Elle est symétrique car si nous avons
alors nous avons
. Elle est transitive,
car si nous avons et , alors nous
avons
.
b) Supposons que et que . Alors
et
La dernière affirmation s'ensuit par récurrence sur .
c) Tout
est équivalent par à
un et un seul des nombres
. En effet, cette
affirmation est une reformulation de l'existence et de
l'unicité du reste dans la division euclidienne de par .
Définition On pose
On note
ou
(ou même ) la classe
de
. Les éléments de
sont donc
les
,
. On munit
des deux lois
Exemple 19
Grâce au lemme ci-dessus les deux lois sont
bien définies.
Par définition de la notion de `classe d'équivalence',
nous avons
si et seulement si
Par conséquent, deux classes
et
sont égales ssi les restes de et par la division
euclidienne par sont égaux.
D'après le lemme ci-dessus, les classes
sont distinctes deux à deux et toute classe est égale
à une d'entre elles. Ces classes constituent donc la
liste (exhaustive et sans répétitions) des éléments
de
. En particulier, est de cardinal .