Terminale · Mathématiques
Congruences et arithmétique modulaire
Définir la congruence modulo n dans ℤ, l'utiliser pour reconnaître deux entiers congrus et simplifier des calculs modulo n, en s'appuyant sur la compatibilité des congruences avec l'addition, la soustraction et la multiplication.
Aperçu gratuit

Les points essentiels
- Soient a et b deux entiers relatifs et n un entier naturel non nul. On dit que a est congru à b modulo n si n divise la différence a − b. On note a ≡ b [n].
- Deux entiers a et b sont congrus modulo n si et seulement si ils ont le même reste dans la division euclidienne par n.
Les mots à connaître
- Congruence modulo n
- Soient a et b deux entiers relatifs et n un entier naturel non nul. On dit que a est congru à b modulo n si n divise a − b. On note a ≡ b [n].
- Division euclidienne dans ℤ
- Pour tout entier relatif a et tout entier naturel non nul n, il existe un unique couple (q, r) d'entiers tels que a = n q + r avec 0 ≤ r < n. Le reste r est l'unique entier de [0 ; n−1] congru à a modulo n.
Un exemple pour comprendre
Calculer 2¹⁰ modulo 7.
Je remarque que 2³ = 8 et 8 = 7 × 1 + 1, donc 2³ ≡ 1 [7]. J'écris 10 = 3 × 3 + 1. Donc 2¹⁰ = (2³)³ × 2 ≡ 1³ × 2 = 2 [7]. Vérification : 2¹⁰ = 1024 et 1024 = 7 × 146 + 2, donc 1024 ≡ 2 [7].

