06 29 33 79 32 Je réserve ici

Lycée · Terminale · Maths expertes (option Tle)

Arithmétique — congruences et applications

Congruences modulo n, critères de divisibilité et arithmétique modulaire (programme de Maths expertes Terminale)

À propos de cette page
Ce cours de maths expertes (option tle) en terminale sur « Arithmétique — congruences et applications » suit le programme officiel de maths expertes (option tle) de terminale. Il présente les définitions, les propriétés et les méthodes essentielles, accompagnées d'exemples résolus pour bien comprendre. Au programme : Relation de congruence modulo n, Propriétés des congruences, Classes de congruence et anneau ℤ/nℤ, Critères de divisibilité via les congruences. Chaque notion est expliquée pas à pas, puis mise en pratique grâce à des exercices interactifs, un QCM et une évaluation corrigée. Idéal pour réviser à son rythme, combler ses lacunes et progresser, en autonomie ou avec un professeur. Cours rédigé par un professeur particulier à Marseille pour aider les élèves de terminale à réussir en maths expertes (option tle).
1

Relation de congruence modulo n

Soit $n$ un entier naturel avec $n \geq 2$. Pour deux entiers relatifs $a$ et $b$, on dit que $a$ est congru à $b$ modulo $n$ si $n$ divise $a - b$, c'est-à-dire s'il existe un entier $k$ tel que $a - b = kn$.

Définition. Soit $n \geq 2$ entier. On dit que $a \equiv b \pmod{n}$ si et seulement si $n \mid (a - b)$, autrement dit $\exists k \in \mathbb{Z},\; a = b + kn$.
Exemple. $17 \equiv 5 \pmod{4}$ car $17 - 5 = 12 = 4 \times 3$.
$-3 \equiv 7 \pmod{5}$ car $-3 - 7 = -10 = 5 \times (-2)$.
$100 \equiv 0 \pmod{10}$ car $100 - 0 = 100 = 10 \times 10$.

La congruence modulo $n$ est une relation d'équivalence sur $\mathbb{Z}$ : elle est réflexive ($a \equiv a$), symétrique (si $a \equiv b$ alors $b \equiv a$), et transitive (si $a \equiv b$ et $b \equiv c$ alors $a \equiv c$).

Astuce. $a \equiv b \pmod{n}$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$. Le reste de $a$ par $n$ est l'unique entier $r \in \{0, 1, \ldots, n-1\}$ tel que $a \equiv r \pmod{n}$.
2

Propriétés des congruences

Les congruences sont compatibles avec les opérations arithmétiques : addition, soustraction et multiplication.

Théorème (compatibilité). Soient $a \equiv a' \pmod{n}$ et $b \equiv b' \pmod{n}$. Alors :
  • $a + b \equiv a' + b' \pmod{n}$
  • $a - b \equiv a' - b' \pmod{n}$
  • $a \times b \equiv a' \times b' \pmod{n}$
  • $a^k \equiv a'^k \pmod{n}$ pour tout entier $k \geq 0$
Exemple. Calculons $7^{10} \pmod{6}$.
$7 \equiv 1 \pmod{6}$ donc $7^{10} \equiv 1^{10} = 1 \pmod{6}$.
Calcul de $3^{100} \pmod{8}$ : $3^2 = 9 \equiv 1 \pmod{8}$, donc $3^{100} = (3^2)^{50} \equiv 1^{50} = 1 \pmod{8}$.
Attention ! On ne peut pas diviser librement une congruence. Par exemple, $6 \equiv 2 \pmod{4}$ mais on ne peut pas conclure $3 \equiv 1 \pmod{4}$ (ce qui est faux). La simplification par $d$ est possible uniquement si $\gcd(d, n) = 1$.

Plus précisément : si $ad \equiv bd \pmod{n}$ et $\gcd(d,n) = d'$, alors $a \equiv b \pmod{n/d'}$.

OpérationRègle
Addition$a+b \equiv a'+b' \pmod n$
Multiplication$ab \equiv a'b' \pmod n$
Puissance$a^k \equiv a'^k \pmod n$
DivisionNécessite $\gcd(d,n)=1$
3

Classes de congruence et anneau ℤ/nℤ

La classe de congruence de $a$ modulo $n$ est l'ensemble de tous les entiers congrus à $a$ modulo $n$ :

Définition. $\bar{a} = \{a + kn \mid k \in \mathbb{Z}\} = \{\ldots, a-n, a, a+n, a+2n, \ldots\}$.

