1. Activité d’introduction

Le concept de congruence sert à « enrouler » les nombres relatifs, que l’on peut voir comme des points sur une droite, autour d’un cercle comportant $n$ points.

Deux nombres seront congrus modulo $n$ si, au bout d’un certain nombre de tours, ils finissent par se retrouver au même endroit sur le cercle.

Une question essentielle : les multiples d’un certain nombre $k$ finiront-ils par couvrir tous les points du cercle ?

En pratique :

On prend un médicament toutes les 5 heures. On commence à midi.

1. Donner la liste des prochains horaires auxquels il faut prendre le médicament.
2. Finira-t-on par prendre le médicament à toutes les heures du jour et de la nuit ?
3. Mêmes questions si on prend le médicament toutes les 3 heures.

Voir les exercices de travaux pratiques.

2. La théorie

2.1. Définition

Soit $n$ un entier supérieur ou égal à 2 et $a$ et $b$ deux entiers relatifs.

On dit que $a$ et $b$ sont congrus modulo $n$ si $a$ et $b$ ont le même reste dans la division euclidienne par $n$. On note :

$$a \equiv b [n]$$

ou parfois

$$a \equiv b ~ (\text{mod} ~n)$$

La définition est équivalente à l’une de ces phrases :

• $a - b$ est un multiple de $n$
• Il existe un entier relatif $k$ tel que $a - b = kn$.

2.2. Remarques

• Il ne faut pas confondre « modulo » et « modulo » !
  La notation $[n]$ ou $(\text{mod} ~n)$ ne correspond pas à une opération.
  La confusion vient du fait que le reste de la division euclidienne de $x$ par $y$ est donnée dans certains langages de programmation par l’écriture x % y et se lit « $x$ modulo $y$ ».
• S’il n’y a pas ambiguïté sur le $n$, on peut omettre le « $[n]$ ».
• On trouve dans le Littré :

  Du latin : congruus, conforme, convenable.
  En géométrie, congru s'est dit jadis de deux figures qui coïncident parfaitement. En arithmétique, d'après Gauss, nombres congrus, nombres qui ont un rapport de congruence.

• Autres références littéraires :
  • Le mot du jour
  • CNRTL

2.3. Exemples

Représenter une horloge avec 5 heures.

Les deux premiers exemples sont fondamentaux.

• $21 \equiv 21 [5]$ (mêmes nombres de départ)
• $21 \equiv 1 [5]$ (un nombre est congru à son reste)
• $21 \equiv 6 [5]$ mais aussi à $11$, $16$… de 5 en 5 (toujours le même reste, seul le quotient change)
• $n \equiv 0 [2]$ signifie que $n$ est…
• $n \equiv 1 [2]$ signifie que $n$ est…
• $a \equiv 0 [p]$ signifie que $a$ est…

2.4. Exercices classiques

• Montrer que $12 \equiv 166 [7]$.
• Donner le plus petit entier positif congru à 183 modulo 6.

2.5. Propriétés

Les propriétés sont données modulo $n$.

2.5.1. Symétrie

Si $a \equiv b$, alors $b \equiv a$.

2.5.2. Transitivité

Si $a \equiv b$ et $b \equiv c$, alors $a \equiv c$.

2.5.3. Règles de réduction, ou de compatibilité

Si $a$, $a'$, $b$ et $b'$ sont des entiers tels que $a \equiv a'$ et $b \equiv b'$, alors on a :

• $a + b \equiv a' + b'$
• $a - b \equiv a' - b'$
• $a × b \equiv a' × b'$
• $a^k \equiv a'^k$

2.5.4. Finalement

La congruence peut être considérée comme une sorte d’égalité, mais plus faible que celle que l’on connaît bien. On peut dire qu’on cache dans $\equiv$ les multiples de $n$.

Voir les exercices de travaux dirigés (non numérisés).

Voir les exercices de travaux pratiques.