Congruences : exercices corrigés

Les congruences permettent de calculer avec les restes de divisions. Ces exercices utilisent les propriétés des congruences pour trouver un reste, calculer une grande puissance, résoudre une équation et démontrer une divisibilité.

Mathématiques · Terminale ·

Congruences modulo n

Deux entiers a et b sont congrus modulo n, noté a ≡ b [n], si leur différence est un multiple de n, c'est-à-dire s'ils ont le même reste dans la division par n.

  • Si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n] et a × c ≡ b × d [n].
  • Si a ≡ b [n], alors aᵏ ≡ bᵏ [n] pour tout entier k ≥ 0.
  • a est divisible par n si et seulement si a ≡ 0 [n].
  • Pour étudier un entier, on distingue souvent les cas selon son reste modulo n.

Exercice 1 Trouver un reste

1. Trouver le reste de la division de 100 par 7.

2. Trouver un entier compris entre 0 et 11 congru à 17 modulo 12.

Un indice

Divisez par le modulo et regardez le reste.

Voir la correction

1. 100 = 7 × 14 + 2, donc 100 ≡ 2 [7] : le reste est 2.

2. 17 = 12 × 1 + 5, donc 17 ≡ 5 [12].

Le nombre 5 est le seul entier entre 0 et 11 congru à 17 modulo 12.

Exercice 2 Une grande puissance

Déterminer le reste de la division de 7²⁰²⁶ par 5.

Un indice

Remplacez 7 par un nombre plus petit congru modulo 5, puis cherchez la période des puissances.

Voir la correction

7 ≡ 2 [5], donc 7²⁰²⁶ ≡ 2²⁰²⁶ [5]. Les puissances de 2 modulo 5 sont : 2, 4, 3, 1, puis le cycle recommence (période 4).

2026 = 4 × 506 + 2, donc 2²⁰²⁶ ≡ (2⁴)⁵⁰⁶ × 2² ≡ 1 × 4 = 4 [5].

Le reste de la division de 7²⁰²⁶ par 5 est 4.

Exercice 3 Résoudre une congruence

Résoudre dans ℤ la congruence 3x ≡ 2 [7].

Un indice

Cherchez un entier k tel que 3k ≡ 1 [7] et multipliez la congruence par k.

Voir la correction

On a 3 × 5 = 15 ≡ 1 [7]. En multipliant les deux membres de 3x ≡ 2 par 5 : 15x ≡ 10 [7], soit x ≡ 10 ≡ 3 [7].

Vérification : pour x = 3, 3 × 3 = 9 ≡ 2 [7].

Les solutions sont les entiers x = 3 + 7k, avec k entier relatif.

Exercice 4 Une divisibilité

Démontrer que, pour tout entier n, n³ − n est divisible par 3.

Un indice

Étudiez les trois cas n ≡ 0, n ≡ 1 et n ≡ 2 modulo 3.

Voir la correction

Si n ≡ 0 [3], alors n³ − n ≡ 0 − 0 = 0 [3].

Si n ≡ 1 [3], alors n³ − n ≡ 1 − 1 = 0 [3]. Si n ≡ 2 [3], alors n³ − n ≡ 8 − 2 = 6 ≡ 0 [3].

Dans tous les cas, n³ − n ≡ 0 [3] : n³ − n est divisible par 3 pour tout entier n.

Les erreurs à éviter

  • Confondre le quotient et le reste d'une division.
  • Diviser les deux membres d'une congruence sans vérifier que c'est licite : on multiplie plutôt par un inverse modulo n.
  • Oublier de vérifier tous les cas possibles de restes dans une preuve par disjonction de cas.
  • Oublier la période pour calculer les grandes puissances.

Questions fréquentes

Que signifie a ≡ b [n] ?

Que a et b ont le même reste dans la division par n, ou encore que n divise a − b.

Pourquoi chercher une période ?

Parce que les puissances d'un nombre modulo n finissent par se répéter : il suffit de connaître le cycle pour calculer un reste, même pour un exposant gigantesque.

À quoi servent les congruences ?

À la cryptographie, aux codes-barres et aux numéros de sécurité sociale, qui utilisent des clés calculées modulo un nombre.

À revoir avant

Prêt à faire le point ?

Un premier rendez-vous de 30 minutes, offert, pour faire connaissance avec l'élève et ses parents.

ou appeler le +33 7 45 30 60 01