Dernière mise à jour : 2026-06-05

L'arithmétique modulaire est la branche de la théorie des nombres qui étudie les entiers réduits par rapport à un diviseur fixe appelé le modulo. Deux entiers sont congrus modulo n s'ils diffèrent d'un multiple de n, ce que l'on note a ≡ b (mod n). Ce calculateur évalue trois opérations fondamentales : le reste de la division euclidienne, l'exponentiation modulaire rapide et l'inverse modulaire.

L'opération modulo

Pour un modulo n ≥ 1, l'opération a mod n est définie comme l'unique entier r dans [0, n − 1] vérifiant :

$a = q \times n + r$

où q = ⌊a / n⌋ est le quotient entier et r le reste. Cette définition garantit un résultat toujours positif ou nul, contrairement au reste de la division tronquée employé dans certains langages de programmation.

Exemple. Pour a = 17 et n = 5 :

$q = \left\lfloor \frac{17}{5} \right\rfloor = 3 \qquad r = 17 - 3 \times 5 = 2$

Donc 17 mod 5 = 2. Cette valeur correspond à l'arithmétique de l'horloge : en avançant de 17 graduations sur un cadran à 5 positions, on arrive à la position 2.

Cas des entiers négatifs. Pour a = −7 et n = 5 :

$q = \left\lfloor \frac{-7}{5} \right\rfloor = -2 \qquad r = -7 - (-2) \times 5 = 3$

Donc −7 mod 5 = 3. La définition mathématique maintient r positif. L'opérateur % de C, JavaScript ou Python 2 renverrait −2, ce qui illustre la différence entre le reste tronqué et le modulo au sens mathématique.

Exponentiation modulaire

Calculer a^b mod n en procédant d'abord au calcul de a^b puis en réduisant modulo n est impraticable pour de grands exposants, car a^b croît exponentiellement. La méthode d'élévation au carré répétée (square-and-multiply) contourne ce problème en réduisant modulo n à chaque étape.

L'algorithme décompose l'exposant en représentation binaire. En partant de 1, à chaque bit de b (du moins significatif au plus significatif) :

• on élève au carré la puissance courante de la base, réduite modulo n ;
• si le bit vaut 1, on multiplie le résultat intermédiaire par cette puissance, réduit modulo n.

Le nombre total de multiplications est au plus 2 log₂(b), et toutes les valeurs intermédiaires restent dans [0, n − 1].

Exemple. Pour a = 17, b = 3, n = 5 :

$17 \equiv 2 \pmod{5}$

$17^2 \equiv 4 \pmod{5}$

$17^3 = 17^2 \times 17 \equiv 4 \times 2 = 8 \equiv 3 \pmod{5}$

Donc 17^3 mod 5 = 3. Vérification directe : 17^3 = 4 913 = 982 × 5 + 3.

Inverse modulaire

L'inverse modulaire de a modulo n est un entier x vérifiant :

$a \times x \equiv 1 \pmod{n}$

Cet inverse existe si et seulement si pgcd(a, n) = 1, c'est-à-dire si a et n sont premiers entre eux. Lorsque n est premier, tout entier de 1 à n − 1 admet un inverse. Lorsque n est composé, tout entier partageant un facteur commun avec n n'en a pas.

L'algorithme d'Euclide étendu permet de calculer cet inverse lorsqu'il existe. Il prolonge l'algorithme d'Euclide classique en suivant les combinaisons linéaires, ce qui produit des entiers s et t tels que :

$a \times s + n \times t = \text{pgcd}(a, n)$

Lorsque pgcd(a, n) = 1, s est l'inverse modulaire de a mod n.

Exemple. Pour a = 3, n = 5 :

Application de l'algorithme d'Euclide étendu :

• 5 = 1 × 3 + 2
• 3 = 1 × 2 + 1

Remontée : 1 = 3 − 1 × 2 = 3 − 1 × (5 − 1 × 3) = 2 × 3 − 1 × 5

Donc 3 × 2 ≡ 1 (mod 5), soit 3⁻¹ ≡ 2 (mod 5).

Vérification : 3 × 2 = 6 = 1 × 5 + 1.

Applications

L'arithmétique modulaire est omniprésente en mathématiques et en informatique :

• Cryptographie à clé publique. RSA chiffre un message en l'élevant à un grand exposant modulo le produit de deux nombres premiers. Le déchiffrement utilise l'inverse modulaire de l'exposant de chiffrement.
• Codes de contrôle. La norme ISBN-13, l'IBAN et l'algorithme de Luhn (numéros de carte bancaire) exploitent l'arithmétique modulaire pour détecter les erreurs de saisie.
• Calculs calendaires. Le jour de la semaine après d jours se calcule modulo 7 ; la date de Pâques repose sur des congruences cycliques.
• Tables de hachage. Un élément est assigné à un compartiment selon la formule clé mod taille_table.
• Structures circulaires. Les tampons en anneau et les tableaux circulaires avancent leur pointeur de lecture ou d'écriture par index mod capacité.

Quotient entier et identité euclidienne

Pour tout couple (a, n) avec n ≥ 1, le quotient entier q = ⌊a / n⌋ et le reste r = a mod n satisfont l'identité euclidienne :

$a = q \times n + r, \qquad 0 \leq r < n$

Ce calculateur affiche à la fois r et q, ce qui permet de vérifier l'identité directement pour n'importe quelle valeur saisie.