Il y a exactement $n$ classes de congruence modulo $n$, représentées par $\bar 0, \bar 1, \ldots, \overline{n-1}$. L'ensemble quotient $\mathbb{Z}/n\mathbb{Z} = \{\bar 0, \bar 1, \ldots, \overline{n-1}\}$ est muni de l'addition et de la multiplication héritées de $\mathbb{Z}$, ce qui en fait un anneau.

Exemple ($n = 3$).
$\bar{0} = \{\ldots, -6, -3, 0, 3, 6, \ldots\}$ (multiples de 3)
$\bar{1} = \{\ldots, -5, -2, 1, 4, 7, \ldots\}$
$\bar{2} = \{\ldots, -4, -1, 2, 5, 8, \ldots\}$
Ces trois classes forment une partition de $\mathbb{Z}$.
Astuce. On peut toujours remplacer un entier par son reste modulo $n$ dans les calculs (reste entre 0 et $n-1$). C'est cela qui rend les calculs modulaires efficaces pour de grands nombres.
4

Critères de divisibilité via les congruences

Les critères de divisibilité classiques se démontrent élégamment grâce aux congruences. Notons $N$ un entier dont les chiffres en base 10 sont $a_k a_{k-1} \ldots a_1 a_0$, soit $N = a_0 + 10 a_1 + 100 a_2 + \cdots$

Proposition.
  • Divisibilité par 2 : $N \equiv a_0 \pmod{2}$ (dernier chiffre pair).
  • Divisibilité par 5 : $N \equiv a_0 \pmod{5}$ (dernier chiffre = 0 ou 5).
  • Divisibilité par 9 : $N \equiv a_0 + a_1 + \cdots + a_k \pmod{9}$ (somme des chiffres).
  • Divisibilité par 3 : même critère que 9, modulo 3.
  • Divisibilité par 11 : $N \equiv a_0 - a_1 + a_2 - \cdots \pmod{11}$ (somme alternée).
Preuve du critère par 9. $10 \equiv 1 \pmod{9}$, donc $10^k \equiv 1^k = 1 \pmod{9}$ pour tout $k$. Ainsi $N = \sum_{i=0}^k a_i \cdot 10^i \equiv \sum_{i=0}^k a_i \cdot 1 = \sum_{i=0}^k a_i \pmod{9}$.
Exemple. $N = 123456$. Somme des chiffres : $1+2+3+4+5+6 = 21 \equiv 3 \pmod{9}$. Donc $123456 \not\equiv 0 \pmod 9$ mais $123456 \equiv 0 \pmod 3$ (car $21 = 7\times 3$).
Attention ! Le critère de divisibilité par 11 utilise la somme alternée (signe $+$ pour un rang, $-$ pour le suivant) car $10 \equiv -1 \pmod{11}$, donc $10^k \equiv (-1)^k \pmod{11}$.
5

Équations de congruence linéaires

Une équation de congruence linéaire est de la forme $ax \equiv b \pmod{n}$, où $a, b, n$ sont des entiers donnés et $x$ est l'inconnue entière.

Théorème (existence des solutions). L'équation $ax \equiv b \pmod{n}$ admet des solutions si et seulement si $\gcd(a,n) \mid b$. Dans ce cas, il y a exactement $d = \gcd(a,n)$ classes de solutions modulo $n$, et une classe de solutions modulo $n/d$.

