Soient et des entiers, alors on dit que est congru à modulo, ce qui s'écrit si ; est le module de la congruence.
Propriétés de la congruence
- et ont le même reste dans la division par
- (réflexivité).
- (symétrie).
- et (transitivité).
- et
I.3. Classes des
résidus
Soit Pour chaque entier on définit , en d'autres termes est l'ensemble de tous les entiers qui sont congrus à modulo . Les autres auteurs appellent la classe congruence ou la classe d'équivalence de modulo
Théorème.
Pour on a : .
Preuve
Supposons
pour tout . Notons que dépends de
On a deux façons d'écrire l'équation
ci-haut :
ou
Tout élément est une représentation de la classe de résidu .
I.4. Ensemble réduit des
résidus
Définition
On défini , alors est l'ensemble de toutes les classes modulo . Nous appelons l'anneau des entiers .
Addition et multiplication dans
Pour , on a :
et
Exemple
Pour
et
Notons que puisque et ,nous avons et . Nous pouvons aussi écrire et
I.5. La fonction d'Euler ou
fonction totient
Définition
Pour ,soit le nombre d'entiers premiers avec dans l'intervalle . La fonction est la fonction d'Euler.
Exemple
Pour , il y a différentes classes de résidu modulo ; les classes et ne sont pas premiers avec ; ainsi seules les classes et sont premiers avec :alors .
Si est un premier, toutes les classes sont premiers avec , alors
Exemple :
2
4
5
6
7
8
9
10
12
15
2
2
4
2
6
4
6
4
4
8
Théorème (Euler)
Soit , alors
Ceci permet de calculer l'inverse modulaire définit
par :
Exemple
Quel est l'inverse de on sait que
On a d'où
Théorème (Petit théorème
de Fermat)
Soit un premier et un entier tel que alors
Preuve
Considérons les entiers suivants : ainsi que leurs restes dans la division euclidienne par notés : Ces restes sont compris entre
En effet, d'après le même de Gauss, si divisait un des ces produits diviserait puisque et sont premiers entre eux, mais ceci est impossible puisque De plus les restes de division de par sont tous différents. Si on trouvait des restes identiques pour
et alors le reste de par serait nul, ce qui est impossible d'après ce qui
précède.
Notons que ces restes sont donc des entiers compris entre et .
En multipliant membre à membre les
congruences :
Alors nous obtenons :
Par définition de la congruence, cette
égalité signifie que divise Or ne divise aucun des entiers il est également premier avec leur produit
Ainsi d'après le lemme de Gauss divise c'est-à-dire .
Théorème de Wilson
Si est un premier, alors
Preuve
Considérons la congruence Alors , ainsi les seules solutions sont et Donc, pour chaque , il existe qu'un inverse unique de ,. Ainsi lorsque nous groupons des inverses en pairs, nous
obtenons :
Théorème du reste Chinois
Soit des entiers et des entiers relativement premiers entre eux, alors le
système des congruences
,
admet une unique solution modulo
Preuve
Soit ,et considérons .Ceci est relativement premier à ainsi il existe un entier tel que.
En conséquence, soit . Alors et D'une manière similaire, il existe un tel que et , Alors est une solution du système ci-haut.
et 
des entiers, alors on dit que 
est congru à 
modulo
, ce qui s'écrit 
si 
; 
est le module de la congruence.
- 
et 
ont le même reste dans la division par 
- 
(réflexivité).
- 
(symétrie).
- 
et 
(transitivité).
- 
et 
Pour chaque entier 
on définit 
, en d'autres termes 
est l'ensemble de tous les entiers qui sont congrus à 
modulo 
. Les autres auteurs appellent 
la classe congruence ou la classe d'équivalence de 
modulo 
on a : 
.
. Notons que 
dépends de 
ou 
est une représentation de la classe de résidu 
.
, alors 
est l'ensemble de toutes les classes modulo 
. Nous appelons 
l'anneau des entiers 
.
, on a :
et 
et 
et 
,nous avons 
et 
. Nous pouvons aussi écrire 
et 
,soit 
le nombre d'entiers premiers avec 
dans l'intervalle 
. La fonction 
est la fonction d'Euler. 
, il y a 
différentes classes de résidu modulo 
; les classes 
et 
ne sont pas premiers avec 
; ainsi seules les classes 
et 
sont premiers avec 
:alors 
.
est un premier, toutes les 
classes 
sont premiers avec , alors 
, alors 
on sait que 
d'où 
un premier et 
un entier tel que 
alors 
entiers suivants :
ainsi que leurs restes dans la division euclidienne par 
notés :
Ces restes sont compris entre 
divisait un des ces produits 
diviserait 
puisque 
et 
sont premiers entre eux, mais ceci est impossible puisque 
De plus les restes de division de 
par 
sont tous différents. Si on trouvait des restes identiques pour
et 
alors le reste de 
par 
serait nul, ce qui est impossible d'après ce qui
précède.
et 
.
divise 
Or 
ne divise aucun des entiers 
il est également premier avec leur produit 
divise 
c'est-à-dire 
.
est un premier, alors 
Alors 
, ainsi les seules solutions sont 
et 
Donc, pour chaque 
, il existe qu'un inverse unique 
de 
,
. Ainsi lorsque nous groupons des inverses en pairs, nous
obtenons :
des entiers et 
des entiers relativement premiers entre eux, alors le
système des congruences 
,
,et considérons 
.Ceci est relativement premier à 
ainsi il existe un entier 
tel que
.
. Alors 
et 
D'une manière similaire, 
il existe un 
tel que 
et 
,
Alors 
est une solution du système ci-haut.
une autre solution, alors 
