Rédigé et vérifié par un professeur diplômé de l’École Polytechnique, avec un niveau de rigueur pensé pour le lycée et la prépa. Découvrir le professeur
Comment déterminer le dernier chiffre de \(7^{2024}\) sans calculatrice ? Les congruences te donnent la réponse en quelques lignes. Au programme de Terminale Maths Expertes et de CPGE, les congruences sont l’outil de l’arithmétique qui permet de raisonner uniquement sur les restes. Tu trouveras ici la définition complète, toutes les propriétés avec démonstrations, des tableaux de congruence, les méthodes de calcul pas à pas et 5 exercices corrigés.
Conforme au programme officiel de Terminale Maths Expertes 2025-2026.
I. Définition d’une congruence modulo n
A. Définition formelle et intuitive
En arithmétique, les congruences permettent de classer les entiers selon leur reste dans la division euclidienne par un entier fixé. Plutôt que de s’intéresser à la valeur exacte d’un nombre, on s’intéresse uniquement à son reste — ce qui simplifie considérablement les calculs.
Définition — Congruence modulo n
Soit \(n\) un entier naturel non nul. On dit que deux entiers \(a\) et \(b\) sont congrus modulo \(n\) lorsque \(n\) divise leur différence \(b – a\).
On écrit alors :
\(a \equiv b \pmod{n}\)
ce qui signifie : il existe un entier \(k \in \mathbb{Z}\) tel que \(b – a = kn\).
Reformulation intuitive : deux entiers sont congrus modulo \(n\) si et seulement s’ils ont le même reste dans la division euclidienne par \(n\). C’est cette caractérisation qui rend les congruences si pratiques : pour trouver le reste de \(a\) dans la division par \(n\), il suffit de remplacer \(a\) par n’importe quel entier congru plus simple à manipuler.
Reformulation avec la division euclidienne
Si \(a = nq_1 + r_1\) et \(b = nq_2 + r_2\) avec \(0 \leq r_1, r_2\) < \(n\), alors :
\(a \equiv b \pmod{n} \iff r_1 = r_2\)
Autrement dit, \(a\) et \(b\) sont congrus modulo \(n\) si et seulement s’ils ont le même reste dans la division euclidienne par \(n\).
B. Notation et symbole de congruence
Le symbole de congruence est \(\equiv\) (à ne pas confondre avec le signe \(=\)). Plusieurs notations coexistent :
- \(a \equiv b \pmod{n}\) — notation internationale, la plus fréquente en Maths Expertes.
- \(a \equiv b \ [n]\) — notation française courante dans les manuels du lycée.
Les deux se lisent « \(a\) est congru à \(b\) modulo \(n\) ». Dans cet article, on utilise principalement la première notation.
Attention : le symbole \(\equiv\) n’est pas un signe d’égalité. L’écriture \(17 \equiv 2 \pmod{5}\) ne signifie pas que \(17 = 2\). Elle signifie que \(17\) et \(2\) ont le même reste dans la division par \(5\).
Où étudie-t-on les congruences ? Les congruences ne sont pas au programme avant la Terminale. Plus précisément :
- En 5ème–3ème : tu travailles avec la divisibilité, les critères de divisibilité, le PGCD et les nombres premiers, mais sans formaliser les congruences.
- En Terminale Maths Expertes : c’est le chapitre principal d’arithmétique — définition, propriétés, applications.
- En CPGE (MPSI, PCSI) : les congruences sont approfondies avec l’anneau \(\mathbb{Z}/n\mathbb{Z}\), le théorème chinois des restes et les applications à la cryptographie (voir la section CPGE en fin d’article).
C. Premiers exemples
Exemple 1 : Montrer que \(17 \equiv 2 \pmod{5}\).
Méthode 1 (définition) : \(17 – 2 = 15 = 5 \times 3\), donc \(5 \mid (17 – 2)\). Ainsi \(17 \equiv 2 \pmod{5}\).
Méthode 2 (restes) : \(17 = 5 \times 3 + \mathbf{2}\) et \(2 = 5 \times 0 + \mathbf{2}\). Les deux restes sont égaux à \(2\), donc \(17 \equiv 2 \pmod{5}\).
Exemple 2 : Est-il vrai que \(100 \equiv 4 \pmod{12}\) ?
\(100 – 4 = 96 = 12 \times 8\). Oui, \(12 \mid 96\), donc \(100 \equiv 4 \pmod{12}\).
Vérification par les restes : \(100 = 12 \times 8 + \mathbf{4}\). Le reste est bien \(4\). ✓
Exemple 3 (négatif) : Déterminer \(r\) tel que \(-7 \equiv r \pmod{3}\) avec \(0 \leq r\) < \(3\).
\(-7 = 3 \times (-3) + 2\), donc le reste est \(r = 2\).
Ainsi \(-7 \equiv 2 \pmod{3}\).
II. Propriétés des congruences
La puissance des congruences vient de leur compatibilité avec les opérations arithmétiques. Tu peux additionner, soustraire, multiplier et élever à une puissance des congruences — exactement comme tu le ferais avec des égalités. C’est ce qui rend le calcul modulaire si efficace.
A. Compatibilité avec l’addition et la soustraction
Propriété — Somme et différence de congruences
Soit \(n \in \mathbb{N}^*\). Si \(a \equiv b \pmod{n}\) et \(c \equiv d \pmod{n}\), alors :
\(a + c \equiv b + d \pmod{n} \quad \text{et} \quad a – c \equiv b – d \pmod{n}\)
Démonstration (au programme)
Par hypothèse, \(n \mid (b – a)\) et \(n \mid (d – c)\). Donc il existe \(k, k^\prime \in \mathbb{Z}\) tels que \(b – a = kn\) et \(d – c = k^\prime n\).
En additionnant : \((b + d) – (a + c) = (k + k^\prime)n\), ce qui signifie que \(n \mid \bigl((b + d) – (a + c)\bigr)\), donc \(a + c \equiv b + d \pmod{n}\).
La preuve pour la soustraction est identique en remplaçant \(+\) par \(–\). \(\blacksquare\)
Application : On sait que \(17 \equiv 2 \pmod{5}\) et \(23 \equiv 3 \pmod{5}\). Alors :
\(17 + 23 = 40 \equiv 2 + 3 = 5 \equiv 0 \pmod{5}\)
En effet, \(40 = 5 \times 8\) : le résultat est bien divisible par \(5\). ✓
B. Compatibilité avec la multiplication
Propriété — Produit de congruences
Si \(a \equiv b \pmod{n}\) et \(c \equiv d \pmod{n}\), alors :
\(a \times c \equiv b \times d \pmod{n}\)
Démonstration (au programme)
On écrit \(a = b + kn\) et \(c = d + k^\prime n\) avec \(k, k^\prime \in \mathbb{Z}\).
Alors : \(ac = (b + kn)(d + k^\prime n) = bd + bk^\prime n + knd + kk^\prime n^2 = bd + n(bk^\prime + kd + kk^\prime n)\).
Ainsi \(ac – bd = n(bk^\prime + kd + kk^\prime n)\), ce qui donne \(n \mid (ac – bd)\), donc \(ac \equiv bd \pmod{n}\). \(\blacksquare\)
Cette propriété est fondamentale : elle permet de remplacer chaque facteur par son reste avant de multiplier, ce qui réduit considérablement la taille des calculs.
C. Puissance modulaire
Propriété — Puissance d’une congruence
Si \(a \equiv b \pmod{n}\), alors pour tout entier naturel \(k\) :
\(a^k \equiv b^k \pmod{n}\)
C’est un corollaire immédiat de la compatibilité avec la multiplication : il suffit d’appliquer la propriété précédente \(k\) fois avec \(c = a\) et \(d = b\).
Méthode clé : pour calculer \(a^k \pmod{n}\), commence par réduire \(a\) modulo \(n\) (en le remplaçant par son reste), puis calcule la puissance sur ce reste. C’est beaucoup plus rapide que de calculer \(a^k\) puis de diviser par \(n\).
Attention — Pas de division !
On ne peut pas diviser une congruence par un entier quelconque. Par exemple, \(6 \equiv 0 \pmod{6}\), mais si l’on « divise » par \(2\), on obtient \(3 \equiv 0 \pmod{6}\), ce qui est faux (\(6\) ne divise pas \(3\)).
La simplification n’est possible que sous condition : si \(ca \equiv cb \pmod{n}\) et \(\mathrm{pgcd}(c, n) = 1\), alors \(a \equiv b \pmod{n}\). La condition « \(c\) et \(n\) premiers entre eux » est indispensable.
D. Tableau récapitulatif des propriétés
| Propriété | Énoncé | Condition |
|---|---|---|
| Réflexivité | \(a \equiv a \pmod{n}\) | Aucune |
| Symétrie | \(a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}\) | Aucune |
| Transitivité | \(a \equiv b\) et \(b \equiv c \Rightarrow a \equiv c \pmod{n}\) | Aucune |
| Addition | \(a \equiv b\) et \(c \equiv d \Rightarrow a + c \equiv b + d \pmod{n}\) | Aucune |
| Multiplication | \(a \equiv b\) et \(c \equiv d \Rightarrow ac \equiv bd \pmod{n}\) | Aucune |
| Puissance | \(a \equiv b \Rightarrow a^k \equiv b^k \pmod{n}\) | \(k \in \mathbb{N}\) |
| Simplification | \(ca \equiv cb \pmod{n} \Rightarrow a \equiv b \pmod{n}\) | \(\mathrm{pgcd}(c, n) = 1\) |
Fiche de révision — Congruences (Maths Expertes)
Définition, toutes les propriétés, méthode de calcul des puissances modulaires et pièges à éviter. L’essentiel du cours en 1 page.
📄 Télécharger la fiche PDFPour réviser efficacement avant un DS ou le bac
III. Tableaux de congruence modulo n
Un tableau de congruence est un outil concret pour visualiser les résultats des opérations modulo \(n\). Il est particulièrement utile pour identifier les éléments inversibles et les régularités du calcul modulaire.
A. Comment construire un tableau de congruence
Pour construire le tableau de multiplication modulo \(n\), il suffit de :
- Lister les restes possibles : \(0, 1, 2, \ldots, n-1\).
- Calculer chaque produit \(a \times b\) et prendre le reste dans la division par \(n\).
- Repérer les cases contenant \(1\) : elles indiquent les paires d’inverses modulaires.
Voyons cela sur des exemples concrets.
B. Tableaux modulo 2, 3 et 5
Modulo 2 : les entiers se répartissent en deux classes — les nombres pairs (reste \(0\)) et les nombres impairs (reste \(1\)). Le tableau de multiplication est trivial : seul \(1 \times 1 \equiv 1 \pmod{2}\).
Tableau de multiplication modulo 3 :
| \(\times\) | \(0\) | \(1\) | \(2\) |
|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) |
| \(1\) | \(0\) | \(1\) | \(2\) |
| \(2\) | \(0\) | \(2\) | \(1\) |
Lecture : la case \((2, 2)\) contient \(1\) car \(2 \times 2 = 4 \equiv 1 \pmod{3}\). Cela signifie que \(2\) est son propre inverse modulo \(3\).
Tableau de multiplication modulo 5 :
| \(\times\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) |
|---|---|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(1\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) |
| \(2\) | \(0\) | \(2\) | \(4\) | \(1\) | \(3\) |
| \(3\) | \(0\) | \(3\) | \(1\) | \(4\) | \(2\) |
| \(4\) | \(0\) | \(4\) | \(3\) | \(2\) | \(1\) |
Lecture rapide du tableau modulo 5 :
- Chaque ligne non nulle contient tous les restes \(0, 1, 2, 3, 4\) exactement une fois — c’est un signe que \(5\) est un nombre premier.
- Les inversibles se lisent sur les cases contenant \(1\) : l’inverse de \(2\) est \(3\) (car \(2 \times 3 = 6 \equiv 1 \pmod{5}\)), et \(4\) est son propre inverse (car \(4 \times 4 = 16 \equiv 1 \pmod{5}\)).
IV. Méthodes de calcul et exemples résolus
Savoir utiliser les congruences, c’est avant tout maîtriser trois techniques de calcul. Chacune répond à un type de problème précis.
A. Réduction modulo n
La technique la plus élémentaire : pour calculer \(a \pmod{n}\), on effectue la division euclidienne de \(a\) par \(n\) et on garde le reste.
Exemple : Calculer \(2024 \pmod{7}\).
\(2024 = 7 \times 289 + 1\), donc \(2024 \equiv 1 \pmod{7}\).
Vérifie : \(7 \times 289 = 2023\), et \(2024 – 2023 = 1\). ✓
Astuce pour les entiers négatifs : \(-7 = 3 \times (-3) + 2\), donc \(-7 \equiv 2 \pmod{3}\). On ajoute un multiple de \(n\) pour obtenir un reste positif.
B. Calcul de puissances modulaires
C’est la technique phare des congruences — celle qui permet de répondre à la question d’ouverture. La stratégie repose sur deux principes :
- Réduire la base : remplacer \(a\) par un entier congru plus simple (souvent négatif !).
- Chercher une puissance qui donne \(1\) ou \(-1\) : cela crée un cycle qui raccourcit le calcul.
Exemple — Quel est le dernier chiffre de \(7^{2024}\) ?
Le dernier chiffre, c’est le reste modulo \(10\). Calculons \(7^{2024} \pmod{10}\).
Étape 1 : Calculer les premières puissances de \(7\) modulo \(10\) :
- \(7^1 \equiv 7 \pmod{10}\)
- \(7^2 = 49 \equiv 9 \pmod{10}\)
- \(7^3 = 7 \times 49 \equiv 7 \times 9 = 63 \equiv 3 \pmod{10}\)
- \(7^4 \equiv 7 \times 3 = 21 \equiv 1 \pmod{10}\)
Étape 2 : On a trouvé que \(7^4 \equiv 1 \pmod{10}\). La suite est cyclique de période \(4\).
Étape 3 : Effectuer la division euclidienne de l’exposant par la période : \(2024 = 4 \times 506\), donc :
\(7^{2024} = (7^4)^{506} \equiv 1^{506} = 1 \pmod{10}\)
Conclusion : le dernier chiffre de \(7^{2024}\) est \(1\).
Exemple — Reste de \(3^{100}\) dans la division par \(7\)
Étape 1 : Chercher un cycle.
- \(3^1 \equiv 3 \pmod{7}\)
- \(3^2 \equiv 2 \pmod{7}\)
- \(3^3 \equiv 6 \equiv -1 \pmod{7}\)
Étape 2 : On a \(3^3 \equiv -1 \pmod{7}\), donc \(3^6 \equiv (-1)^2 = 1 \pmod{7}\). La période est \(6\).
Étape 3 : \(100 = 6 \times 16 + 4\), donc :
\(3^{100} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 3^4 \equiv 3^4 \pmod{7}\)
\(3^4 = 81 = 7 \times 11 + 4\), donc \(3^{100} \equiv 4 \pmod{7}\).
Le reste est \(4\).
C. Recherche de l’inverse modulaire
L’entier \(a\) admet un inverse modulo \(n\) (c’est-à-dire un entier \(b\) tel que \(ab \equiv 1 \pmod{n}\)) si et seulement si \(\mathrm{pgcd}(a, n) = 1\) — autrement dit, si \(a\) et \(n\) sont premiers entre eux.
Méthode pour trouver l’inverse :
- Vérifier que \(\mathrm{pgcd}(a, n) = 1\).
- Utiliser l’identité de Bézout : trouver \(u, v \in \mathbb{Z}\) tels que \(au + nv = 1\).
- Alors \(u\) est l’inverse de \(a\) modulo \(n\) (car \(au \equiv 1 \pmod{n}\)).
Exemple : Trouver l’inverse de \(3\) modulo \(7\).
\(\mathrm{pgcd}(3, 7) = 1\) ✓. On cherche \(u\) tel que \(3u \equiv 1 \pmod{7}\).
Par essai : \(3 \times 5 = 15 = 2 \times 7 + 1\), donc \(3 \times 5 \equiv 1 \pmod{7}\).
L’inverse de \(3\) modulo \(7\) est \(5\).
On le retrouve dans le tableau de multiplication modulo \(5\) : la case \((3, 5)\) vaut \(1\).
D. Quand utiliser les congruences ?
En arithmétique, plusieurs outils coexistent : division euclidienne, congruences, théorème de Bézout et théorème de Gauss. Comment choisir le bon ? Voici un tableau de décision :
| Outil | Quand l’utiliser | Exemple type |
|---|---|---|
| Division euclidienne | Trouver le quotient et le reste | « Quel est le reste de 2024 divisé par 7 ? » |
| Congruences | Travailler uniquement avec les restes, grandes puissances, critères de divisibilité | « Quel est le reste de \(7^{2024}\) divisé par 10 ? » |
| Théorème de Bézout | Montrer que deux nombres sont premiers entre eux | « Montrer que \(\mathrm{pgcd}(2n+1, 3n+2) = 1\) » |
| Théorème de Gauss | Déduire \(a \mid c\) sachant \(a \mid bc\) et \(\mathrm{pgcd}(a, b) = 1\) | « Si \(p \mid ab\) et \(p\) premier avec \(a\), montrer que \(p \mid b\) » |
Règle d’or : dès qu’un énoncé parle de « reste » ou de « dernier(s) chiffre(s) », pense congruences. Si l’énoncé demande une preuve de divisibilité avec une condition « premiers entre eux », pense Gauss.
V. Pièges et erreurs courantes
Voici les erreurs les plus fréquentes chez les élèves de Maths Expertes et de prépa. Pour chaque piège, tu trouveras une « copie fautive » avec le diagnostic de l’erreur et la correction.
Piège 1 — Confondre congruence et égalité
❌ Copie fautive : « \(17 \equiv 2 \pmod{5}\) donc \(17 = 2\). »
Diagnostic : l’élève traite \(\equiv\) comme \(=\). Une congruence est une relation d’équivalence sur les restes, pas une égalité. \(17\) et \(2\) ont le même reste modulo \(5\), mais ce ne sont pas le même nombre.
✅ Correction : « \(17 \equiv 2 \pmod{5}\), c’est-à-dire \(5 \mid (17 – 2)\). »
Piège 2 — Diviser une congruence sans vérifier la condition
❌ Copie fautive : « \(12 \equiv 6 \pmod{6}\) donc, en divisant par \(6\) : \(2 \equiv 1 \pmod{6}\). »
Diagnostic : \(6\) ne divise pas \(2 – 1 = 1\), le résultat est faux. L’erreur vient de ce que \(\mathrm{pgcd}(6, 6) = 6 \neq 1\) — la condition de simplification n’est pas remplie.
✅ Correction : \(12 \equiv 6 \pmod{6}\) est vrai (\(6 \mid 6\)). On peut simplifier par \(2\) car \(\mathrm{pgcd}(2, 6) = 2\), en ajustant le modulo : \(6 \equiv 3 \pmod{3}\). C’est la règle de simplification avec changement de modulo.
Piège 3 — Oublier de traiter les restes négatifs
❌ Copie fautive : « \(3^3 = 27 \equiv -1 \pmod{7}\) donc \(3^6 \equiv -1 \pmod{7}\). »
Diagnostic : l’élève a élevé au carré le mauvais membre. \(3^6 = (3^3)^2 \equiv (-1)^2 = 1 \pmod{7}\), pas \(-1\). Se souvenir que \((-1)^2 = 1\) !
✅ Correction : \(3^6 = (3^3)^2 \equiv (-1)^2 = 1 \pmod{7}\).
Piège 4 — Généraliser à tort « \(a \mid bc \Rightarrow a \mid b\) ou \(a \mid c\) »
❌ Copie fautive : « \(6 \mid 12\) et \(12 = 4 \times 3\), donc \(6 \mid 4\) ou \(6 \mid 3\). »
Diagnostic : \(6\) ne divise ni \(4\) ni \(3\). Cette implication n’est valable que si \(a\) est premier avec l’un des facteurs (c’est le théorème de Gauss) ou si \(a\) est un nombre premier (c’est le lemme d’Euclide).
✅ Conclusion : toujours vérifier la condition « premiers entre eux » ou « premier » avant de conclure.
VI. Exercices corrigés
Voici 5 exercices classés par difficulté croissante, du calcul direct (★) aux problèmes de type concours (★★★). Chaque correction détaille la stratégie, pas seulement le résultat.
Exercice 1 — ★ 🟢 Maths Expertes
Calculer le reste de la division euclidienne de \(2024^2 + 3 \times 2024 + 5\) par \(7\).
Voir la correction
Stratégie : réduire \(2024\) modulo \(7\), puis utiliser les propriétés des congruences.
Étape 1 : \(2024 = 7 \times 289 + 1\), donc \(2024 \equiv 1 \pmod{7}\).
Étape 2 : on remplace partout \(2024\) par \(1\) :
\(2024^2 + 3 \times 2024 + 5 \equiv 1^2 + 3 \times 1 + 5 = 9 \pmod{7}\)Étape 3 : \(9 = 7 \times 1 + 2\), donc \(9 \equiv 2 \pmod{7}\).
Conclusion : le reste est \(2\).
Erreur à éviter : calculer \(2024^2\) avant de réduire. C’est un nombre à 7 chiffres — inutilement compliqué !
Exercice 2 — ★ 🟢 Maths Expertes
Montrer que pour tout entier naturel \(n\), le nombre \(n^3 – n\) est divisible par \(6\).
Voir la correction
Stratégie : montrer séparément que \(2 \mid (n^3 – n)\) et \(3 \mid (n^3 – n)\), puis conclure avec le théorème de Gauss (puisque \(\mathrm{pgcd}(2, 3) = 1\)).
Divisibilité par 2 : il y a deux cas possibles modulo \(2\).
- Si \(n \equiv 0 \pmod{2}\) : \(n^3 – n \equiv 0 – 0 = 0 \pmod{2}\). ✓
- Si \(n \equiv 1 \pmod{2}\) : \(n^3 – n \equiv 1 – 1 = 0 \pmod{2}\). ✓
Dans tous les cas, \(2 \mid (n^3 – n)\).
Divisibilité par 3 : trois cas modulo \(3\).
- Si \(n \equiv 0 \pmod{3}\) : \(n^3 – n \equiv 0 – 0 = 0 \pmod{3}\). ✓
- Si \(n \equiv 1 \pmod{3}\) : \(n^3 – n \equiv 1 – 1 = 0 \pmod{3}\). ✓
- Si \(n \equiv 2 \pmod{3}\) : \(n^3 – n \equiv 8 – 2 = 6 \equiv 0 \pmod{3}\). ✓
Dans tous les cas, \(3 \mid (n^3 – n)\).
Conclusion : puisque \(2 \mid (n^3 – n)\) et \(3 \mid (n^3 – n)\) avec \(\mathrm{pgcd}(2, 3) = 1\), on conclut que \(6 \mid (n^3 – n)\).
Erreur à éviter : oublier de justifier que \(\mathrm{pgcd}(2, 3) = 1\) avant de conclure. Sans cette condition, le raisonnement par « morceaux » n’est pas valide.
Exercice 3 — ★★ 🟢 Maths Expertes (type bac)
Déterminer le reste de la division euclidienne de \(2^{100}\) par \(13\).
Voir la correction
Indication : chercher une puissance de \(2\) congrue à \(1\) ou \(-1\) modulo \(13\).
Étape 1 — Chercher le cycle :
- \(2^1 \equiv 2 \pmod{13}\)
- \(2^2 \equiv 4 \pmod{13}\)
- \(2^3 \equiv 8 \pmod{13}\)
- \(2^4 \equiv 16 \equiv 3 \pmod{13}\)
- \(2^5 \equiv 6 \pmod{13}\)
- \(2^6 \equiv 12 \equiv -1 \pmod{13}\)
Étape 2 : \(2^6 \equiv -1 \pmod{13}\), donc \(2^{12} \equiv (-1)^2 = 1 \pmod{13}\). La période est \(12\).
Étape 3 : \(100 = 12 \times 8 + 4\), donc :
\(2^{100} = (2^{12})^{8} \times 2^4 \equiv 1^{8} \times 16 \equiv 3 \pmod{13}\)Le reste est \(3\).
Erreur à éviter : conclure \(2^6 \equiv -1 \pmod{13}\) implique une période de \(6\). C’est faux — la période est \(12\) (le plus petit \(k\) tel que \(2^k \equiv 1\)).
Exercice 4 — ★★★ 🔴 Type concours (CCINP / Mines)
Déterminer tous les entiers \(n\) tels que \(n^2 \equiv 1 \pmod{24}\).
Voir la correction
Stratégie : décomposer le problème modulo \(8\) et modulo \(3\) (car \(24 = 8 \times 3\) et \(\mathrm{pgcd}(8, 3) = 1\)).
Étude modulo 8 :
On teste tous les restes \(r \in \{0, 1, 2, 3, 4, 5, 6, 7\}\) :
- \(0^2 = 0\), \(1^2 = 1\), \(2^2 = 4\), \(3^2 = 9 \equiv 1\), \(4^2 = 16 \equiv 0\), \(5^2 = 25 \equiv 1\), \(6^2 = 36 \equiv 4\), \(7^2 = 49 \equiv 1 \pmod{8}\).
Donc \(n^2 \equiv 1 \pmod{8}\) si et seulement si \(n \equiv 1, 3, 5\) ou \(7 \pmod{8}\), c’est-à-dire si \(n\) est impair.
Étude modulo 3 :
- \(0^2 = 0\), \(1^2 = 1\), \(2^2 = 4 \equiv 1 \pmod{3}\).
Donc \(n^2 \equiv 1 \pmod{3}\) si et seulement si \(n \equiv 1\) ou \(2 \pmod{3}\), c’est-à-dire si \(n\) n’est pas divisible par \(3\).
Conclusion : \(n^2 \equiv 1 \pmod{24}\) si et seulement si \(n\) est impair et non divisible par \(3\).
Les solutions modulo \(24\) sont : \(n \equiv 1, 5, 7, 11, 13, 17, 19\) ou \(23 \pmod{24}\).
Erreur à éviter : oublier de vérifier que \(\mathrm{pgcd}(8, 3) = 1\) avant de séparer le problème en deux. Cette factorisation n’est valide que pour des modulos premiers entre eux.
Exercice 5 — ★★ 🟢 Maths Expertes (application)
a) Montrer que pour tout entier naturel \(n\), on a \(10^n \equiv (-1)^n \pmod{11}\).
b) Soit \(N = a_p a_{p-1} \ldots a_1 a_0\) un entier écrit en base \(10\), c’est-à-dire \(N = a_0 + a_1 \times 10 + a_2 \times 10^2 + \ldots + a_p \times 10^p\). Montrer que \(N \equiv a_0 – a_1 + a_2 – \ldots + (-1)^p a_p \pmod{11}\).
c) En déduire un critère de divisibilité par \(11\). L’appliquer à \(N = 918\,170\).
Voir la correction
a) On a \(10 \equiv -1 \pmod{11}\) (car \(10 – (-1) = 11\)). Par la propriété de puissance : \(10^n \equiv (-1)^n \pmod{11}\).
b) En utilisant la compatibilité avec l’addition et la multiplication :
\(N = \displaystyle\sum_{k=0}^{p} a_k \times 10^k \equiv \displaystyle\sum_{k=0}^{p} a_k \times (-1)^k = a_0 – a_1 + a_2 – a_3 + \ldots + (-1)^p a_p \pmod{11}\)c) Critère : un entier \(N\) est divisible par \(11\) si et seulement si la somme alternée de ses chiffres (en partant des unités) est divisible par \(11\).
Application : pour \(N = 918\,170\), les chiffres sont (des unités vers la gauche) : \(0, 7, 1, 8, 1, 9\). La somme alternée vaut :
\(0 – 7 + 1 – 8 + 1 – 9 = -22 = -2 \times 11\)Comme \(11 \mid (-22)\), le nombre \(918\,170\) est bien divisible par \(11\).
Erreur à éviter : se tromper dans le sens de l’alternance. La somme alternée commence par le chiffre des unités (avec un signe \(+\)).
VII. Arithmétique modulaire et structures — Compléments CPGE 🔴
En classes préparatoires (MPSI, PCSI), les congruences sont approfondies dans un cadre algébrique. Cette section présente les résultats essentiels que tu rencontreras en Sup. Elle n’est pas au programme de Maths Expertes — tu peux la consulter pour prendre de l’avance ou comprendre « où mènent » les congruences.
A. L’anneau \(\mathbb{Z}/n\mathbb{Z}\)
L’ensemble des classes de congruence modulo \(n\) est noté \(\mathbb{Z}/n\mathbb{Z}\). Il contient exactement \(n\) éléments : \(\bar{0}, \bar{1}, \ldots, \overline{n-1}\).
Définition — Anneau \(\mathbb{Z}/n\mathbb{Z}\)
Muni de l’addition et de la multiplication héritées de \(\mathbb{Z}\), \(\mathbb{Z}/n\mathbb{Z}\) est un anneau commutatif unitaire. L’élément \(\bar{a}\) est inversible dans \(\mathbb{Z}/n\mathbb{Z}\) si et seulement si \(\mathrm{pgcd}(a, n) = 1\).
\(\mathbb{Z}/n\mathbb{Z}\) est un corps (tout élément non nul est inversible) si et seulement si \(n\) est premier.
Exemple : \(\mathbb{Z}/5\mathbb{Z}\) est un corps — le tableau de multiplication modulo \(5\) (section III) montre que chaque élément non nul a un inverse. En revanche, \(\mathbb{Z}/6\mathbb{Z}\) n’est pas un corps car \(\bar{2} \times \bar{3} = \bar{0}\) (diviseurs de zéro).
B. Petit théorème de Fermat
Théorème (Fermat)
Pour tout premier \(p\) et tout entier \(a \in \mathbb{Z}\) :
\(a^p \equiv a \pmod{p}\)
Si de plus \(p \not\mid a\), alors \(a^{p-1} \equiv 1 \pmod{p}\).
Ce théorème est extrêmement puissant pour le calcul de grandes puissances modulaires. Il garantit que l’ordre de tout élément non nul de \(\mathbb{Z}/p\mathbb{Z}\) divise \(p – 1\).
Application : calculer \(2^{100} \pmod{13}\) avec Fermat.
\(13\) est premier et \(13 \not\mid 2\), donc \(2^{12} \equiv 1 \pmod{13}\).
\(100 = 12 \times 8 + 4\), donc \(2^{100} \equiv 2^4 = 16 \equiv 3 \pmod{13}\).
On retrouve le résultat de l’exercice 3, en une seule ligne grâce à Fermat !
C. Théorème chinois des restes
Théorème chinois des restes
Soient \(m\) et \(n\) deux entiers naturels non nuls tels que \(\mathrm{pgcd}(m, n) = 1\). Pour tous entiers \(a\) et \(b\), le système :
\(\begin{cases} x \equiv a \pmod{m} \\ x \equiv b \pmod{n} \end{cases}\)
admet une solution, et toutes les solutions sont congrues modulo \(mn\).
Ce théorème est la clé de l’exercice 4 : il permet de « recombiner » les solutions modulo \(8\) et modulo \(3\) en solutions modulo \(24\).
Exemple : résoudre \(\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \end{cases}\)
\(\mathrm{pgcd}(3, 5) = 1\) ✓. La première condition donne \(x = 3k + 2\). En substituant dans la seconde : \(3k + 2 \equiv 3 \pmod{5}\), soit \(3k \equiv 1 \pmod{5}\). L’inverse de \(3\) modulo \(5\) est \(2\) (car \(3 \times 2 = 6 \equiv 1\)), donc \(k \equiv 2 \pmod{5}\), soit \(k = 5j + 2\).
Ainsi \(x = 3(5j + 2) + 2 = 15j + 8\), d’où \(x \equiv 8 \pmod{15}\).
D. Applications à la cryptographie : RSA
Le système de cryptographie RSA, utilisé chaque fois que tu te connectes à un site sécurisé (HTTPS), repose entièrement sur l’arithmétique modulaire. Son principe est simple :
- Choisir deux grands nombres premiers \(p\) et \(q\), et poser \(n = pq\).
- Choisir un exposant public \(e\) tel que \(\mathrm{pgcd}(e, (p-1)(q-1)) = 1\).
- Calculer l’exposant privé \(d\), inverse de \(e\) modulo \((p-1)(q-1)\).
- Chiffrement : \(c \equiv m^e \pmod{n}\). Déchiffrement : \(m \equiv c^d \pmod{n}\).
La sécurité repose sur la difficulté de factoriser \(n\) en \(p \times q\) (le théorème fondamental de l’arithmétique garantit que cette décomposition existe, mais la trouver prend un temps colossal pour de grands nombres). Le petit théorème de Fermat assure que le déchiffrement fonctionne.
VIII. Questions fréquentes
C'est quoi une congruence en maths ?
Deux entiers \(a\) et \(b\) sont congrus modulo \(n\) si leur différence \(b – a\) est divisible par \(n\). On écrit \(a \equiv b \pmod{n}\). Concrètement, cela signifie que \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\). Les congruences sont au programme de Terminale Maths Expertes et de CPGE.
Comment calculer modulo n ?
Pour calculer \(a \pmod{n}\), effectue la division euclidienne : \(a = nq + r\) avec \(0 \leq r\) < \(n\). Le reste \(r\) est le résultat. Pour les grandes puissances, utilise la méthode des cycles : calcule les puissances successives modulo \(n\) jusqu’à trouver \(1\) ou \(-1\), puis divise l’exposant par la période.
Comment construire un tableau de congruence ?
Un tableau de congruence modulo \(n\) est un tableau à double entrée : en ligne et en colonne, les restes \(0, 1, \ldots, n-1\). À l’intersection de la ligne \(a\) et de la colonne \(b\), inscris le reste de \(a \times b\) (ou \(a + b\)) dans la division par \(n\). Les cases contenant \(1\) dans la table de multiplication révèlent les paires d’inverses.
Quelle est la différence entre congruence et égalité ?
L’égalité \(a = b\) signifie que \(a\) et \(b\) sont le même nombre. La congruence \(a \equiv b \pmod{n}\) signifie qu’ils ont le même reste modulo \(n\) — mais ils peuvent être très différents. Par exemple, \(17 \equiv 2 \pmod{5}\) est vrai, mais \(17 \neq 2\). On ne peut jamais remplacer \(\equiv\) par \(=\).
Quelle est la différence entre congruences et divisibilité ?
La divisibilité (\(a \mid b\), « \(a\) divise \(b\) ») est une relation d’ordre entre deux entiers. La congruence (\(a \equiv b \pmod{n}\)) est une relation d’équivalence qui classifie les entiers selon leur reste. Les deux sont liées : \(a \equiv 0 \pmod{n}\) équivaut à \(n \mid a\). Les congruences sont donc une généralisation de la divisibilité : au lieu de tester si le reste est nul, on compare les restes de deux entiers.
À quoi servent les congruences en arithmétique ?
Les congruences servent à : (1) calculer des restes de grandes puissances sans calculatrice, (2) démontrer des critères de divisibilité (par 3, 9, 11…), (3) résoudre des équations diophantiennes, (4) construire des systèmes de cryptographie (RSA). En classe préparatoire, elles sont le fondement de l’arithmétique modulaire et de la théorie des nombres.
IX. Pour aller plus loin
Tu maîtrises maintenant les congruences — de la définition aux techniques de calcul. Pour approfondir tes compétences en arithmétique, voici les ressources complémentaires :
- 📖 Arithmétique : définition, théorèmes et cours complet — le cours central qui articule toutes les notions
- Théorème de Gauss — le théorème que tu utilises chaque fois que tu combines deux divisibilités
- Théorème fondamental de l’arithmétique — la décomposition en facteurs premiers, socle de tout le calcul modulaire
- Division euclidienne — le fondement des restes et donc des congruences
- PGCD et PPCM — indispensables pour l’inversibilité et le théorème de Bézout
- Nombres premiers — premiers entre eux, lemme d’Euclide et petit théorème de Fermat
- Critères de divisibilité — les applications directes des congruences (par 3, 9, 11…)
- ✏️ Exercices d’arithmétique 3ème — pour consolider les bases en divisibilité et PGCD
