BURHAN.

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 4

Même reste

Devine : Même reste

Sur une horloge, 99 h plus 3030 heures donne 33 h, car 39=12×3+339 = 12 \times 3 + 3. Les entiers 3939 et 33 ont le même reste dans la division par 1212, et 39−3=3639 - 3 = 36 est un multiple de 1212. Lequel de ces entiers a le même reste que 2020 dans la division par 66 ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :44

Faux.

Le reste de 44 par 66 est 44 ; celui de 2020 est 22.

Choix B :−4-4

Juste.

Juste : −4=6×(−1)+2-4 = 6 \times (-1) + 2, et 20−(−4)=24=6×420 - (-4) = 24 = 6 \times 4.

Choix C :−2-2

Faux.

−2=6×(−1)+4-2 = 6 \times (-1) + 4 : le reste est 44, pas 22.

Choix D :3333

Faux.

33=6×5+333 = 6 \times 5 + 3 : le reste est 33.

Voir la correction complète

20=6×3+220 = 6 \times 3 + 2 : le reste est 22. Et −4=6×(−1)+2-4 = 6 \times (-1) + 2, avec 0≤2<60 \leq 2 < 6 : même reste. On remarque que 20−(−4)=2420 - (-4) = 24 est un multiple de 66. Pour 44, −2-2 et 3333, les restes sont 44, 44 et 33.

DéfinitionCongruence modulo n

Soit nn un entier naturel non nul. Deux entiers relatifs aa et bb sont congrus modulo nn si n∣a−bn \mid a - b. On note a≡b [n],a \equiv b \ [n], et on lit « aa est congru à bb modulo nn ».

Exemplelire une congruence

  • 38≡3 [7]38 \equiv 3 \ [7], car 38−3=35=7×538 - 3 = 35 = 7 \times 5.
  • −10≡4 [7]-10 \equiv 4 \ [7], car −10−4=−14=7×(−2)-10 - 4 = -14 = 7 \times (-2).
  • 23≢5 [7]23 \not\equiv 5 \ [7], car 23−5=1823 - 5 = 18 et 7∤187 \nmid 18.

Note que 3838 et 33 ont le même reste, 33, dans la division par 77. Pourquoi est-ce vrai ? Si a=nq+ra = nq + r et b=nq′+rb = nq' + r, alors a−b=n(q−q′)a - b = n(q - q') : le reste disparaît dans la différence.

Continuer : Congruence et reste →

Étape 2 sur 4

Congruence et reste

PropriétéCongruence et reste

Soient nn un entier naturel non nul, et aa et bb deux entiers relatifs. Alors a≡b [n]a \equiv b \ [n] si et seulement si aa et bb ont le même reste dans la division euclidienne par nn.

En particulier, si rr est le reste de la division euclidienne de aa par nn, alors a≡r [n]a \equiv r \ [n] ; et a≡0 [n]a \equiv 0 \ [n] si et seulement si n∣an \mid a.

Démonstration

Étape 1. Écrivons a=nq+ra = nq + r et b=nq′+r′b = nq' + r', avec 0≤r<n0 \leq r < n et 0≤r′<n0 \leq r' < n (division euclidienne). Alors a−b=n(q−q′)+(r−r′)a - b = n(q - q') + (r - r').

Étape 2. Si r=r′r = r', alors a−b=n(q−q′)a - b = n(q - q'), donc n∣a−bn \mid a - b.

