Horloge d'arithmétique modulaire

Choisissez le module n et l'opération. Observez le résultat sur une horloge modulaire et examinez les tables d'addition/multiplication.

Exemple résolu — Horloge d'arithmétique modulaire

Expression	7 x 5 (mod 12)
Résultat	11

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Un module premier vous rend la division 🖖

L'arithmétique modulaire traite des entiers sous un module cyclique n, noté a ≡ b (mod n). Ce système forme un anneau commutatif Z/nZ. Si le module p est premier, l'anneau devient un corps, ce qui signifie que tout élément non nul possède un inverse multiplicatif, structure fondamentale de la cryptographie moderne.

Pourquoi on parle d'arithmétique de l'horloge 🖖

Sur une horloge de 12 heures, 4 heures après 11 h il est 3 h et non 15 h : les nombres reviennent au début dès qu'ils dépassent 12. C'est exactement l'arithmétique modulaire : a ≡ b (mod n) signifie que a et b donnent le même reste lorsqu'on les divise par n. Ainsi 15 ≡ 3 (mod 12). L'essentiel : l'arithmétique modulaire ne garde que le reste de la division, et l'horloge de cet outil montre les nombres tourner en boucle.

La règle de divisibilité par 9 cache de l'arithmétique modulaire 🖖

La vieille règle « un nombre est divisible par 9 si la somme de ses chiffres l'est » relève entièrement de l'arithmétique modulaire. Comme 10 ≡ 1 (mod 9), toute puissance de 10 vaut aussi ≡ 1, si bien qu'un nombre est congru à la somme de ses chiffres (mod 9). Ce même fait fonde la preuve par neuf, une méthode vieille de plusieurs siècles pour vérifier ses calculs à la main.

ARITHMÉTIQUE MODULAIRE — QUAND PEUT-ON DIVISER, ET QUAND NON ?

Dans quel cas d’arithmétique modulaire êtes-vous ?

Travailler modulo n, c’est ne garder que le reste, et l’addition, la soustraction et la multiplication y survivent sans dommage. La division, non. Pouvoir diviser par un nombre — qu’il possède un inverse — dépend uniquement de ce qu’il partage ou non un facteur avec n, et c’est pourquoi un module premier se comporte si différemment d’un module composé. Le cas dépend de l’opération et de la nature du nombre n.

Addition — toujours bien élevée, quel que soit n 13 + 5 ≡ 6 (mod 12)

Module premier — on peut diviser par tout élément non nul φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Module composé — on ne peut diviser par presque aucun élément 2 × 3 ≡ 0, φ(6) = 2

Puissances répétées — elles bouclent, et Fermat dit où a^p−1 ≡ 1 (mod p)

Addition — toujours bien élevée, quel que soit n

Ce que vous savez: N’importe quel module. Additionner, soustraire et multiplier modulo n sont toujours définis, et tout élément a son opposé additif.

Ce qu’il faut vérifier: 13 + 5 ≡ 6 (mod 12)

Exemple résolu: Une horloge de 12 heures : 13 + 5 = 18, et 18 mod 12 = 6. Cinq heures après une heure, il est six heures.

Ouvrir ce cas: horloge mod 12

$Addition — toujours bien élevée, quel que soit n. La table d’addition modulo 12 : chaque ligne est la précédente décalée d’un cran, et chaque valeur apparaît exactement une fois. N’importe quel module. Additionner, soustraire et multiplier modulo n sont toujours définis, et tout élément a son opposé additif.$

La table d’addition modulo 12 : chaque ligne est la précédente décalée d’un cran, et chaque valeur apparaît exactement une fois.

Module premier — on peut diviser par tout élément non nul

Ce que vous savez: n est premier. Aucun élément non nul ne partage alors de facteur avec n, donc chacun possède un inverse multiplicatif.

Ce qu’il faut vérifier: φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Exemple résolu: Modulo 7 : 3 × 4 = 12 ≡ 5. Les six valeurs non nulles 1…6 sont inversibles, si bien que la table de multiplication ne contient aucun zéro hors de la première ligne.

Ouvrir ce cas: nombre premier mod 7

Module premier — on peut diviser par tout élément non nul. La table de multiplication modulo 7 : aucun zéro sous la première ligne, et chaque ligne une permutation de 1 à 6. n est premier. Aucun élément non nul ne partage alors de facteur avec n, donc chacun possède un inverse multiplicatif. — La table de multiplication modulo 7 : aucun zéro sous la première ligne, et chaque ligne une permutation de 1 à 6.

Module composé — on ne peut diviser par presque aucun élément

Ce que vous savez: n est composé. Seules les valeurs premières avec n ont un inverse ; les autres sont des diviseurs de zéro, et diviser par elles n’a aucun sens.

Ce qu’il faut vérifier: 2 × 3 ≡ 0, φ(6) = 2

Exemple résolu: Modulo 6 : 2 × 4 = 8 ≡ 2. Ni 2 ni 4 n’est inversible, puisque pgcd(2,6) = 2 et pgcd(4,6) = 2. Seuls 1 et 5 sont des unités — deux sur six.

Ouvrir ce cas: nombre composé mod 6

Module composé — on ne peut diviser par presque aucun élément. La table de multiplication modulo 6, parsemée de zéros, avec seulement deux lignes qui sont des permutations. n est composé. Seules les valeurs premières avec n ont un inverse ; les autres sont des diviseurs de zéro, et diviser par elles n’a aucun sens. — La table de multiplication modulo 6, parsemée de zéros, avec seulement deux lignes qui sont des permutations.

Puissances répétées — elles bouclent, et Fermat dit où

Ce que vous savez: Élever à une puissance modulo n. Pour p premier et a non divisible par p, les exposants se répètent avec une période divisant p − 1.

