BURHAN.

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 4

Le langage des congruences

Devine : L'horloge

Il est 2222 h. Quelle heure affichera une horloge de 2424 heures dans 100100 heures ?

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

Choix A :2222 h, car 100100 heures font quatre jours.

Faux.

Quatre jours font 9696 heures, pas 100100 : il reste 44 heures à ajouter.

Choix B :44 h

Faux.

44 est le reste de 100100 par 2424. Il faut encore l'ajouter à l'heure de départ : 22+4=2622 + 4 = 26, soit 22 h.

Choix C :22 h

Juste.

22+100=122=24×5+222 + 100 = 122 = 24 \times 5 + 2 : l'horloge affiche le reste, 22.

Besoin d'aide ? Indice 1

Une horloge de 2424 heures revient au même affichage toutes les 2424 heures.

Voir la correction complète

On calcule 22+100=12222 + 100 = 122, puis 122=24×5+2122 = 24 \times 5 + 2 avec 0≤2<240 \leq 2 < 24. L'horloge affiche 22 h : elle ne retient que le reste de la division par 2424.

L'horloge calcule modulo 2424 : deux instants séparés par un multiple de 2424 heures s'affichent pareil. En 1BAC, tu as noté cette relation avec le symbole ≡\equiv. Voici la définition exacte.

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 écrit alors a≡b [n]a \equiv b \ [n], et on lit « aa est congru à bb modulo nn ».

ExempleLire une congruence

  • 122≡2 [24]122 \equiv 2 \ [24], car 122−2=120=24×5122 - 2 = 120 = 24 \times 5.
  • −3≡4 [7]-3 \equiv 4 \ [7], car −3−4=−7-3 - 4 = -7.

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

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, bb deux entiers relatifs.

  1. 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.
  2. Tout entier relatif aa est congru modulo nn à son reste rr, et à aucun autre entier de {0,1,…,n−1}\{0, 1, \dots, n - 1\}.

Démonstration

Étape 1. On écrit 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 dans ℤ »). Alors a−b=n(q−q′)+(r−r′)a - b = n(q - q') + (r - r').

Étape 2 (point 1, sens direct). Si n∣a−bn \mid a - b, alors n∣(a−b)−n(q−q′)=r−r′n \mid (a - b) - n(q - q') = r - r' (« Propriétés de la divisibilité »). Or −n<r−r′<n-n < r - r' < n, car 0≤r<n0 \leq r < n et 0≤r′<n0 \leq r' < n : si r−r′≠0r - r' \neq 0, le point 3 de « Propriétés de la divisibilité » donnerait n≤∣r−r′∣n \leq \lvert r - r' \rvert. Donc r=r′r = r'.

Étape 3 (point 1, réciproque). Si r=r′r = r', alors a−b=n(q−q′)a - b = n(q - q'), donc n∣a−bn \mid a - b.

Étape 4 (point 2). a−r=nqa - r = nq, donc a≡r [n]a \equiv r \ [n]. Si a≡s [n]a \equiv s \ [n] avec 0≤s≤n−10 \leq s \leq n - 1, le reste de ss est ss lui-même (s=n×0+ss = n \times 0 + s) ; le point 1 donne s=rs = r.

Vérifie : Un reste à trouver

Quel est le reste de la division euclidienne de −38-38 par 99 ?

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

Choix A :22

Faux.

C'est le reste de 3838, pas de −38-38 : 38=9×4+238 = 9 \times 4 + 2. Le signe change tout.

Choix B :77

Juste.

On a −38=9×(−5)+7-38 = 9 \times (-5) + 7, avec 0≤7<90 \leq 7 < 9.

Choix C :−2-2

Faux.

L'égalité −38=9×(−4)−2-38 = 9 \times (-4) - 2 est exacte, mais un reste n'est jamais négatif. Il faut descendre d'un multiple de 99.

Besoin d'aide ? Indice 1

Le reste doit vérifier 0≤r<90 \leq r < 9.

Encore bloqué ? Indice 2

Cherche le multiple de 99 juste en dessous de −38-38.

Voir la correction complète

On a −38=9×(−5)+7-38 = 9 \times (-5) + 7 et 0≤7<90 \leq 7 < 9 : le reste est 77. Donc −38≡7 [9]-38 \equiv 7 \ [9], et 77 est le seul entier de {0,1,…,8}\{0, 1, \dots, 8\} congru à −38-38 modulo 99.

← Étape précédenteContinuer : Calculer sans poser le produit →

Étape 3 sur 4

Calculer sans poser le produit

Cherche le reste de 47×5347 \times 53 dans la division par 55. Inutile de poser le produit : 47≡2 [5]47 \equiv 2 \ [5] et 53≡3 [5]53 \equiv 3 \ [5]. On calcule 2×3=6≡1 [5]2 \times 3 = 6 \equiv 1 \ [5].

Vérification : 47×53=249147 \times 53 = 2491, dont le reste est bien 11. Pourquoi peut-on remplacer chaque facteur par son reste ? La propriété suivante le prouve.

PropriétéOpérations sur les congruences

