La congruence

Congruences dans N et dans 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) 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…).

Définition

Soit a et b ∈ Z et n ∈ 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 ≡ b[n] ou a ≡ b(mod n).

Soit r le reste. Nous vérifions que ar[n].

Par exemple, 4 et 7 sont congrus modulo 3 puisque le reste est 1. Donc 4 ≡ 7[3] et 4 ≡ 1[3].

Il s’ensuit une propriété, qui est en fait la définition 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 ≡ 2[12].

Vous avez aussi rencontré la congruence en trigonométrie où tous les nombres congrus modulo 2π sont situés sur le même point du cercle trigonométrique.

Propriétés

La congruence étant réflexive, symétrique et transitive, c’est donc une relation d’équivalence (ceci est hors programme de terminale S).

Les propriétés algébriques à connaître :

Soit a ≡ b[n] et c ≡ d[n].

Addition : a + c ≡ b + d[n].

Multiplication : ac ≡ bd[n].

Multiplication par un entier relatif k : ka ≡ kb[n].

Mais attention, la congruence n’est pas toujours compatible avec la division.

Puissance (avec p entier naturel) : ap ≡ bp[n].

Démonstration des propriétés d’addition et de multiplication :

Soit a ≡ b[n] et c ≡ d[n].

Soit k et k’ ∈ Z tels que a = b + zn et c = dz’n.

Donc a + cb + d + n(zz’).

Comme (z + z’) ∈ Z, a + c ≡ b + d[n].

Par ailleurs ac = (b + kn) + (dk’n) = bdn(bk’ + kd + kk’n).

Or (bk’ + kd + kk’n) ∈ Z, donc ac ≡ 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.

Supposons que a≡ bp[n]. Alors, d’après la propriété de multiplication, nous pouvons écrire a× a ≡ bp × b[n].

Et donc ap+1 ≡ bp+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 ≡ 1[2] et b ≡ 1[2].

Or, en utilisant la propriété de multiplication, a × b ≡ 1 × 1[2].

Comme a × b ≡ 1[2], alors le produit ab est impair.

Exercices

1- Compléter : 100 ≡  …[9]

2- Déterminer selon les valeurs de n entier naturel le reste de la division de 2n 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.

20 ≡ 1[3], 21 ≡ 2[3], 22 ≡ 1[3], 23 ≡ 2[3], 24 ≡ 1[3], …

Modulo 3, il semble que la suite soit de période 2. On peut d’ailleurs l’illustrer avec Excel. Il semble même que, pour être plus précis, 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…

tableau Excel

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 2n ≡ 20[3], d’où 2n ≡ 1[3].

Si n est impair alors 2n ≡ 21[3], d’où 2n ≡ 2[3].

La conjecture établie à partir du tableau Excel est vérifiée.