I. Motivation : l'arithmétique des restes
Nous savons depuis la division euclidienne que tout entier \(a\) divisé par \(n\) donne un reste \(r \in \{0, 1, \ldots, n-1\}\). L'idée des congruences est de classifier les entiers selon leur reste et de faire de l'arithmétique avec ces classes.
.png)
II. Définition et notation
Soient \(a\), \(b\) deux entiers et \(n \geq 2\) un entier. On dit que \(a\) est congru à \(b\) modulo \(n\), et on écrit : \[a \equiv b \pmod{n}\] si \(n\) divise \(a - b\), c'est-à-dire s'il existe un entier \(k\) tel que \(a - b = kn\).
Autrement dit : \(a \equiv b \pmod{n}\) si et seulement si \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
Écrivons \(a = nq_1 + r\) et \(b = nq_2 + r\) avec le même reste \(r\). Alors \(a - b = n(q_1 - q_2)\), donc \(n \mid (a-b)\) : les deux formulations sont bien équivalentes.
a) \(17 \equiv 5 \pmod{6}\) car \(17 - 5 = 12 = 6 \times 2\). ✓
b) \(100 \equiv 2 \pmod{7}\) car \(100 - 2 = 98 = 7 \times 14\). ✓ (Lundi dans 100 jours = mercredi)
c) \(38 \equiv 3 \pmod{5}\) car \(38 = 5 \times 7 + 3\), reste = 3. ✓
d) \(25 \not\equiv 4 \pmod{7}\) car \(25 - 4 = 21 = 7 \times 3\)… En fait si, \(25 \equiv 4 \pmod{7}\) ! ✓
III. La relation de congruence est une relation d'équivalence
La congruence modulo \(n\) est une relation d'équivalence :
- Réflexivité : \(a \equiv a \pmod{n}\) (car \(n \mid 0\)).
- Symétrie : si \(a \equiv b \pmod{n}\), alors \(b \equiv a \pmod{n}\).
- Transitivité : si \(a \equiv b\) et \(b \equiv c \pmod{n}\), alors \(a \equiv c \pmod{n}\).
Une horloge réalise l'arithmétique modulo 12 : 13h, 25h, 37h pointent toutes vers le même chiffre que 1h.
IV. Propriétés de calcul des congruences
Le grand intérêt des congruences est qu'on peut faire des calculs algébriques avec elles, presque comme avec des égalités.
Si \(a \equiv b \pmod{n}\) et \(c \equiv d \pmod{n}\), alors :
- Addition : \(a + c \equiv b + d \pmod{n}\)
- Soustraction : \(a - c \equiv b - d \pmod{n}\)
- Multiplication : \(a \times c \equiv b \times d \pmod{n}\)
- Puissance : \(a^k \equiv b^k \pmod{n}\) pour tout entier \(k \geq 0\)
On suppose \(a = b + kn\) et \(c = d + ln\) pour certains entiers \(k, l\).
\(ac = (b+kn)(d+ln) = bd + bln + knd + kln^2\)
\(= bd + n(bl + kd + kln)\)
Donc \(n \mid (ac - bd)\), soit \(ac \equiv bd \pmod{n}\). \(\square\)
On cherche le reste de \(7^{100}\) dans la division par 5.
D'abord : \(7 \equiv 2 \pmod{5}\)
Donc : \(7^{100} \equiv 2^{100} \pmod{5}\)
Calculons les puissances de 2 mod 5 :
\(2^1 \equiv 2, \quad 2^2 \equiv 4, \quad 2^3 \equiv 3, \quad 2^4 \equiv 1 \pmod{5}\)
Le cycle se répète avec période 4. \(100 = 4 \times 25\), donc \(2^{100} = (2^4)^{25} \equiv 1^{25} = 1 \pmod{5}\).
Aujourd'hui c'est lundi (notons lundi = 1, mardi = 2, …, dimanche = 0 mod 7).
\(365 = 7 \times 52 + 1\), donc \(365 \equiv 1 \pmod{7}\)
Dans 365 jours, on sera \(1 + 1 = 2 \equiv 2 \pmod{7}\) : ce sera un mardi.
Dans 1 000 jours ? \(1000 = 7 \times 142 + 6\), donc \(1000 \equiv 6 \pmod{7}\) : ce sera \(1 + 6 = 7 \equiv 0 \pmod{7}\) : un dimanche.
V. Classes de congruence
Pour un entier \(a\) et un modulo \(n\), la classe de congruence de \(a\) modulo \(n\) est l'ensemble de tous les entiers congrus à \(a\) modulo \(n\) : \[\bar{a} = \{a + kn \mid k \in \mathbb{Z}\} = \{\ldots, a-2n, a-n, a, a+n, a+2n, \ldots\}\]
Il y a exactement \(n\) classes de congruence modulo \(n\), notées \(\bar{0}, \bar{1}, \ldots, \overline{n-1}\). Ensemble, elles forment une partition de \(\mathbb{Z}\).
Il y a exactement 3 classes de congruence modulo 3 :
\(\bar{0} = \{\ldots, -6, -3, 0, 3, 6, 9, 12, \ldots\}\) : multiples de 3
\(\bar{1} = \{\ldots, -5, -2, 1, 4, 7, 10, 13, \ldots\}\) : reste 1 mod 3
\(\bar{2} = \{\ldots, -4, -1, 2, 5, 8, 11, 14, \ldots\}\) : reste 2 mod 3
Tout entier appartient à exactement l'une de ces trois classes.
VI. Critères de divisibilité revisités
Les critères de divisibilité de la leçon 1 se retrouvent naturellement grâce aux congruences.
Soit \(n = \overline{a_k a_{k-1} \cdots a_1 a_0}\) l'écriture décimale d'un entier (\(a_0\) = chiffre des unités).
- Puisque \(10 \equiv 0 \pmod{2}\) et \(\pmod{5}\) : \(n \equiv a_0 \pmod{2}\) et \(\pmod{5}\).
- Puisque \(10 \equiv 1 \pmod{9}\) : \(n \equiv a_0 + a_1 + \cdots + a_k \pmod{9}\).
- Puisque \(10 \equiv 1 \pmod{3}\) : \(n \equiv a_0 + a_1 + \cdots + a_k \pmod{3}\).
- Puisque \(10 \equiv -1 \pmod{11}\) : \(n \equiv a_0 - a_1 + a_2 - \cdots \pmod{11}\) (règle de l'alternance).
On écrit \(n = a_0 + 10 a_1 + 100 a_2 + \cdots = \sum_{i} a_i \cdot 10^i\).
Or \(10 \equiv 1 \pmod 9\), donc \(10^i \equiv 1^i = 1 \pmod 9\) pour tout \(i\).
Donc \(n \equiv \sum_i a_i \cdot 1 = \sum_i a_i \pmod 9\). \(\square\)
On calcule la somme alternée des chiffres (en commençant par les unités) :
Chiffres de 918 291 : 9, 1, 8, 2, 9, 1 (de gauche à droite).
Somme alternée (depuis les unités, droite vers gauche) : \(1 - 9 + 2 - 8 + 1 - 9 = -22\)
\(-22 \equiv 0 \pmod{11}\) car \(-22 = 11 \times (-2)\).
VII. Résolution de congruences simples
On peut résoudre des équations du type \(ax \equiv b \pmod{n}\) — c'est l'analogue des équations linéaires, mais dans l'arithmétique modulaire.
L'équation \(ax \equiv b \pmod{n}\) admet des solutions si et seulement si \(\text{PGCD}(a, n) \mid b\).
En particulier, si \(\text{PGCD}(a, n) = 1\) (c'est-à-dire \(a\) et \(n\) sont premiers entre eux), l'équation admet une solution unique modulo \(n\).
\(\text{PGCD}(3, 7) = 1\) (car 7 est premier), donc il existe une unique solution modulo 7.
On cherche l'inverse de 3 modulo 7 : quel entier \(y\) vérifie \(3y \equiv 1 \pmod{7}\) ?
On teste : \(3 \times 1 = 3\), \(3 \times 2 = 6\), \(3 \times 3 = 9 \equiv 2\), \(3 \times 4 = 12 \equiv 5\), \(3 \times 5 = 15 \equiv 1\) ✓
Donc \(3^{-1} \equiv 5 \pmod{7}\).
La solution est : \(x \equiv 5 \times 2 = 10 \equiv 3 \pmod{7}\).
Vérification : \(3 \times 3 = 9 = 7 \times 1 + 2 \equiv 2 \pmod 7\). ✓
\(\text{PGCD}(4, 10) = 2\). On vérifie que \(2 \mid 6\) : oui. Il y aura \(2\) solutions modulo 10.
On simplifie en divisant tout par 2 : \(2x \equiv 3 \pmod{5}\).
\(\text{PGCD}(2,5) = 1\), inverse de 2 mod 5 : \(2 \times 3 = 6 \equiv 1 \pmod 5\), donc \(2^{-1} \equiv 3\).
\(x \equiv 3 \times 3 = 9 \equiv 4 \pmod{5}\).
Les solutions modulo 10 sont : \(x \equiv 4 \pmod{10}\) et \(x \equiv 9 \pmod{10}\).
VIII. Application burkinabè — Calendriers et marchés
Dans la région du Sahel, le marché de Gorom-Gorom suit un cycle traditionnel de 5 jours. Le dernier marché a eu lieu un mercredi. En numérotant les jours de la semaine de 0 (lundi) à 6 (dimanche) :
Mercredi = 2. Prochain marché dans 5 jours : \(2 + 5 = 7 \equiv 0 \pmod 7\) → lundi.
Marché suivant : \(0 + 5 = 5 \pmod 7\) → samedi.
Le cycle lundi / samedi / jeudi / mardi / dimanche / vendredi / mercredi se répète avec période \(\text{PPCM}(5, 7) = 35\) jours.
Les codes-barres EAN-13 (sur tous les produits vendus au Burkina Faso) utilisent un chiffre de contrôle calculé modulo 10. Pour un code \(d_1 d_2 \cdots d_{12}\), le 13\(^\text{e}\) chiffre \(d_{13}\) vérifie : \[(d_1 + d_3 + d_5 + d_7 + d_9 + d_{11}) + 3(d_2 + d_4 + d_6 + d_8 + d_{10} + d_{12}) + d_{13} \equiv 0 \pmod{10}\]
Vérifions le code 3 017620 425400 :
Positions impaires (1,3,5,7,9,11) : 3, 1, 6, 0, 2, 5 → somme = 17
Positions paires (2,4,6,8,10,12) : 0, 7, 2, 4, 5, 0 → somme = 18, × 3 = 54
Total : \(17 + 54 = 71\). Chiffre de contrôle : \(d_{13} \equiv -71 \equiv -1 \equiv 9 \pmod{10}\) — mais ici \(d_{13} = 0\).
Réessayons : \(71 + 0 = 71 \not\equiv 0\). Ce code est fictif — en vrai, les 13 chiffres doivent donner un total congru à 0.
Dans un village du Plateau Central, deux marchés coexistent : le marché A se tient tous les 4 jours, le marché B tous les 6 jours. Ils ont lieu simultanément aujourd'hui (jour 0).
- a) Après combien de jours auront-ils à nouveau lieu le même jour ? (Calculer \(\text{PPCM}(4,6)\) par congruences.)
- b) Si aujourd'hui est un lundi (jour 1 de la semaine, mod 7), quel jour de la semaine sera la prochaine coïncidence ?
- c) Un commerçant veut trouver un jour \(x\) tel que \(x \equiv 2 \pmod{4}\) (deux jours après le marché A) et \(x \equiv 3 \pmod{6}\) (trois jours après le marché B). Résoudre ce système de congruences.
- d) La fête annuelle du village dure 3 jours consécutifs à partir du jour 100. Ces jours tombent-ils un jour de marché A, B, ou les deux ?
✏️ Exercices d'application
- a) Vérifier que \(123 \equiv 3 \pmod{10}\), \(123 \equiv 3 \pmod{6}\), \(123 \equiv 3 \pmod{4}\).
- b) Calculer les restes de \(2^{10}\), \(3^{20}\) et \(4^{15}\) modulo 7.
- c) Quel est le reste de \(2025^{2025}\) modulo 9 ?
b) \(2^1 \equiv 2, 2^2 \equiv 4, 2^3 \equiv 1 \pmod 7\) (cycle 3). \(10 = 3\times3+1\), donc \(2^{10} \equiv 2^1 = 2 \pmod 7\).
\(3^1 \equiv 3, 3^2 \equiv 2, 3^3 \equiv 6, 3^4 \equiv 4, 3^5 \equiv 5, 3^6 \equiv 1 \pmod 7\) (cycle 6). \(20 = 6\times3+2\), donc \(3^{20} \equiv 3^2 = 2 \pmod 7\).
\(4 \equiv 4 \pmod 7\). \(4^2 = 16 \equiv 2\), \(4^3 \equiv 8 \equiv 1 \pmod 7\) (cycle 3). \(15 = 3 \times 5\), donc \(4^{15} = (4^3)^5 \equiv 1 \pmod 7\).
c) \(2025 = 9 \times 225\), donc \(2025 \equiv 0 \pmod 9\). Donc \(2025^{2025} \equiv 0^{2025} = 0 \pmod 9\).
Utiliser le critère modulo 11 (somme alternée des chiffres) pour déterminer lesquels sont divisibles par 11 :
- a) 74 536
- b) 120 978
- c) 1 234 567 890
b) 120 978 : \(8 - 7 + 9 - 0 + 2 - 1 = 11 \equiv 0 \pmod{11}\). Divisible par 11.
c) 1 234 567 890 : \(0 - 9 + 8 - 7 + 6 - 5 + 4 - 3 + 2 - 1 = -5 \not\equiv 0 \pmod{11}\). Non divisible par 11.
- a) Résoudre \(5x \equiv 3 \pmod{7}\).
- b) Résoudre \(6x \equiv 4 \pmod{8}\).
- c) Montrer que \(3x \equiv 4 \pmod{9}\) n'a pas de solution.
\(x \equiv 3\times3 = 9 \equiv 2 \pmod 7\). Vérification : \(5\times2=10\equiv3\) ✓
b) \(\text{PGCD}(6,8)=2\) et \(2 \mid 4\). On divise par 2 : \(3x \equiv 2 \pmod 4\).
\(\text{PGCD}(3,4)=1\). Inverse de 3 mod 4 : \(3\times3=9\equiv1\), donc \(3^{-1}\equiv3\).
\(x \equiv 3\times2=6\equiv2\pmod4\). Solutions mod 8 : \(x\equiv2\pmod8\) et \(x\equiv6\pmod8\).
c) \(\text{PGCD}(3,9)=3\) et \(3 \nmid 4\) (car \(4 = 3\times1+1\)). La condition \(\text{PGCD}(a,n) \mid b\) n'est pas satisfaite : aucune solution.
Une année est bissextile si elle est divisible par 4, sauf si elle est divisible par 100 mais non par 400.
- a) Exprimer la condition "divisible par 4" en termes de congruences.
- b) Parmi les années 1900, 2000, 2024, 2100, lesquelles sont bissextiles ?
- c) Le 1er janvier 2025 est un mercredi (jour 3, avec lundi = 1). Quel jour sera le 1er janvier 2026 ? (2025 n'est pas bissextile, donc 365 jours. \(365 \equiv ? \pmod 7\))
b) 1900 : \(1900 = 4\times475\) → divisible par 4. Mais \(1900 = 100\times19\) → divisible par 100. Et \(1900 \not\equiv 0 \pmod{400}\) (\(1900 = 400\times4+300\)). Donc 1900 n'est pas bissextile.
2000 : divisible par 400 → bissextile.
2024 : \(2024 = 4\times506\) → divisible par 4. \(2024\div100=20{,}24\) → non divisible par 100. Bissextile.
2100 : divisible par 100 mais \(2100\div400=5{,}25\) → non par 400. Non bissextile.
c) \(365 = 7\times52+1\), donc \(365 \equiv 1 \pmod 7\).
Le 1er janvier 2026 sera : \(3 + 1 = 4 \equiv 4 \pmod 7\) → jeudi.
Calculer les restes suivants en utilisant les propriétés des congruences :
- a) Reste de \(13^{50}\) dans la division par 6.
- b) Reste de \(7^{200} + 3^{100}\) dans la division par 5.
- c) Dernier chiffre de \(9^{2026}\) (c'est-à-dire \(9^{2026} \pmod{10}\)).
b) \(7 \equiv 2 \pmod 5\). Cycle de 2 mod 5 : \(2^1=2, 2^2=4, 2^3=3, 2^4=1\) (cycle 4). \(200 = 4\times50\), donc \(7^{200} \equiv 1 \pmod 5\).
\(3^1=3, 3^2=4, 3^3=2, 3^4=1 \pmod 5\) (cycle 4). \(100=4\times25\), donc \(3^{100} \equiv 1 \pmod 5\).
\(7^{200}+3^{100} \equiv 1+1=2 \pmod 5\). Reste = 2.
c) \(9^1=9, 9^2=81\equiv1\pmod{10}\) (cycle 2). \(2026 = 2\times1013\) → \(9^{2026}=(9^2)^{1013}\equiv1^{1013}=1\pmod{10}\). Dernier chiffre = 1.
Récapitulatif — Congruences
- Définition : \(a \equiv b \pmod n\) si \(n \mid (a-b)\), i.e. \(a\) et \(b\) ont le même reste mod \(n\).
- Relation d'équivalence : réflexive, symétrique, transitive.
- Compatibilité : on peut additionner, soustraire, multiplier et élever à une puissance des congruences membres à membres.
- Calcul de \(a^k \pmod n\) : chercher le cycle des puissances de \(a\) mod \(n\), puis utiliser la division euclidienne de \(k\) par la période.
- Classes de congruence : il y a exactement \(n\) classes mod \(n\), formant une partition de \(\mathbb{Z}\).
- Critères de divisibilité : découlent directement des congruences de 10 (mod 2, 3, 5, 9, 11).
- Équations \(ax \equiv b \pmod n\) : solution si et seulement si \(\text{PGCD}(a,n) \mid b\). Solution unique mod \(n\) si \(\text{PGCD}(a,n)=1\).
- Applications : calendriers, jours de la semaine, codes-barres EAN, cryptographie, horloges.