L'aritmetica modulare spiegata
Tutti fanno già aritmetica modulare: 10 ore dopo le 8 sono le 6, e il giorno dopo la domenica è lunedì. Contare ricominciando da 0 dopo n passi si rivela avere un'aritmetica completa tutta sua, con regole, sorprese e un posto centrale nella teoria dei numeri e nella crittografia che protegge Internet.
Resti e congruenza
Dividi a per n e tieni solo il resto: questo è a mod n, un numero da 0 a n − 1. 26 mod 7 = 5, perché 26 = 3 × 7 + 5. I numeri con lo stesso resto si comportano allo stesso modo mod n, per questo li chiamiamo congruenti: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss introdusse questa notazione nelle sue Disquisitiones Arithmeticae del 1801, e trasformò le vecchie osservazioni di Fermat ed Euler in un'aritmetica a sé stante. Su un orologio con n posizioni ogni numero intero cade sul proprio resto; i giri completi vengono dimenticati.
Addizione, sottrazione e moltiplicazione
Le tre operazioni ordinarie funzionano come al solito, e puoi ridurre mod n quando vuoi: il resto di una somma è il resto della somma dei resti, e lo stesso vale per differenze e prodotti. Per trovare l'ultima cifra di 37 × 48, moltiplica solo le ultime cifre: 7 × 8 = 56, quindi finisce con 6. È questo che rende l'aritmetica modulare così utile per i computer: per quanto grandi siano i numeri, i valori intermedi non superano mai n².
La divisione richiede un inverso
La divisione è l'eccezione. 2 × 3 ≡ 2 × 8 (mod 10), poiché entrambi valgono 6 mod 10, eppure 3 e 8 sono diversi, quindi non puoi semplicemente cancellare il 2. Dividere per a significa moltiplicare per il suo inverso, il numero x con a × x ≡ 1, che esiste esattamente quando a e n non hanno fattori comuni. L'algoritmo di Euclide esteso lo trova: esegue i passi di divisione di Euclide per il massimo comun divisore e tiene traccia di un moltiplicatore a ogni passo, così che quando il resto arriva a 1 il moltiplicatore è l'inverso. Quando n è primo, ogni numero tranne 0 ha un inverso, e la divisione funziona sempre.
Potenze, Fermat ed Euler
Le potenze si ripetono. Prendi le potenze di 3 mod 7: 3, 2, 6, 4, 5, 1, e poi di nuovo 3. La lunghezza di questo ciclo è l'ordine di 3. Nel 1640 Pierre de Fermat notò che, per un primo p, a^(p − 1) ≡ 1 (mod p) ogni volta che p non divide a, quindi ogni ordine divide p − 1. Leonhard Euler lo dimostrò e lo estese a qualsiasi n, sostituendo p − 1 con il numero di valori coprimi con n. Le potenze enormi si calcolano con i quadrati ripetuti: a, a², a⁴, a⁸ …, ciascuna il quadrato della precedente, ridotta mod n, e poi moltiplicate secondo le cifre binarie dell'esponente.
Cifre di controllo e calendari
L'aritmetica modulare scopre gli errori. L'ultima cifra di un ISBN-10 è scelta in modo che una somma pesata di tutte e dieci le cifre sia un multiplo di 11, così viene rilevata ogni singola cifra sbagliata e ogni scambio di due cifre vicine. I numeri delle carte di pagamento usano il controllo di Luhn mod 10, e gli IBAN un controllo mod 97. I calendari funzionano mod 7: il giorno della settimana di qualsiasi data si ricava con pochi resti, ed è così che funzionano i calendari perpetui e la regola del doomsday.
Crittografia
La crittografia moderna si basa su potenze modulari facili da calcolare e difficili da invertire. Nello scambio di chiavi Diffie–Hellman del 1976, due persone concordano un segreto comune su una linea aperta scambiandosi potenze modulo un grande numero primo. RSA, pubblicato nel 1977 da Rivest, Shamir e Adleman, cifra un messaggio m come m^e mod n, dove n è il prodotto di due grandi numeri primi, e decifra con un secondo esponente d che solo chi conosce i due primi può calcolare. Nell'esempio da manuale, n = 3233 = 61 × 53, e = 17 e d = 413: 65 diventa 2790, e 2790 torna a essere 65.
Esploralo
Apri l'orologio modulare per calcolare a mod n, somme, differenze, prodotti, potenze, inversi e quozienti mod n, per numeri fino a 30 cifre. Ogni risultato è accompagnato dai suoi passaggi: la divisione con resto, le potenze dei quadrati ripetuti o la tabella dell'algoritmo di Euclide esteso. L'orologio disegna come si arriva al risultato, dalla spirale di un'addizione al ciclo delle potenze, e per n piccoli la tabella dell'operazione mostra tutti i risultati in una volta.
Domande frequenti
Che cosa significa il simbolo ≡?
a ≡ b (mod n) dice che a e b danno lo stesso resto quando sono divisi per n, o, in modo equivalente, che n divide a − b. 38 ≡ 2 (mod 12), perché 38 − 2 = 36 è un multiplo di 12.
mod è uguale all'operatore % nella programmazione?
Per i numeri positivi sì. Per i numeri negativi molti linguaggi, come C, Java e JavaScript, restituiscono un resto negativo: lì −7 % 3 vale −1, mentre −7 mod 3 = 2. L'operatore % di Python segue la convenzione matematica per n positivo.
Che cos'è l'ordine di un numero mod n?
Il più piccolo k > 0 con a^k ≡ 1 (mod n). Esiste solo quando a e n non hanno fattori comuni. L'ordine di 2 mod 7 è 3, perché 2³ = 8 ≡ 1, e l'ordine di 3 mod 7 è 6, quindi le potenze di 3 percorrono tutti i resti diversi da zero: 3 è una radice primitiva mod 7.
Chi ha inventato l'aritmetica modulare?
I resti erano usati molto prima, per esempio nel teorema cinese del resto, tra il III e il V secolo, e da Fermat ed Euler. Gauss ne fece un'aritmetica sistematica, con la notazione delle congruenze, nel 1801.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri l'orologio modulare