Congruences modulo n : définition et calculs

Deux entiers a et b sont congrus modulo n (n entier, n ≥ 2) quand ils ont le même reste dans la division par n, c'est-à-dire quand leur différence a − b est un multiple de n. On écrit a ≡ b [n] ou a ≡ b (mod n). Par exemple 38 ≡ 3 [7], car 38 − 3 = 35 = 7 × 5. Les congruences permettent de calculer « sur les restes » sans manipuler de grands nombres : c'est le calcul de l'horloge, des jours de la semaine, des clés de contrôle et du chiffrement. Ce chapitre donne la définition, les règles de calcul et leurs applications.

Définition et notations

Exemples :

• 38 ≡ 3 [7] : 38 − 3 = 35 = 7 × 5. Les deux ont pour reste 3 dans la division par 7.
• 2 026 ≡ 3 [7] : 2 026 = 7 × 289 + 3.
• 25 ≡ 1 [12] : 25 − 1 = 24 = 12 × 2.
• 17 ≢ 4 [5] (non congrus) : 17 − 4 = 13 n'est pas multiple de 5.
• a ≡ 0 [n] signifie que n divise a : 2 023 ≡ 0 [7].
• a ≡ 0 [2] signifie que a est pair, a ≡ 1 [2] qu'il est impair.

Tout entier est congru à son reste

Si a = n × q + r est la division euclidienne de a par n, alors a − r = n × q est un multiple de n, donc a ≡ r [n] avec 0 ≤ r < n. Chaque entier est donc congru à exactement un des n nombres 0, 1, …, n − 1. Ces n restes possibles sont les représentants des n classes modulo n : la classe de r est l'ensemble des entiers congrus à r modulo n.

Modulo 3, tous les entiers se rangent en trois classes :

C'est exactement le principe d'une horloge : modulo 12, 15 heures et 3 heures tombent au même endroit du cadran. Calculer modulo n, c'est compter sur un cercle de n positions.

Avec des négatifs. La définition marche aussi pour les entiers négatifs : −3 ≡ 4 [7], car −3 − 4 = −7 est un multiple de 7. Pour trouver le représentant entre 0 et n − 1 d'un nombre négatif, ajoute n autant de fois que nécessaire : −3 + 7 = 4. De même, −45 ≡ −45 + 2 × 26 = 7 [26].

Les propriétés de la congruence

La congruence modulo n se manipule presque comme une égalité :

• réflexivité : a ≡ a [n] ;
• symétrie : si a ≡ b [n], alors b ≡ a [n] ;
• transitivité : si a ≡ b [n] et b ≡ c [n], alors a ≡ c [n].

