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
Illustration de la fiche « Congruences et arithmétique modulaire »

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].

Première page de l’Essentiel : Congruences et arithmétique modulaire
Ketty