Les congruences

Mathématiques Expertes · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

Définitions et théorèmes

Soit n un entier naturel non nul. Pour deux entiers relatifs a et b, on dit que a est congru à b modulo n, et on note a\equiv b\pmod n, lorsque n divise a-b. De façon équivalente, a et b ont le même reste dans la division euclidienne par n.

La congruence modulo n est une relation d'équivalence : elle est réflexive, symétrique et transitive. Elle partitionne \mathbb{Z} en n classes, représentées par les restes 0,1,\dots,n-1.

Compatibilité avec les opérations. Si a\equiv b\pmod n et c\equiv d\pmod n, alors : a+c\equiv b+d\pmod n,\qquad a-c\equiv b-d\pmod n,\qquad ac\equiv bd\pmod n. En particulier, a^k\equiv b^k\pmod n pour tout entier k\ge0.

Formules

  • a\equiv b\pmod n \iff n\mid(a-b).
  • a\equiv b\pmod n \implies a^k\equiv b^k\pmod n.
  • 4\equiv1\pmod 3 donc 4^n\equiv1\pmod 3.
  • Cycles utiles : 3^n\pmod 7 a pour période 6 ; 7^n\pmod{10} a pour période 4 ; 2^n\pmod 9 a pour période 6.

Méthodes type bac

  • Reste d'une grande puissance a^k modulo n : on calcule les puissances successives a,a^2,a^3,\dots modulo n jusqu'à retrouver 1 (ou un cycle). Si la période est p, on écrit k=pq+s et a^k\equiv a^s\pmod n.
  • Chiffre des unités : c'est le reste modulo 10.
  • Démontrer une divisibilité \forall n : remplacer la base par sa classe modulo n (par exemple 4\equiv1) et conclure \equiv0.

Pièges

  • Ne jamais diviser une congruence : ac\equiv bc\pmod n n'entraîne pas a\equiv b\pmod n (sauf si \mathrm{PGCD}(c,n)=1, théorème de Gauss).
  • Confondre la période du cycle avec l'exposant : c'est k\bmod p qui compte, où p est la période.
  • Oublier que le reste doit être pris dans \{0,\dots,n-1\} (un reste de 6\equiv0\pmod 3).
  • Mélanger les modules : on ne peut combiner que des congruences relatives au même module n.

Exemple détaillé

Reste de 3^{100} modulo 7 : on calcule 3^1\equiv3, 3^2\equiv2, 3^3\equiv6, 3^4\equiv4, 3^5\equiv5, 3^6\equiv1\pmod 7. La période est 6. Comme 100=6\times16+4, on a 3^{100}=(3^6)^{16}\times3^4\equiv1^{16}\times3^4\equiv4\pmod 7. Le reste cherché est donc 4.

Pour l'épreuve

Les congruences sont l'outil central des exercices type bac d'arithmétique (calculs de restes, divisibilité, critères de divisibilité, cryptographie). La technique reine : ramener une grande puissance à un petit exposant grâce à la périodicité du cycle des puissances. Rédige proprement ce cycle et cite explicitement la compatibilité de la congruence avec les puissances. Garde en tête l'interdiction de diviser une congruence : c'est une erreur sanctionnée, sauf si le facteur est premier avec le module (théorème de Gauss). Le calcul du chiffre des unités d'une grande puissance se ramène toujours à un travail modulo 10.