Congruences modulo n : Cours de Mathématiques 2BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ
Congruences modulo n : notion du chapitre Arithmétique dans ℤ du programme de maths 2BAC SM, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de 2BAC SM A et SM B, option française (BIOF).
Notions du cours (11)
Apprendre avec Burhan
Congruences
Étape 1 sur 4Le langage des congruences
Devine : L'horloge

Il est h. Quelle heure affichera une horloge de heures dans heures ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A : h, car heures font quatre jours.
Faux.
Quatre jours font heures, pas : il reste heures à ajouter.
Choix B : h
Faux.
est le reste de par . Il faut encore l'ajouter à l'heure de départ : , soit h.
Choix C : h
Juste.
: l'horloge affiche le reste, .
Besoin d'aide ? Indice 1
Une horloge de heures revient au même affichage toutes les heures.
Voir la correction complète
On calcule , puis avec . L'horloge affiche h : elle ne retient que le reste de la division par .
L'horloge calcule modulo : deux instants séparés par un multiple de heures s'affichent pareil. En 1BAC, tu as noté cette relation avec le symbole . Voici la définition exacte.
DéfinitionCongruence modulo n
Soit un entier naturel non nul. Deux entiers relatifs et sont congrus modulo si . On écrit alors , et on lit « est congru à modulo ».

ExempleLire une congruence
- , car .
- , car .
Remarque que et ont le même reste, , dans la division par . Est-ce un hasard ? Non : la propriété suivante l'affirme, et sa preuve compare les deux restes.

Étape 2 sur 4Congruence et reste
PropriétéCongruence et reste
Soient un entier naturel non nul et , deux entiers relatifs.
- si et seulement si et ont le même reste dans la division euclidienne par .
- Tout entier relatif est congru modulo à son reste , et à aucun autre entier de .
Démonstration
Étape 1. On écrit et avec et (« Division euclidienne dans ℤ »). Alors .
Étape 2 (point 1, sens direct). Si , alors (« Propriétés de la divisibilité »). Or , car et : si , le point 3 de « Propriétés de la divisibilité » donnerait . Donc .
Étape 3 (point 1, réciproque). Si , alors , donc .
Étape 4 (point 2). , donc . Si avec , le reste de est lui-même () ; le point 1 donne .

Vérifie : Un reste à trouver

Quel est le reste de la division euclidienne de par ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Faux.
C'est le reste de , pas de : . Le signe change tout.
Choix B :
Juste.
On a , avec .
Choix C :
Faux.
L'égalité est exacte, mais un reste n'est jamais négatif. Il faut descendre d'un multiple de .
Besoin d'aide ? Indice 1
Le reste doit vérifier .
Encore bloqué ? Indice 2
Cherche le multiple de juste en dessous de .
Voir la correction complète
On a et : le reste est . Donc , et est le seul entier de congru à modulo .
← Étape précédenteContinuer : Calculer sans poser le produit →
Étape 3 sur 4Calculer sans poser le produit
Cherche le reste de dans la division par . Inutile de poser le produit : et . On calcule .
Vérification : , dont le reste est bien . Pourquoi peut-on remplacer chaque facteur par son reste ? La propriété suivante le prouve.
PropriétéOpérations sur les congruences
Soit un entier naturel non nul.
- Pour tous entiers relatifs , , : ; si , alors ; si et , alors .
- Pour tous entiers relatifs , , , : si et , alors et .
- Pour tous entiers relatifs , : si , alors pour tout entier naturel .
Démonstration
Étape 1 (point 1). ; ; . On conclut par le point 2 de « Propriétés de la divisibilité ».
Étape 2 (point 2). On écrit et avec . Alors et .
Étape 3 (point 3, par récurrence sur ). Initialisation : (convention pour tout entier , même nul). Hérédité : si , le point 2 appliqué à cette congruence et à donne . Conclusion : la propriété est vraie pour tout .

Méthodereste d'une puissance
- Repérer un retour à 1 : on calcule les restes de , , … modulo , jusqu'à un exposant tel que .
- Diviser l'exposant par : , avec .
- Conclure : .
Un tel exposant n'existe pas toujours : essaie modulo . Le petit théorème de Fermat donnera des cas où il existe à coup sûr.
Rédaction attendue. « On a . D'après les opérations sur les congruences, , donc . » Le module s'écrit à chaque ligne.

ExempleExemple guidé : une grande puissance
Montrons que .
| reste de modulo |
On a . Or , avec . Donc .

Étape 4 sur 4À toi de rédiger
À toi : Une divisibilité pour tout n

Montre que, pour tout entier naturel , .
Besoin d'aide ? Indice 1
Calcule les restes de et de modulo .
Encore bloqué ? Indice 2
Tu dois trouver , donc .
Encore bloqué ? Indice 3
Écris , puis conclus en écrivant le module.
Voir la solution complète
On a , donc . Puis .
D'après les opérations sur les congruences, pour tout . Donc .
Ainsi , c'est-à-dire .
AttentionL'exposant ne se réduit pas modulo n
Pour modulo , une erreur fréquente consiste à réduire l'exposant modulo : , puis . C'est faux : le bon reste est .
L'exposant se réduit selon la longueur du cycle des restes, ici . Il ne se réduit pas selon le module.

← Étape précédenteFin de la notion
S'entraîner sur cette notion
- Les puissances de 5 modulo 13 · niveau application
- Carrés modulo 7 · niveau entraînement
- Deux preuves pour une divisibilité par 11 · niveau entraînement
- Critères de divisibilité en base huit · niveau entraînement
- Deux congruences, modulo 43 et modulo 18 · niveau examen
- Un entier lu en base 7 et en base 9 · niveau perfectionnement
Sources du cours
- Référentiel BURHAN du chapitre « Arithmétique dans ℤ » (2bac · sciences-mathematiques · mathematiques)