Étape 3. Réciproquement, si n∣a−bn \mid a - b, alors nn divise (a−b)−n(q−q′)=r−r′(a - b) - n(q - q') = r - r' (propriétés de la divisibilité). Or ∣r−r′∣<n\lvert r - r' \rvert < n. Si l'on avait r≠r′r \neq r', la comparaison des valeurs absolues donnerait n≤∣r−r′∣n \leq \lvert r - r' \rvert : contradiction. Donc r=r′r = r'.

Étape 4. Comme a−r=nqa - r = nq, on a a≡r [n]a \equiv r \ [n]. Enfin, a≡0 [n]a \equiv 0 \ [n] signifie n∣a−0n \mid a - 0 (définition de la congruence).

À retenirRetenir de la preuve : le même reste

On écrit les deux divisions euclidiennes et on soustrait : a−b=n(q−q′)+(r−r′)a - b = n(q - q') + (r - r'). Les restes vérifient ∣r−r′∣<n\lvert r - r' \rvert < n, et un multiple de nn aussi petit est nul. Retiens : « congrus modulo nn » et « même reste par nn » disent la même chose.

Vérifie : L'étape clé

Dans l'étape 3 de la preuve, nn divise r−r′r - r'. Pourquoi en déduit-on r=r′r = r' ?

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 55 et de 66 dans la division par 77 sont 55 et 66 : ils diffèrent.

Choix B :Parce que rr et r′r' sont positifs.

Faux.

La positivité seule ne suffit pas : 11 et 88 sont positifs, et 7∣8−17 \mid 8 - 1.

Choix C :Parce que nn divise rr et r′r'.

Faux.

Rien ne le dit : nn divise seulement leur différence.

Choix D :Parce que ∣r−r′∣<n\lvert r - r' \rvert < n, et un multiple de nn aussi petit est nul.

Juste.

Juste : c'est la comparaison des valeurs absolues.

Voir la correction complète

Les restes vérifient 0≤r<n0 \leq r < n et 0≤r′<n0 \leq r' < n, donc ∣r−r′∣<n\lvert r - r' \rvert < n. Si l'on avait r≠r′r \neq r', la comparaison des valeurs absolues donnerait n≤∣r−r′∣n \leq \lvert r - r' \rvert : contradiction. Donc r=r′r = r'.

Exempleremplacer un entier par son reste

100=7×14+2100 = 7 \times 14 + 2, donc 100≡2 [7]100 \equiv 2 \ [7]. De même, −15=4×(−4)+1-15 = 4 \times (-4) + 1, donc −15≡1 [4]-15 \equiv 1 \ [4]. Et 91≡0 [13]91 \equiv 0 \ [13], car 91=13×791 = 13 \times 7.

Une congruence se manie presque comme une égalité. Pourquoi est-ce vrai ? Le nombre 00, l'opposé d'un multiple de nn et la somme de deux multiples de nn sont des multiples de nn.

← Étape précédenteContinuer : Comme une égalité →

Étape 3 sur 4

Comme une égalité

PropriétéRéflexivité, symétrie, transitivité

Soit nn un entier naturel non nul. Pour tous entiers relatifs aa, bb et cc :

  1. a≡a [n]a \equiv a \ [n] ;
  2. si a≡b [n]a \equiv b \ [n], alors b≡a [n]b \equiv a \ [n] ;
  3. si a≡b [n]a \equiv b \ [n] et b≡c [n]b \equiv c \ [n], alors a≡c [n]a \equiv c \ [n].

Démonstration

Étape 1. a−a=0=0×na - a = 0 = 0 \times n, donc n∣a−an \mid a - a (définition de la divisibilité).

Étape 2. Si n∣a−bn \mid a - b, alors nn divise (a−b)×(−1)=b−a(a - b) \times (-1) = b - a (propriétés de la divisibilité).

Étape 3. Si n∣a−bn \mid a - b et n∣b−cn \mid b - c, alors nn divise leur somme (a−b)+(b−c)=a−c(a - b) + (b - c) = a - c (propriétés de la divisibilité).

À retenirRetenir de la preuve : se ramener à un multiple

Chaque règle se ramène à un multiple de nn : a−a=0a - a = 0, puis b−a=−(a−b)b - a = -(a - b), puis a−c=(a−b)+(b−c)a - c = (a - b) + (b - c). 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 n∣a−cn \mid a - c ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :(a−b)−(b−c)=a−c(a - b) - (b - c) = a - c

Faux.

Faux : on obtient a−2b+ca - 2b + c.

Choix B :(a−b)(b−c)=a−c(a - b)(b - c) = a - c

Faux.

Faux : pour a=2a = 2, b=1b = 1, c=0c = 0, le produit vaut 11 et a−c=2a - c = 2.

Choix C :a−c=a−ba - c = a - b

Faux.

Faux dès que b≠cb \neq c.

Choix D :(a−b)+(b−c)=a−c(a - b) + (b - c) = a - c

Juste.

Juste : une somme de deux multiples de nn.

Voir la correction complète

nn divise a−ba - b et b−cb - c, donc leur somme (a−b)+(b−c)=a−c(a - b) + (b - c) = a - c (propriétés de la divisibilité) : a≡c [n]a \equiv c \ [n].

Exempleune chaîne de congruences

47≡12 [5]47 \equiv 12 \ [5], car 47−12=35=5×747 - 12 = 35 = 5 \times 7 ; et 12≡2 [5]12 \equiv 2 \ [5], car 12−2=10=5×212 - 2 = 10 = 5 \times 2. Par transitivité, 47≡2 [5]47 \equiv 2 \ [5]. Contrôle : 47=5×9+247 = 5 \times 9 + 2.

← Étape précédenteContinuer : Piège et entraînement →

Étape 4 sur 4

Piège et entraînement

Attentionune congruence sans module ne veut rien dire

✗ « 22≡722 \equiv 7 ».

✓ Il faut écrire le module : 22≡7 [5]22 \equiv 7 \ [5] est vraie, mais 22≡7 [4]22 \equiv 7 \ [4] est fausse. Et une congruence n'est pas une égalité : 22≡7 [5]22 \equiv 7 \ [5], alors que 22≠722 \neq 7.

À toi : Vraie ou fausse ?

Pour chaque proposition, dis si elle est vraie, en justifiant : (a) 53≡−3 [8]53 \equiv -3 \ [8] ; (b) −21≡5 [9]-21 \equiv 5 \ [9] ; (c) 144≡0 [12]144 \equiv 0 \ [12]. Donne ensuite le reste de −21-21 dans la division par 99. Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Reviens à la définition : calcule chaque différence a−ba - b.

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 −21-21, le quotient est négatif et le reste doit vérifier 0≤r<90 \leq r < 9.

Voir la solution complète

(a) 53−(−3)=56=8×753 - (-3) = 56 = 8 \times 7 : la proposition est vraie.

(b) −21−5=−26-21 - 5 = -26, et 9∤269 \nmid 26 : la proposition est fausse.

(c) 144−0=144=12×12144 - 0 = 144 = 12 \times 12 : la proposition est vraie.

Enfin, −21=9×(−3)+6-21 = 9 \times (-3) + 6, avec 0≤6<90 \leq 6 < 9 : le reste est 66, et −21≡6 [9]-21 \equiv 6 \ [9].

← É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)