Maths expertes — Arithmétique
Arithmétique : congruences et applications
Congruences modulo n, propriétés, petit théorème de Fermat, applications à la cryptographie
Résumé synthétiqueFiche en 5 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Les congruences sont l'arithmétique de l'horloge : sur un cadran, $14\,\text{h}$ et $2\,\text{h}$ pointent au même endroit, car ils ont le même reste modulo $12$. De même, $a \equiv b\ [n]$ signifie que $a$ et $b$ ont le même reste dans la division par $n$, c'est-à-dire que $n$ divise $a - b$. La force de cet outil : il est compatible avec l'addition, la multiplication et les puissances, ce qui permet de calculer le reste de nombres gigantesques sans jamais les écrire. Le petit théorème de Fermat ($a^{p-1} \equiv 1\ [p]$ si $p$ est premier) accélère encore ces calculs. Ces idées, autrefois purement théoriques, font tourner aujourd'hui le chiffrement RSA qui protège nos communications.
Une congruence regroupe les entiers qui « tombent au même endroit » modulo $n$. La relation se comporte presque comme une égalité : on peut additionner, multiplier et passer à la puissance des deux côtés.
- $a \equiv b\ [n]$ signifie que $n \mid (a - b)$, c'est-à-dire que $a$ et $b$ ont le même reste modulo $n$.
- Réflexivité, symétrie, transitivité : $a \equiv a$ ; si $a \equiv b$ alors $b \equiv a$ ; si $a \equiv b$ et $b \equiv c$ alors $a \equiv c$ (le tout modulo $n$).
- Compatibilité avec $+$ : si $a \equiv b\ [n]$ et $c \equiv d\ [n]$, alors $a + c \equiv b + d\ [n]$.
- Compatibilité avec $\times$ : dans les mêmes conditions, $ac \equiv bd\ [n]$.
- Puissances : $a \equiv b\ [n] \Rightarrow a^k \equiv b^k\ [n]$ pour tout entier $k \geq 1$.
Exemple
Quel est le reste de $17 \times 23$ modulo $5$ ? On réduit d'abord : $17 \equiv 2\ [5]$ et $23 \equiv 3\ [5]$. Donc $17 \times 23 \equiv 2 \times 3 = 6 \equiv 1\ [5]$. Le reste est $1$.
Piège à éviter
On peut additionner et multiplier des congruences, mais on ne peut pas diviser librement : $ac \equiv bc\ [n]$ n'entraîne $a \equiv b\ [n]$ que si $\mathrm{pgcd}(c\,;n) = 1$.
La vraie puissance des congruences : trouver le reste de $7^{100}$ sans calculer ce nombre monstrueux. L'astuce est de chercher un cycle dans les puissances successives, puis de réduire l'exposant.
- On réduit $a$ modulo $n$, puis on élève à la puissance en réduisant à chaque étape.
- On cherche une puissance qui retombe sur $1$ (ou un petit nombre) : cela crée un cycle.
- On découpe l'exposant à l'aide de ce cycle (division euclidienne de l'exposant).
- Simplification autorisée : $ac \equiv bc\ [n] \Rightarrow a \equiv b\ [n]$ uniquement si $\mathrm{pgcd}(c\,;n) = 1$.
Exemple
Reste de $2^{100}$ modulo $5$. On a $2^2 = 4 \equiv -1\ [5]$, donc $2^4 \equiv 1\ [5]$. Comme $100 = 4 \times 25$, $\ 2^{100} = (2^4)^{25} \equiv 1^{25} = 1\ [5]$. Le reste est $1$.
Piège à éviter
Pour réduire une puissance, on agit sur l'exposant via le cycle, jamais en « divisant la base par $n$ » n'importe comment. Repérer le premier retour à $1$ est la clé.
Les vieux critères de divisibilité (par $3$, $9$, $11$) ne sont pas magiques : ils se démontrent en une ligne avec les congruences, à partir du comportement de $10$ modulo $n$.
- $10 \equiv 1\ [9]$, donc $10^k \equiv 1\ [9]$ : un nombre est congru à la somme de ses chiffres modulo $9$.
- Critère par $9$ (et $3$) : un entier est divisible par $9$ (resp. $3$) si la somme de ses chiffres l'est.
- $10 \equiv -1\ [11]$, donc $10^k \equiv (-1)^k\ [11]$ : un nombre est congru à la somme alternée de ses chiffres.
- Critère par $11$ : un entier est divisible par $11$ si sa somme alternée des chiffres l'est.
Exemple
$2728$ est-il divisible par $11$ ? Somme alternée (de droite à gauche) : $8 - 2 + 7 - 2 = 11 \equiv 0\ [11]$. Donc $2728$ est divisible par $11$ (en effet $2728 = 11 \times 248$).
Piège à éviter
Pour le critère par $11$, on prend la somme alternée ($+, -, +, -$), pas la somme simple. La somme simple ($2 + 7 + 2 + 8 = 19$) ne renseigne que sur $9$ et $3$.
Le petit théorème de Fermat offre un raccourci spectaculaire pour les puissances modulo un nombre premier : dès que la base n'est pas multiple de $p$, l'exposant $p - 1$ ramène à $1$.
- Si $p$ est premier et $p \nmid a$, alors $a^{p-1} \equiv 1\ [p]$.
- Conséquence (valable pour tout $a$) : $a^p \equiv a\ [p]$.
- Usage : pour calculer $a^k\ [p]$, on écrit $k = (p-1)q + r$ et $a^k \equiv a^r\ [p]$.
- Attention : la réciproque est fausse — il existe des nombres composés (dits de Carmichael) qui imitent un premier.
Exemple
Calculons $3^{100}$ modulo $7$. Par Fermat, $3^6 \equiv 1\ [7]$. Or $100 = 6 \times 16 + 4$, donc $3^{100} = (3^6)^{16} \times 3^4 \equiv 3^4\ [7]$. Et $3^4 = 81 = 7 \times 11 + 4 \equiv 4\ [7]$. Le reste est $4$.
Piège à éviter
Fermat exige que $p$ soit premier et que $p$ ne divise pas $a$. Modulo $6$ (non premier), $a^5 \equiv 1$ est faux en général : ne l'applique jamais avec un module composé.
Toute cette arithmétique culmine dans RSA, le système qui sécurise les paiements en ligne. Son secret : il est facile de multiplier deux grands premiers, mais quasi impossible de retrouver les facteurs à partir du produit.
- On choisit deux grands premiers $p$ et $q$, on pose $n = pq$ et $\varphi(n) = (p-1)(q-1)$.
- Clé publique : un entier $e$ premier avec $\varphi(n)$. Clé privée : $d$ tel que $ed \equiv 1\ [\varphi(n)]$.
- Chiffrement : $c = m^e \bmod n$. Déchiffrement : $m = c^d \bmod n$.
- La sécurité repose sur la difficulté de factoriser $n = pq$ quand $p$ et $q$ sont très grands.
Exemple
Exemple jouet : $p = 3$, $q = 11$, donc $n = 33$ et $\varphi(n) = 2 \times 10 = 20$. On prend $e = 7$ (premier avec $20$) et on cherche $d$ tel que $7d \equiv 1\ [20]$ : $d = 3$ convient car $7 \times 3 = 21 \equiv 1\ [20]$.
Piège à éviter
Dans RSA, $d$ est l'inverse de $e$ modulo $\varphi(n)$, pas modulo $n$. Calculer $d$ avec le mauvais module rend le déchiffrement impossible.
Quiz - Congruences et applications
10 questions
S'entraîner
Notions clés — Maths expertes
Articles utiles
Questions fréquentes
Les points clés à retenir sur Arithmétique : congruences et applications, extraits du quiz de révision.
À quoi $17$ est-il congru modulo $5$ ?
Réponse :
$2$
$17 = 3 \times 5 + 2$, donc le reste est $2$ : $17 \equiv 2\ [5]$.
Si $a \equiv 3\ [7]$ et $b \equiv 5\ [7]$, alors $ab \equiv\ ?\ [7]$
Réponse :
$1$
$ab \equiv 3 \times 5 = 15 \equiv 1\ [7]$ (car $15 = 2 \times 7 + 1$).
Le reste de $2^{10}$ dans la division par $7$ est :
Réponse :
$2$
Par Fermat, $2^6 \equiv 1\ [7]$. Donc $2^{10} = 2^6 \times 2^4 \equiv 16 \equiv 2\ [7]$.
Le critère de divisibilité par $9$ repose sur le fait que :
Réponse :
$10 \equiv 1\ [9]$
$10 \equiv 1\ [9]$, donc $10^k \equiv 1\ [9]$ : un nombre est congru à la somme de ses chiffres modulo $9$.