Soit nn un entier naturel non nul.

  1. Pour tous entiers relatifs aa, bb, cc : a≡a [n]a \equiv a \ [n] ; si a≡b [n]a \equiv b \ [n], alors b≡a [n]b \equiv a \ [n] ; si a≡b [n]a \equiv b \ [n] et b≡c [n]b \equiv c \ [n], alors a≡c [n]a \equiv c \ [n].
  2. Pour tous entiers relatifs aa, bb, cc, dd : si a≡b [n]a \equiv b \ [n] et c≡d [n]c \equiv d \ [n], alors a+c≡b+d [n]a + c \equiv b + d \ [n] et ac≡bd [n]ac \equiv bd \ [n].
  3. Pour tous entiers relatifs aa, bb : si a≡b [n]a \equiv b \ [n], alors ak≡bk [n]a^k \equiv b^k \ [n] pour tout entier naturel kk.

Démonstration

Étape 1 (point 1). a−a=0=n×0a - a = 0 = n \times 0 ; b−a=−(a−b)b - a = -(a - b) ; a−c=(a−b)+(b−c)a - c = (a - b) + (b - c). On conclut par le point 2 de « Propriétés de la divisibilité ».

Étape 2 (point 2). On écrit a−b=nka - b = nk et c−d=nk′c - d = nk' avec k,k′∈Zk, k' \in \mathbb{Z}. Alors (a+c)−(b+d)=n(k+k′)(a + c) - (b + d) = n(k + k') et ac−bd=a(c−d)+d(a−b)=n(ak′+dk)ac - bd = a(c - d) + d(a - b) = n(ak' + dk).

Étape 3 (point 3, par récurrence sur kk). Initialisation : a0=1=b0a^0 = 1 = b^0 (convention x0=1x^0 = 1 pour tout entier xx, même nul). Hérédité : si ak≡bk [n]a^k \equiv b^k \ [n], le point 2 appliqué à cette congruence et à a≡b [n]a \equiv b \ [n] donne ak+1=ak×a≡bk×b=bk+1 [n]a^{k+1} = a^k \times a \equiv b^k \times b = b^{k+1} \ [n]. Conclusion : la propriété est vraie pour tout k∈Nk \in \mathbb{N}.

Méthodereste d'une puissance

  1. Repérer un retour à 1 : on calcule les restes de aa, a2a^2, a3a^3… modulo nn, jusqu'à un exposant k≥1k \geq 1 tel que ak≡1 [n]a^k \equiv 1 \ [n].
  2. Diviser l'exposant par kk : N=kq+rN = kq + r, avec 0≤r<k0 \leq r < k.
  3. Conclure : aN=(ak)q×ar≡ar [n]a^N = (a^k)^q \times a^r \equiv a^r \ [n].

Un tel exposant kk n'existe pas toujours : essaie 22 modulo 44. Le petit théorème de Fermat donnera des cas où il existe à coup sûr.

Rédaction attendue. « On a ak≡1 [n]a^k \equiv 1 \ [n]. D'après les opérations sur les congruences, (ak)q≡1 [n](a^k)^q \equiv 1 \ [n], donc aN≡ar [n]a^N \equiv a^r \ [n]. » Le module s'écrit à chaque ligne.

ExempleExemple guidé : une grande puissance

Montrons que 32026≡4 [7]3^{2026} \equiv 4 \ [7].

kk 11 22 33 44 55 66
reste de 3k3^k modulo 77 33 22 66 44 55 11

On a 36≡1 [7]3^6 \equiv 1 \ [7]. Or 2026=6×337+42026 = 6 \times 337 + 4, avec 0≤4<60 \leq 4 < 6. Donc 32026=(36)337×34≡1×81≡4 [7]3^{2026} = (3^6)^{337} \times 3^4 \equiv 1 \times 81 \equiv 4 \ [7].

← Étape précédenteContinuer : À toi de rédiger →

Étape 4 sur 4

À toi de rédiger

À toi : Une divisibilité pour tout n

Montre que, pour tout entier naturel nn, 13∣46n+1−413 \mid 4^{6n+1} - 4.

Besoin d'aide ? Indice 1

Calcule les restes de 424^2 et de 434^3 modulo 1313.

Encore bloqué ? Indice 2

Tu dois trouver 43≡−1 [13]4^3 \equiv -1 \ [13], donc 46≡1 [13]4^6 \equiv 1 \ [13].

Encore bloqué ? Indice 3

Écris 46n+1=(46)n×44^{6n+1} = (4^6)^n \times 4, puis conclus en écrivant le module.

Voir la solution complète

On a 43=64=13×5−14^3 = 64 = 13 \times 5 - 1, donc 43≡−1 [13]4^3 \equiv -1 \ [13]. Puis 46=(43)2≡(−1)2=1 [13]4^6 = (4^3)^2 \equiv (-1)^2 = 1 \ [13].

D'après les opérations sur les congruences, (46)n≡1 [13](4^6)^n \equiv 1 \ [13] pour tout n∈Nn \in \mathbb{N}. Donc 46n+1=(46)n×4≡4 [13]4^{6n+1} = (4^6)^n \times 4 \equiv 4 \ [13].

Ainsi 46n+1−4≡0 [13]4^{6n+1} - 4 \equiv 0 \ [13], c'est-à-dire 13∣46n+1−413 \mid 4^{6n+1} - 4.

AttentionL'exposant ne se réduit pas modulo n

Pour 320263^{2026} modulo 77, une erreur fréquente consiste à réduire l'exposant modulo 77 : 2026≡3 [7]2026 \equiv 3 \ [7], puis 33≡6 [7]3^3 \equiv 6 \ [7]. C'est faux : le bon reste est 44.

L'exposant se réduit selon la longueur du cycle des restes, ici 66. Il ne se réduit pas selon le module.

← É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 ℤ » (2bac · sciences-mathematiques · mathematiques)