C'est donc une relation d'équivalence (voir le cours sur les relations d'équivalence), et ses classes d'équivalence sont les classes de restes ci-dessus.

Surtout, elle est compatible avec l'addition et la multiplication :

Pourquoi l'addition marche : a − b = n × u et c − d = n × v, donc (a + c) − (b + d) = n × (u + v), un multiple de n. Pour la multiplication : ac − bd = a(c − d) + d(a − b) = a × n × v + d × n × u, encore un multiple de n.

Mener un calcul de congruence

La méthode tient en une phrase : réduis chaque nombre modulo n le plus tôt possible, puis calcule avec les petits restes.

Exemple 1 : le reste de 2 026 × 2 027 dans la division par 7. 2 026 ≡ 3 [7] et 2 027 ≡ 4 [7], donc 2 026 × 2 027 ≡ 3 × 4 = 12 ≡ 5 [7]. Inutile de calculer le produit, 4 106 702.

Exemple 2 : le chiffre des unités de 7²⁰²⁶. Le chiffre des unités est le reste modulo 10. On cherche une puissance de 7 congrue à 1 :

7⁴ ≡ 1 [10]. Or 2 026 = 4 × 506 + 2, donc 7²⁰²⁶ = (7⁴)⁵⁰⁶ × 7² ≡ 1⁵⁰⁶ × 49 ≡ 9 [10]. Le chiffre des unités de 7²⁰²⁶ est 9.

Exemple 3 : le reste de 3²⁰²⁶ dans la division par 7.

On obtient chaque ligne en multipliant la précédente par 3 et en réduisant : 3 × 3 = 9 ≡ 2 ; 2 × 3 = 6 ; 6 × 3 = 18 ≡ 4 ; 4 × 3 = 12 ≡ 5 ; 5 × 3 = 15 ≡ 1. 3⁶ ≡ 1 [7] et 2 026 = 6 × 337 + 4, donc 3²⁰²⁶ ≡ 3⁴ ≡ 4 [7].

Les tables modulo n

Comme il n'y a que n restes, on peut dresser toutes les additions et multiplications modulo n dans une table. Voici la table de multiplication modulo 6 :

Deux choses surprennent :

• 2 × 3 ≡ 0 [6] alors que ni 2 ni 3 n'est congru à 0. Un produit peut être nul sans qu'aucun facteur le soit.
• Les lignes de 1 et de 5 contiennent tous les restes, chacun une fois ; celles de 2, 3 et 4 n'en contiennent qu'une partie. 1 et 5 sont premiers avec 6, pas 2, 3 et 4.

Compare avec la table de multiplication modulo 5, où 5 est premier :

Ici, chaque ligne non nulle contient tous les restes, et donc un 1 : 2 × 3 ≡ 1 [5], 4 × 4 ≡ 1 [5]. Ce que tu observes dans ces deux tables, c'est la propriété du programme sur les multiples modulo n et la notion d'inverse, détaillées au chapitre 9.

Pourquoi les critères de divisibilité marchent

Les congruences expliquent les critères du chapitre 5. Prends 7 425 = 7 × 10³ + 4 × 10² + 2 × 10 + 5.

• Par 9 (et par 3) : 10 ≡ 1 [9], donc toute puissance 10ᵏ ≡ 1 [9], et 7 425 ≡ 7 + 4 + 2 + 5 = 18 ≡ 0 [9]. Un nombre est congru modulo 9 à la somme de ses chiffres. C'est vrai aussi modulo 3, puisque 10 ≡ 1 [3].
• Par 11 : 10 ≡ −1 [11], donc 10ᵏ ≡ 1 si k est pair et −1 si k est impair. 7 425 ≡ −7 + 4 − 2 + 5 = 0 [11] : on retrouve la somme alternée.
• Par 4 : 100 ≡ 0 [4], donc seuls les deux derniers chiffres comptent.

C'est aussi le principe de la preuve par 9 des écoliers : si a × b = c, alors la somme des chiffres de c doit être congrue modulo 9 au produit des sommes des chiffres de a et b.

Applications : les clés de contrôle

Une clé de contrôle est un ou plusieurs chiffres ajoutés à un numéro pour détecter une erreur de saisie. Elle se calcule presque toujours avec un modulo.

Le numéro de sécurité sociale (NIR). Il compte 13 chiffres suivis d'une clé de 2 chiffres : clé = 97 − (N mod 97), où N est le nombre formé par les 13 chiffres. Pour le numéro fictif 1 85 05 78 006 084 : N = 1 850 578 006 084, N mod 97 = 6, et la clé vaut 97 − 6 = 91. Si on se trompe d'un seul chiffre en le saisissant, le reste change et la clé ne correspond plus.

L'IBAN. Un IBAN est valide si, après avoir déplacé les quatre premiers caractères à la fin et remplacé chaque lettre par un nombre (A = 10, B = 11… Z = 35), le nombre obtenu est congru à 1 modulo 97. C'est le cas de l'IBAN d'exemple FR76 3000 6000 0112 3456 7890 189 que l'on trouve dans les documentations bancaires. Ce contrôle détecte toutes les erreurs portant sur un seul chiffre et la plupart des inversions de deux caractères voisins, les deux fautes de frappe les plus courantes.

Les codes-barres EAN-13 et les ISBN-13. Les 13 chiffres d'un code-barres de produit ou d'un livre vérifient : la somme des chiffres de rang impair, plus 3 fois la somme des chiffres de rang pair, est congrue à 0 modulo 10. Pour l'ISBN fictif 978-2-1234-5680-? :

La somme vaut 97 ≡ 7 [10]. Pour atteindre un multiple de 10, la clé est 3 : 97 + 3 = 100. L'ISBN complet est 978-2-1234-5680-3.

Exercices

Exercice 1 sur 5 Vrai ou faux Réussi À revoir

Justifie chaque réponse.

1. 47 ≡ 2 [9]
2. 100 ≡ 1 [11]
3. −8 ≡ 5 [13]
4. 2 026 ≡ 0 [2]
5. 123 456 789 ≡ 0 [9]

Voir la réponseMasquer la réponse de l'exercice 1

1. Vrai : 47 − 2 = 45 = 9 × 5.
2. Vrai : 100 − 1 = 99 = 11 × 9.
3. Vrai : −8 − 5 = −13 = 13 × (−1).
4. Vrai : 2 026 est pair.
5. Vrai : la somme des chiffres vaut 1 + 2 + … + 9 = 45, un multiple de 9, donc 123 456 789 ≡ 45 ≡ 0 [9].

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 5 Réduire avant de calculer Réussi À revoir

Sans calculatrice, donne le reste de la division euclidienne :

1. de 45 × 76 + 33 par 8 ;
2. de 1 234 567 × 7 654 321 par 9 ;
3. de 6⁹⁹ par 7.

Voir la réponseMasquer la réponse de l'exercice 2

1. 45 = 8 × 5 + 5, donc 45 ≡ 5 [8] ; 76 = 8 × 9 + 4, donc 76 ≡ 4 [8] ; 33 ≡ 1 [8]. 45 × 76 + 33 ≡ 5 × 4 + 1 = 21 ≡ 5 [8].
2. Somme des chiffres de 1 234 567 : 28 ≡ 1 [9]. Somme des chiffres de 7 654 321 : 28 ≡ 1 [9]. Le produit est congru à 1 × 1 = 1 [9].
3. 6 ≡ −1 [7], donc 6⁹⁹ ≡ (−1)⁹⁹ = −1 ≡ 6 [7]. Remplacer un reste par un nombre négatif proche de 0 simplifie souvent les puissances.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 5 Puissances et chiffre des unités Réussi À revoir

1. Quel est le chiffre des unités de 2²⁰²⁶ ?
2. Quel est le reste de 5²⁰²⁶ dans la division par 9 ?
3. Montre que 2¹⁰ ≡ 1 [11].

Voir la réponseMasquer la réponse de l'exercice 3

1. Puissances de 2 modulo 10 : 2, 4, 8, 16 ≡ 6, 12 ≡ 2… Le cycle 2, 4, 8, 6 a une longueur 4. 2 026 = 4 × 506 + 2 : 2²⁰²⁶ ≡ 2² = 4 [10]. Le chiffre des unités est 4. (Attention : 2⁴ ≡ 6 et non 1 ; ici on utilise le fait que le cycle se répète à partir de 2¹.)
2. Puissances de 5 modulo 9 : 5, 25 ≡ 7, 35 ≡ 8, 40 ≡ 4, 20 ≡ 2, 10 ≡ 1. 5⁶ ≡ 1 [9] et 2 026 = 6 × 337 + 4, donc 5²⁰²⁶ ≡ 5⁴ ≡ 4 [9].
3. 2⁵ = 32 = 2 × 11 + 10, donc 2⁵ ≡ 10 ≡ −1 [11]. Alors 2¹⁰ = (2⁵)² ≡ (−1)² = 1 [11].

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 5 Horaires et jours Réussi À revoir

1. Un traitement de nuit démarre à 22 h et dure 29 heures. À quelle heure se termine-t-il ? Écris le calcul avec une congruence.
2. Dans un tourniquet de répartition de charge à 3 serveurs, numérotés 0, 1 et 2, la requête numéro k est envoyée au serveur k mod 3. Vers quel serveur part la requête 2 026 ? Combien de requêtes, parmi les 2 026 premières (numérotées de 1 à 2 026), le serveur 0 a-t-il reçues ?

Voir la réponseMasquer la réponse de l'exercice 4

1. 22 + 29 = 51 et 51 = 24 × 2 + 3, donc 51 ≡ 3 [24]. Le traitement se termine à 3 h, deux jours plus tard (le surlendemain).
2. 2 026 = 3 × 675 + 1 : la requête 2 026 part vers le serveur 1. Le serveur 0 reçoit les requêtes de numéro multiple de 3 : 3, 6, …, 2 025, soit 2 025 ÷ 3 = 675 requêtes.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 5 sur 5 Clés de contrôle Réussi À revoir

1. Calcule la clé du numéro de sécurité sociale fictif 2 69 05 49 588 157 (on donne N mod 97 = 17, où N = 2 690 549 588 157).
2. Calcule le chiffre de contrôle du code EAN-13 dont les douze premiers chiffres sont 978274605000.

Voir la réponseMasquer la réponse de l'exercice 5

1. Clé = 97 − 17 = 80.
2. Rangs impairs (poids 1) : 9, 8, 7, 6, 5, 0 → somme 35. Rangs pairs (poids 3) : 7, 2, 4, 0, 0, 0 → somme 13, soit 39. Total : 35 + 39 = 74 ≡ 4 [10]. Il faut ajouter 6 pour atteindre 80, un multiple de 10. Le chiffre de contrôle est 6.

Tu avais trouvé ?

Oui, j'avais bonPas encore