Mode d'emploi
- Choisissez l'Opération : a mod n, l'inverse, une puissance, ou le théorème des restes chinois.
- Saisissez le Nombre a, l'Exposant e et le Module n là où ils sont demandés, ou une congruence par ligne dans Congruences (une par ligne).
- Lisez Résultat. Pour l'inverse, la case Vérification indique s'il existe.
- Parcourez Détail du calcul : les tableaux montrent les lignes d'Euclide ou les chiffres binaires.
Restes, inverses et puissances
Le résidu de a modulo n est le nombre r tel que 0 ≤ r < n et a = q·n + r : a mod n n'est donc jamais négatif. Par exemple, −17 mod 5 vaut 3, car −17 = (−4)·5 + 3. Un inverse de a modulo n est un nombre x tel que a·x ≡ 1 (mod n). Il existe exactement lorsque pgcd(a ; n) = 1, et l'algorithme d'Euclide étendu le trouve. Une puissance a^e mod n se calcule par élévations au carré : on élève au carré une fois par chiffre binaire de e.
a mod n = a − n·⌊a ÷ n⌋
Si s·a + t·n = 1, alors a⁻¹ ≡ s (mod n)- De nombreuses calculatrices donnent −2 pour −17 mod 5 : c'est le reste de la division tronquée, et non le résidu modulaire, qui va toujours de 0 à n − 1.
- Une puissance à exposant négatif utilise l'inverse de a, donc n'existe que si pgcd(a ; n) = 1.
- Le tableau d'Euclide et le tableau binaire montrent chaque nombre intermédiaire, pour pouvoir vérifier le calcul à la main.
Le théorème des restes chinois et ce que le calculateur ne couvre pas
Le théorème des restes chinois trouve un nombre x qui laisse le reste rᵢ lorsqu'on le divise par mᵢ, pour chaque congruence d'un système. Lorsque les modules sont premiers entre eux deux à deux, il existe toujours une seule solution modulo leur produit. Sinon, les restes doivent être compatibles modulo les pgcd des modules, faute de quoi le système n'a pas de solution.
- Les très grands exposants, de plus de 64 chiffres binaires, sont refusés pour que le calcul reste lisible.
- Les congruences avec une variable autre que x, les congruences polynomiales et les racines carrées modulaires ne sont pas traitées.
- Le calculateur ne travaille qu'avec des nombres entiers : une décimale est refusée.
Exemple détaillé : 4¹³ mod 497, et les autres opérations
L'exposant 13 s'écrit 1101 en binaire. En partant de 1 et en élevant au carré à chaque chiffre, avec une multiplication par 4 à chaque 1, les résultats sont 4, 64, 120, puis 445 : donc 4¹³ mod 497 = 445. Le calculateur applique la même méthode, avec son tableau des chiffres.
Les autres exemples : −17 mod 5 = 3 ; l'inverse de 4 modulo 7 est 2, car 4 × 2 = 8 ≡ 1 ; et x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) a pour solution x ≡ 23 (mod 105).
| Question | Réponse |
|---|---|
| 4^13 mod 497 | 445 |
| −17 mod 5 | 3 |
| Inverse de 4 modulo 7 | 2 |
| x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7) | x ≡ 23 (mod 105) |
Questions fréquentes
Pourquoi −17 mod 5 vaut-il 3 et non −2 ?
Le résidu est le reste, qui n'est jamais négatif : 0 ≤ r < n. Comme −17 = (−4) × 5 + 3, le résidu vaut 3. De nombreuses calculatrices affichent −2, qui est le reste de la division tronquée, et non le résidu modulaire.
Quand un nombre a-t-il un inverse modulo n ?
Lorsque le pgcd de ce nombre et de n vaut 1. Par exemple, 4 a un inverse modulo 7, qui est 2, mais 4 n'en a pas modulo 6, car pgcd(4 ; 6) = 2.
Pourquoi la puissance utilise-t-elle des carrés et non des multiplications répétées ?
Élever au carré et réduire à chaque chiffre binaire garde tous les nombres petits. Pour 4¹³, la plus grande valeur intermédiaire est 484 × 4 = 1 936, alors qu'un produit direct donnerait un nombre d'environ huit chiffres.
Que se passe-t-il si les modules d'un système ont un facteur commun ?
Le système peut quand même avoir une solution. Les restes doivent être compatibles modulo le pgcd des deux modules : x ≡ 2 (mod 4) et x ≡ 8 (mod 6) sont compatibles, et la solution est x ≡ 2 (mod 12).
Mes nombres sont-ils envoyés à un serveur ?
Non. Le calcul se fait dans votre navigateur : ce que vous saisissez ne nous est pas envoyé.
Sources
- Wikipédia (en anglais) : Modular arithmetic
- Wikipédia (en anglais) : Modular exponentiation
- Wikipédia (en anglais) : Extended Euclidean algorithm
- Wikipédia (en anglais) : Chinese remainder theorem
Chiffres et texte vérifiés pour la dernière fois le mardi 10 novembre 2026.