Congruences

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

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

Il est tellement évident de vérifier que, pour 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 est congru à modulo , on note :

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

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

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 , et trois entiers relatifs. Alors :

$\displaystyle {\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 de ? On commence par écrire

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

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

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

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

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

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

et la réponse est .

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

Exercice : Montrer qu'une règle de calcul possible pour calculer des congruences modulo est la suivante. On décompose l'écriture de en base en groupes de chiffres consécutifs en commençant par le chiffre des unités. Si un bloc vaut , on note . Puis on effectue la somme alternée des en commençant par le bloc du chiffre des unités. Alors et sont congrus modulo .

Par exemple, si , 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

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

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