Congruences des entiers relatifs
Exemple : congruence module 24 et heure
Imaginez une horloge numérique. Les heures affichées vont de 0h à 23h. Après 23h, on revient à 0h et un cycle recommence. 25h équivaut à 1h, 26h vaut 2h etc...
On dit que 25 est congru à 1 modulo 24 26 est congru à 2 modulo 24 etc...
Définition : Congruence
Soit \(n\) un entier naturel non nul.
Deux entiers relatifs \(a\) et \(b\) sont congrus modulo \(n\) lorsque leur différence \(a – b\) est divisible par \(n\).=
On note \(a \equiv b[n]\) .
Fondamental : congruence et division euclidienne
\(a \equiv b[n]\) si et seulement si \(a\) et \(b\) ont le même reste dans la division par \(n\).
Méthode : Démontrer une équivalence
La propriété à démontrer fait intervenir une équivalence (si et seulement si).
Pour démontrer une équivalence A <=> B il est fréquent de procéder en deux étapes :
démontrer le sens direct A => B : Si A est vrai on montre que B est vrai
démontrer la réciproque B => A : Si B est vrai on montre que A est vrai
Démonstration : sens direct
On suppose que \(a \equiv b[n]\).
Posons \(a=n\times q_1+r_1\) et \(b=n\times q_2+r_2\) les divisions euclidiennes de \(a\) et \(b\) par \(n\). \(0\leqslant r_i<n\)
On a alors \(a-b=n(q_1-q_2)+r_1-r_2\)
Mais \(a \equiv b[n]\) donc \(a-b\) est divisible par \(n\). Donc \(r_1-r_2\) est divisible par \(n\) aussi.
Encadrons \(r_1-r_2\) : \(0\leqslant r_1<n\) et \(-n < -r_2\leqslant 0\) donc \(-n < r_1-r2<n\).
On en déduit que \(r_1-r_2=0\) ce qui prouve le sens direct.
Démonstration : sens réciproque
Posons \(a=n\times q_1+r\) et \(b=n\times q_2+r\) les divisions euclidiennes de \(a\) et \(b\) par \(n\). \(0\leqslant r<n\)
\(a-b = n(q_1-q_2)\) donc \(a-b\) est divisible par \(n\), ce qui prouve que \(a \equiv b[n]\) et donc la réciproque de la propriété.
Exemple :
\(36\equiv 12 [24]\) car \(36 = 24\times 1 + 12\) donc 36 et 12 ont le même reste dans la division euclidienne par 24.
\(-5 \equiv 3 [2]\) car \(3-(-5) = 8\) et 8 est divisible par 2.