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.
Relations de congruence et structures d'anneaux algébriques 🖖
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.
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.