La méthode de résolution :

  1. Calculer $d = \gcd(a, n)$ (algorithme d'Euclide).
  2. Vérifier que $d \mid b$. Sinon, pas de solution.
  3. Diviser l'équation par $d$ : $\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{n}{d}}$.
  4. Utiliser Bézout pour trouver l'inverse de $\frac{a}{d}$ modulo $\frac{n}{d}$.
  5. Remonter les solutions modulo $n$.
Exemple. Résoudre $6x \equiv 4 \pmod{10}$.
$d = \gcd(6,10) = 2$. Comme $2 \mid 4$, il y a des solutions.
On divise par 2 : $3x \equiv 2 \pmod{5}$. Inverse de 3 mod 5 : $3 \times 2 = 6 \equiv 1 \pmod 5$, donc $3^{-1} \equiv 2 \pmod 5$.
Ainsi $x \equiv 2 \times 2 = 4 \pmod 5$.
Les solutions modulo 10 sont $x \equiv 4 \pmod{10}$ et $x \equiv 9 \pmod{10}$.
Astuce. Pour résoudre $ax \equiv 1 \pmod n$ (trouver l'inverse de $a$), on utilise l'identité de Bézout : si $au + nv = 1$, alors $au \equiv 1 \pmod n$, donc $a^{-1} \equiv u \pmod n$.
6

Petit théorème de Fermat

Ce théorème fondamental relie les puissances d'entiers aux nombres premiers.

Théorème (Fermat, 1640). Soit $p$ un nombre premier. Pour tout entier $a$ non divisible par $p$ :
$$a^{p-1} \equiv 1 \pmod{p}$$
En particulier, pour tout entier $a$ (divisible ou non par $p$) : $a^p \equiv a \pmod p$.
Exemples.
$5^6 \equiv 1 \pmod 7$ car 7 est premier et $7 \nmid 5$. Vérification : $5^2=25\equiv4$, $5^3=125\equiv6\equiv-1$, $5^6\equiv(-1)^2=1\pmod7$. ✓

Calcul de $3^{100} \pmod 7$ : $3^6 \equiv 1 \pmod 7$. $100 = 6\times16 + 4$, donc $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 81 \equiv 81 \pmod 7$. $81 = 11\times7+4$, donc $3^{100}\equiv 4\pmod 7$.
Attention ! Le théorème de Fermat est valable uniquement pour $p$ premier. Si $n$ est composé, $a^{n-1} \not\equiv 1 \pmod n$ en général (sauf pour les nombres de Carmichael, hors programme).
Méthode.} Pour calculer $a^m \pmod p$ ($p$ premier, $p\nmid a$) : écrire $m = q(p-1)+r$ avec $0\leq r<p-1$. Alors $a^m \equiv a^r \pmod p$.
7

Applications : cryptographie et codes

Les congruences sont au cœur de nombreuses applications concrètes : vérification d'identifiants, cryptographie, calendrier.

Codes de contrôle (ISBN, clé RIB). Le code ISBN-13 utilise un chiffre de contrôle $c$ tel que la somme pondérée des 13 chiffres vérifie une congruence modulo 10.

Exemple — Jour de la semaine. Le 1er janvier 2000 était un samedi (jour 6, en numérotant lundi=0 à dimanche=6). Pour trouver le jour du $n$-ième jour après le 1er janvier 2000, on calcule $(6 + n) \pmod 7$. Le 1er janvier 2001 (366 jours plus tard, 2000 est bissextile) : $(6 + 366) \pmod 7 = 372 \pmod 7$. $372 = 53\times7+1$, donc $372\equiv1\pmod7$ → lundi. ✓

Chiffrement RSA (principe). RSA repose sur l'impossibilité pratique de factoriser de grands entiers et sur le petit théorème de Fermat (ou plutôt son généralisation, le théorème d'Euler). Le message $M$ est chiffré en $C = M^e \pmod n$ et déchiffré par $C^d \pmod n = M$, où $n = pq$ est un produit de deux grands premiers.

Astuce. La puissance rapide (exponentiation modulaire) permet de calculer $a^m \pmod n$ efficacement en $O(\log m)$ multiplications, en décomposant $m$ en base 2 et en élevant successivement au carré.
À retenir
  • $a \equiv b \pmod n$ $\Leftrightarrow$ $n \mid (a-b)$ $\Leftrightarrow$ $a$ et $b$ ont le même reste par $n$.
  • Les congruences sont compatibles avec $+$, $-$, $\times$ et les puissances (pas la division en général).
  • Critère par 9 : $N \equiv$ somme des chiffres $\pmod 9$. Par 11 : somme alternée des chiffres.
  • $ax \equiv b \pmod n$ a des solutions $\Leftrightarrow$ $\gcd(a,n) \mid b$.
  • Petit théorème de Fermat : si $p$ premier et $p\nmid a$, alors $a^{p-1}\equiv 1\pmod p$.
  • Pour calculer $a^m \pmod p$, réduire $m$ modulo $p-1$.
Bloqué sur ce chapitre ?

Cours particuliers de maths expertes (option tle) à Marseille, en présentiel ou à distance — un prof qui s'adapte à ton rythme et reprend ce qui coince.

Réserver un 1er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs

benprofparticulier.fr — Soutien scolaire à Marseille (7e · 8e · 9e) · Services à la Personne déclaré N° SAP880950407 — crédit d'impôt 50%
Cours de maths expertes (option tle) Terminale · Arithmétique — congruences et applications · Besoin d'aide ? Me contacter →