Ce qu’il faut vérifier: a^p−1 ≡ 1 (mod p)

Exemple résolu: Modulo 13 : 7¹² ≡ 1. Le petit théorème de Fermat le garantit pour toute base de 1 à 12, sans calculer la moindre grande puissance.

Ouvrir ce cas: Fermat mod 13

Puissances répétées — elles bouclent, et Fermat dit où. Les puissances de chaque base modulo 13 ; la colonne de l’exposant 12 revient à 1 pour toute unité. Élever à une puissance modulo n. Pour p premier et a non divisible par p, les exposants se répètent avec une période divisant p − 1. — Les puissances de chaque base modulo 13 ; la colonne de l’exposant 12 revient à 1 pour toute unité.

Problème entièrement résolu

Évaluer 7 12 mod 13 sur la grille complète 5 étapes
Évaluez 7¹² mod 13 sans jamais poser 7¹² par écrit. Il s'agit de l'opération a^k avec n = 13, a = 7 et k = 12, et la grille est la table complète de a^k mod 13.
1. 7¹² vaut 13 841 287 201 — onze chiffres pour un résultat qui doit se situer entre 0 et 12. La réduction est compatible avec la multiplication : le résidu d'un produit ne dépend que des résidus de ses facteurs, on peut donc réduire après chaque étape au lieu de le faire à la fin.
  
  $7^{12} = 13841287201, x y mod n = ((x mod n) (y mod n)) mod n$
2. Le petit théorème de Fermat tranche la question avant même le moindre calcul. Pour un nombre premier p et un entier a non divisible par p, a^p−1 ≡ 1 ; ici p = 13 et k vaut exactement p − 1, de sorte que le résultat est 1 et que tout ce qui suit constitue une vérification du théorème plutôt qu'une recherche du résultat.
  
  $p = 13 prime, 13 ∤ 7 ⟹ 7^{12} = 7^{p - 1} \equiv 1 (mod 13)$
3. Élever au carré double l'exposant, si bien que trois élévations au carré permettent d'atteindre 7⁸. Chaque ligne est réduite avant de passer à la suivante, c'est pourquoi aucun nombre ne dépasse 100 dans l'ensemble du calcul.
  
  $7^{2} = 49 \equiv 10, 7^{4} \equiv 1 0^{2} = 100 \equiv 9, 7^{8} \equiv 9^{2} = 81 \equiv 3 (mod 13)$
4. 12 vaut 8 + 4, et ces deux puissances ont été calculées en chemin, si bien qu'une multiplication supplémentaire suffit à conclure. Quatre multiplications au total, contre les onze qu'exigerait le produit de gauche à droite de douze sept — et le gain augmente avec l'exposant, pas avec le modulo.
  
  $12 = 110 0_{2} = 8 + 4 ⟹ 7^{12} \equiv 7^{8} \cdot 7^{4} \equiv 3 \times 9 = 27 \equiv 1 (mod 13)$
5. L'ordre de 7, c'est-à-dire le plus petit k vérifiant 7^k ≡ 1, doit diviser 12, il s'agit donc de l'un des nombres 1, 2, 3, 4, 6 et 12. Vérifier les cinq diviseurs propres permet d'éliminer chacun d'eux, l'ordre est donc exactement 12.
  
  $7^{1} \equiv 7, 7^{2} \equiv 10, 7^{3} \equiv 5, 7^{4} \equiv 9, 7^{6} \equiv 12 ⟹ ord_{13} (7) = 12$
Réponse

Les trois élévations au carré et la multiplication finale reproduisent sans erreur la ligne de l'outil pour a = 7 : 10 pour k = 2, 9 pour k = 4, 3 pour k = 8, et 1 pour k = 12, exactement là où Fermat l'avait annoncé. Puisque l'ordre est 12 et non un diviseur propre de celui-ci — le test d'ordre nécessitait 12 pour k = 6, qui n'est pas 1 — cette ligne est une permutation des nombres de 1 à 12, atteignant chaque résidu non nul exactement une fois, ce qui fait de 7 une racine primitive modulo 13. Lisez à présent la ligne dans l'autre sens : étant donné 11, trouver k. Il n'existe pas de méthode d'élévation au carré et multiplication pour cela, seulement une recherche, et cette dissymétrie entre un sens direct simple et un sens inverse complexe constitue le principe même de l'échange de clés de Diffie–Hellman. L'algorithme passe à l'échelle d'une manière impossible pour la table : un exposant de 2048 bits coûte au plus environ 4 000 multiplications modulaires, alors que la puissance correspondante nécessiterait environ 2,7 × 10⁶¹⁶ chiffres pour être écrite en entier.

$ord_{13} (7) = 12 ⟹ {7^{k} mod 13}_{k = 1}^{12} = {1, 2, \dots, 12}$

Parcours

Quand deux choses tombent sur la même valeur

Mène à Paradoxe des anniversaires

Références (1)

The congruence sign this tool prints, and the book that introduced it: C. F. Gauss, Disquisitiones arithmeticae. Leipzig, 1801 — Section I defines a ≡ b (mod n); Section II is where a prime modulus starts behaving like a field. Digitised by the Smithsonian Libraries.

Par l’équipe 42Math · Mis à jour 2026-08-17

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Mathématiques →

Exemples de problèmes

horloge mod 12 - Arithmétique de l'horloge : 13 ≡ 1 (mod 12), donc 13+5 revient à 6.
nombre premier mod 7 - Modulo premier : les lignes de multiplication non nulles se comportent comme des permutations.
nombre composé mod 6 - Un modulo composé présente des lignes répétées lorsque gcd(row,n) > 1.
Fermat mod 13 - Motif à la Fermat : a^(p-1) ≡ 1 mod p pour p premier et gcd(a,p)=1.