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.