| Reste r | Quotient q | Multiplicateur t |
|---|
Horloge modulaire
Cinq heures après 9 heures, il est 2 heures, car 9 + 5 = 14 et 14 dépasse 12 de 2. C'est cela, l'arithmétique modulaire : compter sur une horloge qui repart de 0 après n. Choisissez une opération, saisissez n, a et b, et la calculatrice donne la réponse avec chaque étape détaillée, du reste d'une division à l'exponentiation rapide et à l'algorithme d'Euclide étendu, tandis que l'horloge montre comment on arrive à la réponse. Choisissez une opération, puis saisissez le module n et les nombres a et b ; les entiers jusqu'à 30 chiffres sont acceptés, négatifs compris, et n peut aller jusqu'à 10^18. L'horloge compte n positions avec 0 en haut, et son aiguille indique la réponse. L'addition et la soustraction sont dessinées comme une spirale de b pas, avec un anneau par tour complet ; la multiplication comme des sauts de a ; les puissances comme les cordes a, a², a³ …, qui se referment en un cycle ; l'inverse et la division comme les multiples qui tombent sur 1 ou sur a. Les étapes montrent le même calcul en chiffres. Jusqu'à mod 20, la table de l'opération est affichée ; cliquez sur une case pour utiliser ses nombres. Exemple remplit un problème classique.
Comment ça marche
- Choisissez une opération : a mod n, addition, soustraction, multiplication, division, puissance ou inverse de a.
- Saisissez le module n et les nombres a et b, ou choisissez un exemple comme le dernier chiffre de 7^2026 ou un petit message RSA.
- Lisez la réponse et les étapes, suivez le chemin sur l'horloge et, jusqu'à mod 20, cliquez sur une case de la table pour essayer ses nombres.
Ce que signifie a mod n
a mod n est le reste de la division de a par n : 17 mod 5 = 2, car 17 = 3 × 5 + 2. Le reste est toujours compris entre 0 et n − 1, même pour les nombres négatifs : −7 mod 3 = 2, car −7 = −3 × 3 + 2. Sur l'horloge, cela revient à reculer de 7 pas à partir de 0. Deux nombres ayant le même reste sont congrus, ce qui s'écrit 17 ≡ 2 (mod 5), une notation introduite par Carl Friedrich Gauss en 1801. Les sommes, différences et produits peuvent être réduits mod n à chaque étape, ce qui garde les nombres petits.
Où l'on utilise l'arithmétique modulaire
Les horloges et les calendriers fonctionnent mod 12, mod 24 et mod 7 : 100 jours après un mercredi, c'est un vendredi, car 100 mod 7 = 2. Les chiffres de contrôle s'en servent pour détecter les fautes de frappe, des numéros ISBN-10 (mod 11) aux numéros de carte bancaire (mod 10) et aux IBAN (mod 97). Les chiffrements décalent les lettres mod 26, et le chiffre affine a besoin d'un inverse mod 26 pour déchiffrer. RSA, qui protège une grande partie d'Internet, chiffre un message m en m^e mod n et le déchiffre avec une autre puissance : avec n = 3233, 65^17 mod 3233 = 2790 et 2790^413 mod 3233 = 65.
Questions fréquemment posées
Comment calculer a mod n pour un nombre négatif ?
Ajoutez ou retranchez des multiples de n jusqu'à ce que le nombre soit compris entre 0 et n − 1. Pour −7 mod 3 : −7 + 9 = 2, la réponse est donc 2. Certains langages de programmation donnent plutôt −1 pour −7 % 3, car ils arrondissent le quotient vers zéro ; en mathématiques, le reste n'est jamais négatif.
Qu'est-ce qu'un inverse modulaire ?
L'inverse de a mod n est le nombre x tel que a × x ≡ 1 (mod n). L'inverse de 7 mod 26 est 15, car 7 × 15 = 105 = 4 × 26 + 1. Il n'existe que si a et n n'ont aucun facteur commun, et l'algorithme d'Euclide étendu permet de le trouver. Diviser par a mod n revient à multiplier par son inverse.
Comment calculer une puissance comme 7^2026 mod n ?
Par exponentiation rapide : élevez 7 au carré encore et encore, en réduisant mod n à chaque fois, pour obtenir 7^1, 7^2, 7^4, 7^8 et ainsi de suite, puis multipliez celles qui composent 2026 en binaire. Cela demande 10 élévations au carré et 7 multiplications au lieu de 2 025 multiplications, et les nombres ne dépassent jamais n². 7^2026 se termine par 9.
Pourquoi l'horloge affiche-t-elle 0 au lieu de 12 ?
En arithmétique modulaire, les restes vont de 0 à n − 1, donc sur une horloge à 12 positions, midi correspond à 0. 12 ≡ 0 (mod 12) ; une horloge ordinaire affiche simplement 12 là où les mathématiques écrivent 0.
Quelle taille peuvent avoir les nombres ?
a et b peuvent compter jusqu'à 30 chiffres et être négatifs, et le module peut aller jusqu'à 10^18. La calculatrice travaille avec des entiers exacts dans votre navigateur, si bien que même des exemples de la taille de RSA donnent des réponses exactes, et rien n'est envoyé nulle part.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur