BURHAN.

Propriétés des congruences : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ

Propriétés des congruences : 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

Calculer avec les congruences

Étape 1 sur 5

Additionner et multiplier

Devine : Un reste sans tout calculer

On a 38≡3 [7]38 \equiv 3 \ [7] et 50≡1 [7]50 \equiv 1 \ [7]. Quel est le reste de 38×5038 \times 50 dans la division par 77 ?

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

Choix A :44

Faux.

4=3+14 = 3 + 1 : c'est le reste de la somme 38+50=8838 + 50 = 88, pas celui du produit.

Choix B :11

Faux.

Tu as gardé le reste de 5050 seulement.

Choix C :33

Juste.

Juste : 3×1=33 \times 1 = 3, et 1900=7×271+31900 = 7 \times 271 + 3.

Choix D :00

Faux.

77 ne divise ni 3838 ni 5050, et le reste du produit est celui de 3×13 \times 1.

Voir la correction complète

On remplace chaque facteur par son reste : 38×50≡3×1 [7]38 \times 50 \equiv 3 \times 1 \ [7], c'est-à-dire 38×50≡3 [7]38 \times 50 \equiv 3 \ [7]. Contrôle : 38×50=1900=7×271+338 \times 50 = 1900 = 7 \times 271 + 3.

Pourquoi est-ce vrai ? On a ac−bd=a(c−d)+d(a−b)ac - bd = a(c - d) + d(a - b) : si nn divise a−ba - b et c−dc - d, il divise ac−bdac - bd.

PropriétéCongruences, addition et multiplication

Soient nn un entier naturel non nul et aa, bb, cc, dd des entiers relatifs tels que a≡b [n]a \equiv b \ [n] et c≡d [n]c \equiv d \ [n]. Alors a+c≡b+d [n],a−c≡b−d [n]etac≡bd [n].a + c \equiv b + d \ [n], \quad a - c \equiv b - d \ [n] \quad \text{et} \quad ac \equiv bd \ [n]. En particulier, ka≡kb [n]ka \equiv kb \ [n] pour tout entier relatif kk.

Démonstration

Étape 1. On a (a+c)−(b+d)=(a−b)+(c−d)(a + c) - (b + d) = (a - b) + (c - d) et (a−c)−(b−d)=(a−b)−(c−d)(a - c) - (b - d) = (a - b) - (c - d). Comme nn divise a−ba - b et c−dc - d, il divise ces deux nombres (propriétés de la divisibilité).

Étape 2. On a ac−bd=a(c−d)+d(a−b)ac - bd = a(c - d) + d(a - b). Comme nn divise c−dc - d et a−ba - b, il divise ac−bdac - bd (propriétés de la divisibilité).

Étape 3. En prenant c=d=kc = d = k, qui vérifie k≡k [n]k \equiv k \ [n] (réflexivité, symétrie, transitivité), l'étape 2 donne ka≡kb [n]ka \equiv kb \ [n].

À retenirRetenir de la preuve : ajouter et retrancher

Tout repose sur deux écritures : (a+c)−(b+d)=(a−b)+(c−d)(a + c) - (b + d) = (a - b) + (c - d), et ac−bd=a(c−d)+d(a−b)ac - bd = a(c - d) + d(a - b). Retiens l'usage : dans une somme ou un produit, on peut remplacer chaque nombre par un nombre congru, avec le même module.

Vérifie : Le produit

Dans l'étape 2 de la preuve, quelle égalité montre que nn divise ac−bdac - bd ?

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

Choix A :ac−bd=a(c−d)+d(a−b)ac - bd = a(c - d) + d(a - b)

Juste.

Juste : les deux termes sont des multiples de nn.

Choix B :ac−bd=(a−b)(c−d)ac - bd = (a - b)(c - d)

Faux.

Faux : pour a=2a = 2 et b=c=d=1b = c = d = 1, on a ac−bd=1ac - bd = 1, et (a−b)(c−d)=0(a - b)(c - d) = 0.

Choix C :ac−bd=(a−c)+(b−d)ac - bd = (a - c) + (b - d)

Faux.

Faux : pour a=c=2a = c = 2 et b=d=1b = d = 1, on a ac−bd=3ac - bd = 3, et (a−c)+(b−d)=0(a - c) + (b - d) = 0.

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

Faux.

Faux : pour a=b=c=1a = b = c = 1 et d=0d = 0, on a ac−bd=1ac - bd = 1, et (a+b)(c−d)=2(a + b)(c - d) = 2.

Voir la correction complète

On ajoute et on retranche adad : ac−bd=ac−ad+ad−bd=a(c−d)+d(a−b)ac - bd = ac - ad + ad - bd = a(c - d) + d(a - b). Comme nn divise c−dc - d et a−ba - b, il divise cette combinaison, d'après les propriétés de la divisibilité. Donc ac≡bd [n]ac \equiv bd \ [n].

