Sciences · Mathématiques
L’arithmétique modulaire
En arithmétique modulaire, on ne garde que le reste de la division par un entier n. Deux nombres sont congrus modulo n s’ils ont le même reste : 17 ≡ 5 (mod 12), comme 17 h et 5 h sur une horloge.
Mis à jour le 4 min de lecture
Une horloge calcule « modulo 12 » : 9 h + 5 h donne 2 h, pas 14 h. Les jours de la semaine fonctionnent modulo 7, les angles modulo 360°. L’arithmétique modulaire formalise ces calculs « qui tournent en rond ». Développée systématiquement par Carl Friedrich Gauss dans ses Disquisitiones arithmeticae (1801), elle est aujourd’hui au cœur de la cryptographie, des codes de contrôle et de l’informatique.
Premiers exemples
| Congruence | Pourquoi |
|---|---|
17 ≡ 5 (mod 12) | 17 − 5 = 12 |
100 ≡ 2 (mod 7) | 100 = 7 × 14 + 2 |
−3 ≡ 4 (mod 7) | −3 − 4 = −7 |
25 ≡ 0 (mod 5) | 5 divise 25 |
n ≡ 0 (mod 2) | n est pair |
Un nombre est congru à 0 modulo n exactement quand il est un multiple de n. La parité est l’arithmétique modulo 2 (voir les nombres pairs et impairs).
Les règles de calcul
Les congruences se manipulent presque comme des égalités. Si a ≡ b (mod n) et c ≡ d (mod n), alors :
a + c ≡ b + d (mod n);a − c ≡ b − d (mod n);a × c ≡ b × d (mod n);aᵏ ≡ bᵏ (mod n)pour tout entier naturel k.
On peut donc remplacer chaque nombre par son reste avant de calculer, ce qui garde les nombres petits.
Ce qui ne marche pas : la division
On ne peut pas simplifier librement. 2 × 3 ≡ 2 × 8 (mod 10) (6 et 16), mais 3 ≢ 8 (mod 10). La simplification par a est permise seulement si a et n sont premiers entre eux. Un nombre a a un inverse modulo n (un x tel que ax ≡ 1 (mod n)) si et seulement si PGCD(a, n) = 1 : c’est une conséquence du théorème de Bézout. Lorsque n est premier, tout nombre non multiple de n est inversible.
Applications de tous les jours
Le calendrier
Une année non bissextile compte 365 = 7 × 52 + 1 jours : une date tombe donc un jour de la semaine plus tard l’année suivante (deux jours plus tard après un 29 février).
Les critères de divisibilité
10 ≡ 1 (mod 9), donc 10ᵏ ≡ 1 (mod 9) : un nombre est congru à la somme de ses chiffres modulo 9. D’où le critère de divisibilité par 9 (et par 3). De même 10 ≡ −1 (mod 11) donne le critère par 11 avec la somme alternée (voir les critères de divisibilité). La « preuve par 9 » des calculs posés repose sur la même idée.
Les clés de contrôle
Les numéros ISBN, IBAN, de sécurité sociale ou de carte bancaire contiennent une clé calculée modulo un nombre (11, 97, 10…). Une faute de frappe change le reste et l’erreur est détectée. Pour l’IBAN, le numéro réarrangé doit être congru à 1 modulo 97.
La cryptographie
Le chiffrement RSA repose sur des puissances modulo un très grand nombre n = p × q (produit de deux nombres premiers) et sur le petit théorème de Fermat généralisé par Euler. L’échange de clés de Diffie-Hellman utilise aussi des puissances modulaires (voir le chiffrement HTTPS).
En programmation
L’opérateur % donne le reste : 17 % 5 vaut 2. On s’en sert pour tester la parité, faire boucler un index dans un tableau ou répartir des données. Attention, avec des nombres négatifs, le résultat de % dépend du langage.
Résoudre une congruence simple
Erreurs fréquentes
- Diviser les deux membres sans vérifier que le diviseur est premier avec n.
- Donner un reste négatif : le reste de −3 modulo 7 est 4.
- Confondre
≡et=:17 ≡ 5 (mod 12)mais 17 ≠ 5.
Questions fréquentes
Que veut dire « modulo » ?
« a modulo n » est le reste de la division euclidienne de a par n. Dire que deux nombres sont égaux modulo n signifie qu’ils ont le même reste.
Comment calculer un modulo à la main ?
On divise et on garde le reste : 47 mod 5 = 2 car 47 = 5 × 9 + 2. Pour une grande puissance, on cherche un cycle dans les restes.
À quoi sert l’arithmétique modulaire ?
Au calendrier, aux clés de contrôle (IBAN, ISBN), au hachage et au chiffrement des données, aux générateurs de nombres pseudo-aléatoires.
Pourquoi ne peut-on pas diviser modulo n ?
Parce qu’un nombre n’a pas toujours d’inverse modulo n. Il en a un seulement s’il est premier avec n ; c’est toujours le cas pour les nombres non multiples de n lorsque n est premier.