Congruence modulo n : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ
Congruence modulo n : notion du chapitre Arithmétique dans ℤ du programme de maths 1BAC SM, expliquée pas à pas, avec 3 exemples guidés. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).
Notions du cours (13)
Apprendre avec Burhan
Congruence modulo n
Étape 1 sur 4Même reste
Devine : Même reste

Sur une horloge, h plus heures donne h, car . Les entiers et ont le même reste dans la division par , et est un multiple de . Lequel de ces entiers a le même reste que dans la division par ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Faux.
Le reste de par est ; celui de est .
Choix B :
Juste.
Juste : , et .
Choix C :
Faux.
: le reste est , pas .
Choix D :
Faux.
: le reste est .
Voir la correction complète
: le reste est . Et , avec : même reste. On remarque que est un multiple de . Pour , et , les restes sont , et .
DéfinitionCongruence modulo n
Soit un entier naturel non nul. Deux entiers relatifs et sont congrus modulo si . On note et on lit « est congru à modulo ».

Exemplelire une congruence
- , car .
- , car .
- , car et .
Note que et ont le même reste, , dans la division par . Pourquoi est-ce vrai ? Si et , alors : le reste disparaît dans la différence.

Étape 2 sur 4Congruence et reste
PropriétéCongruence et reste
Soient un entier naturel non nul, et et deux entiers relatifs. Alors si et seulement si et ont le même reste dans la division euclidienne par .
En particulier, si est le reste de la division euclidienne de par , alors ; et si et seulement si .
Démonstration
Étape 1. Écrivons et , avec et (division euclidienne). Alors .
Étape 2. Si , alors , donc .
Étape 3. Réciproquement, si , alors divise (propriétés de la divisibilité). Or . Si l'on avait , la comparaison des valeurs absolues donnerait : contradiction. Donc .
Étape 4. Comme , on a . Enfin, signifie (définition de la congruence).

À retenirRetenir de la preuve : le même reste
On écrit les deux divisions euclidiennes et on soustrait : . Les restes vérifient , et un multiple de aussi petit est nul. Retiens : « congrus modulo » et « même reste par » disent la même chose.

Vérifie : L'étape clé

Dans l'étape 3 de la preuve, divise . Pourquoi en déduit-on ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :Parce que deux restes sont toujours égaux.
Faux.
Les restes de et de dans la division par sont et : ils diffèrent.
Choix B :Parce que et sont positifs.
Faux.
La positivité seule ne suffit pas : et sont positifs, et .
Choix C :Parce que divise et .
Faux.
Rien ne le dit : divise seulement leur différence.
Choix D :Parce que , et un multiple de aussi petit est nul.
Juste.
Juste : c'est la comparaison des valeurs absolues.
Voir la correction complète
Les restes vérifient et , donc . Si l'on avait , la comparaison des valeurs absolues donnerait : contradiction. Donc .
Exempleremplacer un entier par son reste
, donc . De même, , donc . Et , car .
Une congruence se manie presque comme une égalité. Pourquoi est-ce vrai ? Le nombre , l'opposé d'un multiple de et la somme de deux multiples de sont des multiples de .

Étape 3 sur 4Comme une égalité
PropriétéRéflexivité, symétrie, transitivité
Soit un entier naturel non nul. Pour tous entiers relatifs , et :
- ;
- si , alors ;
- si et , alors .
Démonstration
Étape 1. , donc (définition de la divisibilité).
Étape 2. Si , alors divise (propriétés de la divisibilité).
Étape 3. Si et , alors divise leur somme (propriétés de la divisibilité).

À retenirRetenir de la preuve : se ramener à un multiple
Chaque règle se ramène à un multiple de : , puis , puis . Conséquence pratique : dans une chaîne de congruences de même module, on enchaîne comme avec des égalités.

Vérifie : La transitivité

Dans l'étape 3, quelle égalité montre que ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Faux.
Faux : on obtient .
Choix B :
Faux.
Faux : pour , , , le produit vaut et .
Choix C :
Faux.
Faux dès que .
Choix D :
Juste.
Juste : une somme de deux multiples de .
Voir la correction complète
divise et , donc leur somme (propriétés de la divisibilité) : .
Exempleune chaîne de congruences
, car ; et , car . Par transitivité, . Contrôle : .

Étape 4 sur 4Piège et entraînement
Attentionune congruence sans module ne veut rien dire
✗ « ».
✓ Il faut écrire le module : est vraie, mais est fausse. Et une congruence n'est pas une égalité : , alors que .

À toi : Vraie ou fausse ?

Pour chaque proposition, dis si elle est vraie, en justifiant : (a) ; (b) ; (c) . Donne ensuite le reste de dans la division par . Écris ta réponse avant de dévoiler la correction.
Besoin d'aide ? Indice 1
Reviens à la définition : calcule chaque différence .
Encore bloqué ? Indice 2
Cherche si cette différence est un multiple du module.
Encore bloqué ? Indice 3
Point délicat : pour le reste de , le quotient est négatif et le reste doit vérifier .
Voir la solution complète
(a) : la proposition est vraie.
(b) , et : la proposition est fausse.
(c) : la proposition est vraie.
Enfin, , avec : le reste est , et .
← Étape précédenteFin de la notion
S'entraîner sur cette notion
Sources du cours
- Référentiel BURHAN du chapitre « Arithmétique dans ℤ » (1bac · sciences-mathematiques · mathematiques)