Exemplecalculer modulo 7

On a 38≡3 [7]38 \equiv 3 \ [7]. Donc 382=38×38≡3×3 [7]38^{2} = 38 \times 38 \equiv 3 \times 3 \ [7], soit 382≡9 [7]38^{2} \equiv 9 \ [7], puis 382≡2 [7]38^{2} \equiv 2 \ [7]. Contrôle : 382=1444=7×206+238^{2} = 1444 = 7 \times 206 + 2.

Pour une puissance quelconque, on répète la multiplication. Pourquoi est-ce vrai ? Une récurrence rend rigoureux ce « on répète kk fois ».

Continuer : Les puissances →

Étape 2 sur 5

Les puissances

PropriétéCongruences et puissances

Soient nn un entier naturel non nul, et aa et bb deux entiers relatifs tels que a≡b [n]a \equiv b \ [n]. Pour tout entier naturel non nul kk, ak≡bk [n].a^{k} \equiv b^{k} \ [n].

Démonstration

Raisonnons par récurrence sur l'entier k≥1k \geq 1.

Étape 1 (initialisation). Pour k=1k = 1 : a1=aa^{1} = a, b1=bb^{1} = b et a≡b [n]a \equiv b \ [n] par hypothèse.

Étape 2 (hérédité). Soit k≥1k \geq 1 un entier tel que ak≡bk [n]a^{k} \equiv b^{k} \ [n]. Avec a≡b [n]a \equiv b \ [n], la compatibilité avec la multiplication donne ak×a≡bk×b [n]a^{k} \times a \equiv b^{k} \times b \ [n], c'est-à-dire ak+1≡bk+1 [n]a^{k+1} \equiv b^{k+1} \ [n].

Étape 3 (conclusion). D'après le principe de récurrence, ak≡bk [n]a^{k} \equiv b^{k} \ [n] pour tout entier naturel k≥1k \geq 1.

À retenirRetenir de la preuve : la récurrence

La récurrence transforme « multiplier kk fois » en une preuve : l'hérédité multiplie ak≡bk [n]a^{k} \equiv b^{k} \ [n] par a≡b [n]a \equiv b \ [n]. Retiens l'usage : pour une puissance, on remplace d'abord la base par un nombre congru plus simple, par exemple 11 ou −1-1.

Vérifie : L'hérédité

Dans l'hérédité, quelle propriété permet de passer de ak≡bk [n]a^{k} \equiv b^{k} \ [n] à ak+1≡bk+1 [n]a^{k+1} \equiv b^{k+1} \ [n] ?

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

Choix A :La compatibilité avec l'addition.

Faux.

On ne fait aucune somme : ak+1=ak×aa^{k + 1} = a^{k} \times a.

Choix B :La compatibilité avec la multiplication.

Juste.

Juste : on multiplie ak≡bk [n]a^{k} \equiv b^{k} \ [n] par a≡b [n]a \equiv b \ [n].

Choix C :La transitivité, et elle seule.

Faux.

La transitivité enchaîne deux congruences ; elle ne fabrique pas un produit.

Choix D :La simplification par aa.

Faux.

On ne simplifie pas une congruence en général ; ici, on multiplie.

Voir la correction complète

On multiplie membre à membre ak≡bk [n]a^{k} \equiv b^{k} \ [n] et a≡b [n]a \equiv b \ [n]. La compatibilité avec la multiplication donne ak×a≡bk×b [n]a^{k} \times a \equiv b^{k} \times b \ [n], c'est-à-dire ak+1≡bk+1 [n]a^{k+1} \equiv b^{k+1} \ [n].

← Étape précédenteContinuer : Le reste d'une grande puissance →

Étape 3 sur 5

Le reste d'une grande puissance

Méthodetrouver le reste d'une grande puissance

  1. Calcule aa, a2a^{2}, a3a^{3}… modulo nn, en remplaçant chaque résultat par son reste.
  2. Repère un exposant k≥1k \geq 1 tel que ak≡1 [n]a^{k} \equiv 1 \ [n]. Un tel exposant n'existe pas toujours (par exemple, 2k≡0 [4]2^{k} \equiv 0 \ [4] pour tout k≥2k \geq 2) : si aucune puissance ne donne le reste 11, les étapes suivantes ne s'appliquent pas : conclus directement, comme ici 2N≡0 [4]2^{N} \equiv 0 \ [4] pour tout N≥2N \geq 2.
  3. Divise l'exposant NN par kk : N=kq+sN = kq + s, avec 0≤s<k0 \leq s < k.
  4. Conclus : aN=(ak)q×asa^{N} = (a^{k})^{q} \times a^{s}, donc aN≡as [n]a^{N} \equiv a^{s} \ [n] ; puis lis le reste.

ExempleExemple guidé : le jour dans $2^{50}$ jours

