Congruences dans \(\mathbb{N}\) et dans \(\mathbb{Z}\)
La congruence est une notion fondamentale d’arithmétique modulaire. C’est d’ailleurs par sa définition que débute l’ouvrage référence de Carl Friedrich Gauss, Disquisitiones arithmeticae, chef d’œuvre des mathématiques. Le symbole de la congruence (trois barres parallèles horizontales) est lui aussi dû à Gauss. Aujourd'hui, les congruences, comme les nombres premiers, sont un élément essentiel de la cryptographie (codages, sécurité des réseaux…).
Petit apparté culturel : un navire océanograpique allemand a été baptisé du nom du grand mathématicien. Il participa à plusieurs expéditions polaires au début du vingtième siècle.
Définition
Soit \(a\) et \(b ∈ \mathbb{Z}\) et \(n ∈ \mathbb{N}^*.\)
On dit que \(a\) et \(b\) sont congrus modulo \(n\) (ou que \(a\) est congru à \(b\) modulo \(n\)) si et seulement si \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n.\)
On l’écrit \(a \equiv b[ n ]\) ou \(a \equiv b \,(\bmod n).\)
Soit \(r\) le reste. Nous vérifions que \(a \equiv r[n].\)
Par exemple, 4 et 7 sont congrus modulo 3 puisque le reste d'une division de 4 par 3 est 1 et de 7 par 3 aussi. Donc \(4 \equiv 7[3]\) et \(4 \equiv 1[3].\)
Il s’ensuit une propriété, qui est en fait la définition de la congruence que donnait Gauss : si \(n\) divise \(a - b,\) alors \(a\) est congru à \(b\) modulo \(n.\)
Nous faisons tous cette opération sans nous en rendre compte. Si le soir une horloge à aiguille indique onze heures, nous savons que trois heures plus tard il ne sera pas quatorze heures mais deux heures du matin puisque l’horloge fonctionne modulo 12. Donc \(14 \equiv 2[12].\)
Vous avez aussi rencontré la congruence en trigonométrie où tous les nombres congrus modulo \(2 \pi\) sont situés sur le même point du cercle trigonométrique.
Propriétés
La congruence étant réflexive, symétrique et transitive, est une relation d’équivalence (ceci est hors programme de terminale générale).
Soit \(a \equiv b[n]\) et \(c \equiv d[n].\) Les propriétés algébriques à connaître sont les suivantes :
Addition : \(a + c \equiv b + d[n].\)
Multiplication : \(ac \equiv bd[n].\)
Multiplication par un entier relatif \(k\) : \(ka \equiv kb[n].\)
Mais attention, la congruence n’est pas toujours compatible avec la division.
Puissance (avec \(p\) entier naturel) : \(a^p \equiv b^p [n].\)
Des exercices d'application, extraits d'épreuves du bac, se trouvent en page d'exercices sur la congruence.
Démonstration des propriétés d’addition et de multiplication
Soit \(a \equiv b[n]\) et \(c \equiv d[n].\)
Soit \(k\) et \(k' ∈ \mathbb{Z}\) tels que \(a = b + zn\) et \(c = d + z'n.\)
Donc \(a + c = b + d + n(z + z').\)
Comme \((z + z') ∈ \mathbb{Z},\) \(a + c \equiv b + d[n].\)
Par ailleurs \(ac\) \(=\) \((b + kn) + (d + k'n)\) \(=\) \(bd + n(bk' + kd + kk'n).\)
Or \((bk' + kd + kk'n) ∈ \mathbb{Z},\) donc \(ac \equiv bd[n].\)
Démonstration de la propriété avec les puissances
Nous utilisons la récurrence.
La relation est vraie pour \(p = 1,\) par définition de la congruence.
Si l'on suppose que \(a^p \equiv b^p[n],\) alors d’après la propriété de multiplication, nous pouvons écrire \(a^p × a \equiv b^p × b[n].\)
Et donc \(a^{p+1} \equiv b^{p+1}[n].\)
La congruence permet des démonstrations, dont voici un exemple.
Exemple de démonstration
Comment démontrer que le produit de deux nombres impairs est toujours impair ?
Soit \(a\) et \(b\) deux nombres impairs.
Nous avons donc \(a \equiv 1[2]\) et \(b \equiv 1[2].\)
Or, en utilisant la propriété de multiplication, \(a × b \equiv 1 × 1[2].\)
Comme \(a × b \equiv 1[2],\) alors le produit \(ab\) est impair.
Exercices
1- Compléter : \(100 \equiv …[9]\)
2- Déterminer selon les valeurs de \(n \in \mathbb{N}\) le reste de la division de \(2^n\) par 3.
Corrigés
1- On sait que 99 est un multiple de 9. Donc le reste de la division de 100 par 9 est 1. On peut donc répondre \(1[9],\) \(10[9],\) \(19[9]…\)
2- Pour réaliser ce type d’exercice, il faut tester des puissances successives afin d'établir une conjecture puis la prouver.
\(2^0 \equiv 1[3],\) \(2^1 \equiv 2[3],\) \(2^2 \equiv 1[3],\) \(2^3 \equiv 2[3],\) \(2^4 \equiv 1[3] …\)
Modulo 3, il semble que la suite soit de période 2. On peut d’ailleurs l’illustrer avec Excel. Pour être plus précis, il paraîtrait même que le reste d’une division par 3 d’une puissance de 2 soit 1 lorsque cette puissance est paire et 2 lorsque la puissance est impaire…
Effectuons la division euclidienne de \(n\) par 2. On pose \(n = 2q + r.\) Le reste \(r\) est soit 0 soit 1. Si \(n\) est pair \(r = 0\) et si \(n\) est impair \(r = 1.\)
Si \(n\) est pair alors \(2^n \equiv 2^0[3],\) d’où \(2^n \equiv 1[3].\)
Si \(n\) est impair alors \(2^n \equiv 2^1[3],\) d’où \(2^n \equiv 2[3].\)
La conjecture établie à partir du tableau Excel est vérifiée.
