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 a=kb.
On note b | a.
Propriétés
Tout entier relatif non nul n possède un nombre fini de diviseurs, compris entre −n et n.
Soit a, b et c trois entiers relatifs, avec a≠0 et b≠0. 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 a≠0. Si a divise b et c, alors a divise tout nombre de la forme mb+nc, 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 q ; r d’entiers relatifs tels que :
a=bq+r et 0≤r<b.
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 a≡b n.
Propriétés : Soit a, a′, b, b′ et c des entiers relatifs et n un entier naturel non nul.
a et b sont congrus modulo n si et seulement si b−a est divisible par n.
Si a≡b n et b≡c n, alors a≡c n.
Si a≡b n et a′≡b′ n, alors a+a′≡b+b′ n et aa′≡bb′ n.
Si a≡b n alors, pour tout entier relatif c, a+c≡b+c n.
Si a≡b n alors, pour tout entier naturel non nul p, ap≡bp n.
Méthodes
1) Construire et utiliser un tableau de congruences
Pour tout entier relatif n, on pose gn=n2−3n+6.
On veut déterminer les entiers n tels que gn 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 gn 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 « gn est divisible par 5⇔gn≡0 5 ».
Solution
a. On peut dresser le tableau suivant.
5, alors n2−3n+6≡9−9+6 5, donc gn≡6 5, donc gn≡1 5.
On raisonne de la même manière pour les autres cas.
b. D’après le tableau précédent, on constate que gn≡0 5 si et seulement si n≡4 5. Les entiers n tels que gn 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, 52n−14n est divisible par 11.
Conseils
Utilisez des congruences modulo 11.
Solution
52=25, donc 52≡3 1125=11×2+3, donc, pour tout entier naturel n, 52n≡3n 11 (1).
14=11+3, donc 14≡3 11, donc 14n≡3n 11 (2).
Des relations (1) et (2) on déduit, par soustraction, que, pour tout entier naturel n, 52n−14n≡0 11, ce qui signifie que 52n−14n est divisible par 11.