On cherche le reste de 2502^{50} dans la division par 77.

  • 21=22^{1} = 2, 22=42^{2} = 4 et 23=82^{3} = 8, avec 8≡1 [7]8 \equiv 1 \ [7] : on prend k=3k = 3.
  • 50=3×16+250 = 3 \times 16 + 2, avec 0≤2<30 \leq 2 < 3.
  • 250=(23)16×222^{50} = (2^{3})^{16} \times 2^{2}, donc 250≡116×4 [7]2^{50} \equiv 1^{16} \times 4 \ [7], soit 250≡4 [7]2^{50} \equiv 4 \ [7].

Le reste est 44. Lundi plus 44 jours : dans 2502^{50} jours, on sera vendredi. C'est la réponse à la question d'ouverture du chapitre.

← Étape précédenteContinuer : Un critère de divisibilité →

Étape 4 sur 5

Un critère de divisibilité

Méthodeétablir un critère de divisibilité

  1. Écris l'entier avec ses chiffres : A=ak10k+⋯+a1×10+a0A = a_k 10^{k} + \dots + a_1 \times 10 + a_0.
  2. Réduis 1010 modulo nn, par exemple 10≡1 [9]10 \equiv 1 \ [9] ou 10≡−1 [11]10 \equiv -1 \ [11], puis ses puissances.
  3. Remplace dans l'écriture de AA pour obtenir une congruence simple.
  4. Conclus : A≡0 [n]A \equiv 0 \ [n] si et seulement si n∣An \mid A.

ExempleExemple guidé : la divisibilité par 11

Comme 10≡−1 [11]10 \equiv -1 \ [11], on a 10i≡(−1)i [11]10^{i} \equiv (-1)^{i} \ [11] pour tout entier i≥1i \geq 1, et aussi pour i=0i = 0, car 100=1=(−1)010^{0} = 1 = (-1)^{0}. Pour A=918082A = 918082, on remplace chaque puissance de 1010 : A≡2−8+0−8+1−9 [11],A \equiv 2 - 8 + 0 - 8 + 1 - 9 \ [11], soit A≡−22 [11]A \equiv -22 \ [11]. Or −22=11×(−2)-22 = 11 \times (-2), donc A≡0 [11]A \equiv 0 \ [11] : 11∣91808211 \mid 918082. Contrôle : 918082=11×83462918082 = 11 \times 83462.

Attentionon ne simplifie pas une congruence

✗ « 4×5≡4×2 [12]4 \times 5 \equiv 4 \times 2 \ [12], donc 5≡2 [12]5 \equiv 2 \ [12]. »

✓ La première congruence est vraie : 20−8=1220 - 8 = 12. La seconde est fausse : 5−2=35 - 2 = 3, et 12∤312 \nmid 3. Avec les congruences, on additionne, on soustrait, on multiplie, on élève à une puissance ; on ne divise pas.

← Étape précédenteContinuer : À toi →

Étape 5 sur 5

À toi

À toi : Une divisibilité pour tout n

Montre que, pour tout entier naturel nn, 77 divise 32n+1+2n+23^{2n + 1} + 2^{n + 2}. Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Écris 32n+1=3×9n3^{2n + 1} = 3 \times 9^{n} et 2n+2=4×2n2^{n + 2} = 4 \times 2^{n}.

Encore bloqué ? Indice 2

Réduis 99 modulo 77, puis utilise les puissances.

Encore bloqué ? Indice 3

Point délicat : écris le module à chaque congruence, jusqu'à la conclusion.

Voir la solution complète

Soit nn un entier naturel. On a 9≡2 [7]9 \equiv 2 \ [7], donc 9n≡2n [7]9^{n} \equiv 2^{n} \ [7], d'après la propriété des puissances ; pour n=0n = 0, les deux membres valent 11. Par compatibilité avec la multiplication et l'addition : 32n+1+2n+2=3×9n+4×2n≡3×2n+4×2n [7].3^{2n + 1} + 2^{n + 2} = 3 \times 9^{n} + 4 \times 2^{n} \equiv 3 \times 2^{n} + 4 \times 2^{n} \ [7]. Or 3×2n+4×2n=7×2n3 \times 2^{n} + 4 \times 2^{n} = 7 \times 2^{n}, et 7×2n≡0 [7]7 \times 2^{n} \equiv 0 \ [7]. Donc 77 divise 32n+1+2n+23^{2n + 1} + 2^{n + 2}.

RemarqueCoin devoir : rédiger un calcul de reste

En devoir, chaque ligne d'un calcul de reste porte son module et sa justification. Par exemple : « 23≡1 [7]2^{3} \equiv 1 \ [7], donc (23)16≡1 [7](2^{3})^{16} \equiv 1 \ [7], d'après la propriété des puissances ». Écris la division de l'exposant, avec son reste. Termine par une phrase : « le reste de la division de … par … est … », avec un reste compris entre 00 et n−1n - 1.

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