Congruences

Juste quelques notations pratiques. La section se réduit à quasiment rien.

Définition 6   Soit $a$ et $b$ des entiers relatifs et $n\geqslant 1$ un entier strictement positif. On dit que $a$ est congru à $b$ modulo $n$ lorsque $b-a$ est un multiple de $n$.

Il est tellement évident de vérifier que, pour $n$ fixé, la relation «est congru à» est une relation d'équivalence sur $\mathbb{Z}$ que cet énoncé n'aura pas même l'honneur d'être qualifié de proposition.

Notation 4   Lorsque $a$ est congru à $b$ modulo $n$, on note :

$$a\equiv b [n].$$

Exemple 1   On repère les jours de l'année par leur numéro de $1$ à $365$ ou $366$ selon les cas. Alors les numéros de tous les lundis sont congrus les uns aux autres modulo $7$.

L'intérêt des congruences est d'être compatibles avec l'addition et la multiplication, au sens suivant :

Proposition 3   Soit $n\geqslant 1$ fixé et soit $a$, $b$ et $c$ trois entiers relatifs. Alors :

$${\rm si}\quad a\equiv b [n]\quad {\rm alors}\quad a+c\equiv b+c [n]\quad {\rm et}\quad ac\equiv bc [n].$$

Démonstration : C'est vraiment trop facile.$\square$

Exemple 2   Quel est le reste de la division par $9$ de $12345$ ? On commence par écrire

$$12345=10^4+2\cdot10^3+3\cdot10^2+4\cdot10+5.$$

Comme $10\equiv1 [9]$, on en déduit

$$12345\equiv 1^4+2\cdot1^3+3\cdot1^2+4\cdot1+5 =1+2+3+4+5=15,$$

et

$$12345\equiv1\cdot10+5\equiv 1\cdot1+5=1+5=6,$$

donc la réponse est $6$. Et par $11$ ? Ici, on utilise le fait que $10\equiv-1 [11]$, donc

$$12345\equiv ({-1})^4+2\cdot({-1})^3+3\cdot({-1})^2+4\cdot({-1})^1+ 5=3,$$

et la réponse est $3$.

Exercice : Formaliser les règles de calcul des congruences modulo $9$ et modulo $11$ utilisées dans l'exemple 2.

Exercice : Montrer qu'une règle de calcul possible pour calculer des congruences modulo $7$ est la suivante. On décompose l'écriture de $n$ en base $10$ en groupes de $3$ chiffres consécutifs en commençant par le chiffre des unités. Si un bloc vaut $B=abc$, on note $s(B)=2a+3b+c$. Puis on effectue la somme alternée $s(n)$ des $s(B)$ en commençant par le bloc du chiffre des unités. Alors $n$ et $s(n)$ sont congrus modulo $7$.

Par exemple, si $n=12345678$, les blocs sont $B_{3}=012$, $B_{2}=345$ et $B_{1}=678$. On calcule $s(B_{3})=2\times0+3\times1+1\times2=5$, $s(B_{2})=2\times3+3\times4+1\times5=23$, $s(B_{1})=2\times6+3\times7+1\times8=41$, puis

$$s(n)=s(B_{1})-s(B_{2})+s(B_{3})=41-23+5=23,$$

donc $n\equiv23 [7]$ et enfin $n\equiv2 [7]$.