Les congruences
Découvrir.
Dans la division euclidienne d'un entier par
, les restes possibles sont
Par exemple :
Ainsi les nombres
,
et
ont même reste dans la division euclidienne par
.
On dit qu'ils sont congrus entre eux modulo
.
Cela se note :
ou encore
.
Congru à 0 | Congru à 1 | Congru à 2 | Congru à 3 | Congru à 4 | Congru à 5 | Congru à 6 |
|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
... | ... | ... | ... | ... | ... | ... |
392 | 393 | 394 | 395 | 396 | 397 | 398 |
399 | 400 | 401 | 402 | 403 | 404 | 405 |
... | ... | ... | ... | ... | ... | ... |
Dans la première colonne on remarque qu'il s'agit des multiples de
.
Définition : Congruences.
Soient
et
deux entiers relatifs et
un entier naturel non nul.
On dit que
si et seulement si
et
ont même reste dans la division euclidienne par
.
se lit «
est congru à
modulo
»
Par exemple :
Fondamental : Congruence et divisibilité.
Prenons par exemple,
et
.
Leur différence
est un multiple de
.
De manière plus générale, considérons deux entiers
et
et un entier naturel non nul
.
Or
équivaut à dire qu'ils ont même reste dans la division euclidienne par
.
Soit :
.
Et donc :
, c'est-à-dire que
est un multiple de
.
Ou encore que
divise
.
________________________________________________________________________________________________________
Ce qu'il faut retenir :
Soient
et
.
Exemple : Montrons que tous les nombres pairs sont congrus entre eux modulo 2.
Les nombres pairs sont des multiples de
.
Prenons deux nombres pairs :
et
, pour
et
deux entiers relatifs non nuls.
Or
est un multiple de
donc
.
Et les nombres impairs ?
Attention : Propriétés.
Propriété 1 : Tout entier est congru à son reste modulo
, dans la division euclidienne par
.
Soit
et
.
Exemple :
donc
Preuve :
Comme
, on a :
ce qui équivaut à :
.
Propriété 2 :
Si
est un multiple de
alors
Exemple :
donc
.
Preuve :
On a :
donc
d'où :
.
Propriété 3 :
Soient
quatre entiers relatifs et
un entier naturel non nul.
Preuves :
On en présente une en exemple, les autres se font à peu près de la même manière.
.
De même
.
Donc des égalités :
et
il vient par exemple
soit
.
Pour
une récurrence semble s'imposer !
