L'arithmétique modulaire expliquée

Tout le monde pratique déjà l'arithmétique modulaire : 10 heures après 8 heures, il est 6 heures, et le lendemain du dimanche est le lundi. Compter en repartant de 0 après n pas se révèle avoir sa propre arithmétique complète, avec ses règles, ses surprises et une place centrale dans la théorie des nombres et dans la cryptographie qui protège Internet.

Une horloge à douze positions numérotées de 0 à 11 et un chemin en spirale qui fait une fois le tour du cadran de 9 à 2
Une horloge à douze positions numérotées de 0 à 11 et un chemin en spirale qui fait une fois le tour du cadran de 9 à 2

Restes et congruence

Divisez a par n et ne gardez que le reste : c'est a mod n, un nombre de 0 à n − 1. 26 mod 7 = 5, car 26 = 3 × 7 + 5. Les nombres qui ont le même reste se comportent de la même façon mod n, c'est pourquoi on les dit congrus : 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss a introduit cette notation dans ses Disquisitiones Arithmeticae de 1801, et elle a fait des anciennes observations de Fermat et d'Euler une arithmétique à part entière. Sur une horloge à n positions, chaque entier tombe sur son reste ; les tours complets sont oubliés.

Carl Friedrich Gauss, sur un portrait de Christian Albrecht Jensen de 1840. Il introduisit la notation de congruence a ≡ b (mod n) dans ses Disquisitiones Arithmeticae de 1801.
Carl Friedrich Gauss, sur un portrait de Christian Albrecht Jensen de 1840. Il introduisit la notation de congruence a ≡ b (mod n) dans ses Disquisitiones Arithmeticae de 1801.

Additionner, soustraire et multiplier

Les trois opérations ordinaires fonctionnent comme d'habitude, et vous pouvez réduire mod n quand vous le voulez : le reste d'une somme est le reste de la somme des restes, et il en va de même pour les différences et les produits. Pour trouver le dernier chiffre de 37 × 48, multipliez seulement les derniers chiffres : 7 × 8 = 56, le résultat se termine donc par 6. C'est ce qui rend l'arithmétique modulaire si utile aux ordinateurs : quelle que soit la taille des nombres, les valeurs intermédiaires ne dépassent jamais n².

La division exige un inverse

La division est l'exception. 2 × 3 ≡ 2 × 8 (mod 10), puisque les deux valent 6 mod 10, et pourtant 3 et 8 sont différents : on ne peut donc pas simplement supprimer le facteur 2. Diviser par a revient à multiplier par son inverse, le nombre x tel que a × x ≡ 1, qui existe exactement lorsque a et n n'ont aucun facteur commun. L'algorithme d'Euclide étendu le trouve : il effectue les divisions successives d'Euclide pour le plus grand commun diviseur et tient le compte d'un multiplicateur à chaque étape, de sorte que lorsque le reste atteint 1, le multiplicateur est l'inverse. Lorsque n est premier, tout nombre sauf 0 a un inverse, et la division fonctionne toujours.

Puissances, Fermat et Euler

Les puissances se répètent. Prenez les puissances de 3 mod 7 : 3, 2, 6, 4, 5, 1, puis de nouveau 3. La longueur de ce cycle est l'ordre de 3. En 1640, Pierre de Fermat remarqua que pour un nombre premier p, a^(p − 1) ≡ 1 (mod p) dès que p ne divise pas a, de sorte que tout ordre divise p − 1. Leonhard Euler le démontra et l'étendit à tout n, en remplaçant p − 1 par le nombre de valeurs premières avec n. Les puissances énormes se calculent par exponentiation rapide : a, a², a⁴, a⁸ …, chacune étant le carré de la précédente, réduite mod n, puis multipliées selon les chiffres binaires de l'exposant.

Portrait de Pierre de Fermat
Portrait de Pierre de Fermat
Portrait de Leonhard Euler
Portrait de Leonhard Euler

Chiffres de contrôle et calendriers

L'arithmétique modulaire détecte les erreurs. Le dernier chiffre d'un ISBN-10 est choisi pour qu'une somme pondérée des dix chiffres soit un multiple de 11, si bien que toute erreur sur un seul chiffre et toute inversion de deux chiffres voisins est détectée. Les numéros de carte bancaire utilisent le contrôle de Luhn mod 10, et les IBAN un contrôle mod 97. Les calendriers fonctionnent mod 7 : le jour de la semaine de n'importe quelle date se calcule avec quelques restes, et c'est ainsi que fonctionnent les calendriers perpétuels et la méthode doomsday.

Cryptographie

La cryptographie moderne repose sur des puissances modulaires faciles à calculer et difficiles à inverser. Dans l'échange de clés Diffie–Hellman de 1976, deux personnes conviennent d'un secret commun sur une ligne ouverte en échangeant des puissances modulo un grand nombre premier. RSA, publié en 1977 par Rivest, Shamir et Adleman, chiffre un message m en m^e mod n, où n est le produit de deux grands nombres premiers, et déchiffre avec un second exposant d que seul quelqu'un qui connaît les deux nombres premiers peut calculer. Dans l'exemple classique des manuels, n = 3233 = 61 × 53, e = 17 et d = 413 : 65 devient 2790, et 2790 redevient 65.

À vous d'explorer

Ouvrez l'horloge modulaire pour calculer a mod n, sommes, différences, produits, puissances, inverses et quotients mod n, pour des nombres jusqu'à 30 chiffres. Chaque réponse est accompagnée de ses étapes : la division avec reste, les puissances de l'exponentiation rapide ou la table de l'algorithme d'Euclide étendu. L'horloge dessine comment on arrive à la réponse, de la spirale d'une addition au cycle des puissances, et pour les petits n, la table de l'opération montre toutes les réponses à la fois.

Questions fréquemment posées

Que signifie le symbole ≡ ?

a ≡ b (mod n) signifie que a et b ont le même reste dans la division par n, ou, de façon équivalente, que n divise a − b. 38 ≡ 2 (mod 12), car 38 − 2 = 36 est un multiple de 12.

mod est-il identique à l'opérateur % en programmation ?

Pour les nombres positifs, oui. Pour les nombres négatifs, de nombreux langages comme C, Java et JavaScript renvoient un reste négatif : −7 % 3 y vaut −1, alors que −7 mod 3 = 2. L'opérateur % de Python suit la convention mathématique pour un n positif.

Qu'est-ce que l'ordre d'un nombre mod n ?

Le plus petit k > 0 tel que a^k ≡ 1 (mod n). Il n'existe que si a et n n'ont aucun facteur commun. L'ordre de 2 mod 7 est 3, car 2³ = 8 ≡ 1, et l'ordre de 3 mod 7 est 6, donc les puissances de 3 parcourent tous les restes non nuls : 3 est une racine primitive mod 7.

Qui a inventé l'arithmétique modulaire ?

Les restes étaient utilisés bien avant, par exemple dans le théorème des restes chinois, entre le IIIe et le Ve siècle, ainsi que par Fermat et Euler. Gauss en a fait une arithmétique systématique, avec la notation des congruences, en 1801.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Ouvrir l'horloge modulaire