La relation de congruence est l’une des bases de l’arithmétique modulaire. Au lieu de considérer les entiers, on raisonne suivant leur reste dans la division euclidienne par un entier fixé.
I) Divisibilité dans ℤ
Définitions : Si a et b sont deux entiers relatifs, on dit que b divise a ou que b est un diviseur de a ou que a est un multiple de b ou que a est divisible par b lorsqu’il existe un entier relatif k tel que .
On note .
Propriétés
Tout entier relatif non nul n possède un nombre fini de diviseurs, compris entre et n.
Soit a, b et c trois entiers relatifs, avec et . Si a divise b et b divise c, alors a divise c.
Mot-clé
ℤ est l’ensemble des entiers relatifs, ℕ est l’ensemble des entiers naturels.
ℕ est inclus dans ℤ, on note .
Soit a, b et c trois entiers relatifs, avec . Si a divise b et c, alors a divise tout nombre de la forme , où m et n sont des entiers relatifs.
II) Division euclidienne
Soit a un entier relatif et b un entier naturel non nul.
Théorème : Il existe un unique couple d’entiers relatifs tels que :
et .
Définitions : a est le dividende, b est le diviseur, q est le quotient, r est le reste dans la division euclidienne de a par b.
III) Congruences
Définition : Soit a et b deux entiers relatifs et n un entier naturel non nul. On dit que a et b sont congrus modulo n lorsque a et b ont le même reste dans la division euclidienne par n. On note .
Propriétés : Soit a, , b, et c des entiers relatifs et n un entier naturel non nul.
a et b sont congrus modulo n si et seulement si est divisible par n.
Si et , alors .
Si et , alors et .
Si alors, pour tout entier relatif c, .
Si alors, pour tout entier naturel non nul p,
Méthodes
1) Construire et utiliser un tableau de congruences
Pour tout entier relatif n, on pose
On veut déterminer les entiers n tels que soit divisible par 5.
a. Étudier suivant le reste de n dans la division euclidienne par 5 (on dit « reste de n modulo 5 ») le reste de modulo 5. Consigner les résultats dans un tableau.
b. Conclure à l’aide du tableau de la question précédente.
Conseils
a. Utilisez les propriétés des congruences.
b. Utilisez l’équivalence « est divisible par ».
Solution
a. On peut dresser le tableau suivant.
On raisonne de la même manière pour les autres cas.
b. D’après le tableau précédent, on constate que si et seulement si . Les entiers n tels que soit divisible par 5 sont les entiers n de la forme 4 + 5k, avec k entier.
2) Montrer une divisibilité à l’aide de congruences
Montrer que, pour tout entier naturel n, est divisible par 11.
Conseils
Utilisez des congruences modulo 11.
Solution
, donc , donc, pour tout entier naturel n, (1).
, donc , donc (2).
Des relations (1) et (2) on déduit, par soustraction, que, pour tout entier naturel n, , ce qui signifie que est divisible par 11.