Se adesso sono le 10 e aggiungo 5 ore, l'orologio segna le 3, non le 15. Usiamo ogni giorno un'aritmetica in cui i numeri «girano». L'aritmetica modulare formalizza questa idea ed è ovunque in informatica: tabelle hash, buffer circolari, generatori di numeri pseudocasuali, calendari, cifre di controllo e crittografia.
Divisione con resto
Dati due interi a e n con n > 0, esistono e sono unici due interi q (quoziente) e r (resto) tali che
a = q · n + r, con 0 ≤ r < n
Il resto si indica con a mod n. Per esempio 17 mod 5 = 2, perché 17 = 3 · 5 + 2. E −7 mod 5 = 3, perché −7 = (−2) · 5 + 3.
Congruenze
Due interi a e b sono congruenti modulo n se n divide la loro differenza:
a ≡ b (mod n) ⟺ n | (a − b)
Equivalentemente, a e b hanno lo stesso resto nella divisione per n. Quindi 17 ≡ 2 ≡ −3 ≡ 32 (mod 5).
La congruenza modulo n è una relazione di equivalenza, e divide gli interi in n classi: quelle dei resti 0, 1, …, n − 1. L'insieme di queste classi si indica con ℤₙ.
Le operazioni rispettano le congruenze
La proprietà che rende utile tutto questo è che somma, sottrazione e moltiplicazione sono compatibili con le congruenze: se a ≡ a′ e b ≡ b′ (mod n), allora
- a + b ≡ a′ + b′ (mod n)
- a − b ≡ a′ − b′ (mod n)
- a · b ≡ a′ · b′ (mod n)
In pratica si può ridurre modulo n in qualunque momento del calcolo, senza cambiare il risultato finale. È ciò che permette di lavorare con numeri piccoli anche quando i numeri intermedi sarebbero enormi.
Esempio: l'ultima cifra di una potenza
Qual è l'ultima cifra di 7²⁰²⁶? L'ultima cifra è il resto modulo 10. Le potenze di 7 modulo 10 sono 7, 9, 3, 1, 7, 9, 3, 1, … con periodo 4. Poiché 2026 = 4 · 506 + 2, si ha 7²⁰²⁶ ≡ 7² ≡ 9 (mod 10). L'ultima cifra è 9.
Attenzione alla divisione
La divisione non è compatibile in generale: 2 · 3 ≡ 2 · 8 (mod 10), perché 6 e 16 hanno la stessa ultima cifra, ma 3 non è congruo a 8 modulo 10. Non si può «semplificare» il 2.
Si può dividere per a modulo n solo quando a ha un inverso, cioè un numero b con a · b ≡ 1 (mod n). Questo succede esattamente quando a e n non hanno fattori comuni. Se n è primo, ogni numero non multiplo di n è invertibile, e ℤₙ si comporta come un insieme in cui tutte e quattro le operazioni sono possibili.
L'operatore modulo nei linguaggi di programmazione
Qui si nasconde una trappola. Con numeri negativi, linguaggi diversi danno risultati diversi:
| Espressione | Python | C, Java, JavaScript |
|---|---|---|
| 7 % 3 | 1 | 1 |
| −7 % 3 | 2 | −1 |
| 7 % −3 | −2 | 1 |
Python restituisce un resto con lo stesso segno del divisore, coerente con la definizione matematica quando n > 0. C, Java e JavaScript troncano il quoziente verso zero, e il resto prende il segno del dividendo.
Questo produce errori reali. Un indice in un buffer circolare calcolato come (i - 1) % n in C o in Java diventa −1 quando i = 0, e l'accesso all'array fallisce. La forma sicura è:
int indice = ((i - 1) % n + n) % n;
Potenze modulari
Calcolare aᵉ mod n con e molto grande è un'operazione centrale in crittografia. Non si calcola mai aᵉ per intero: si usa l'esponenziazione per quadrati successivi, riducendo modulo n a ogni passo. In Python è già disponibile:
pow(7, 2026, 10) # 9
pow(3, 10**18, 1000003) # risultato immediato
Il piccolo teorema di Fermat
Se p è primo e a non è multiplo di p, allora
aᵖ⁻¹ ≡ 1 (mod p)
Esempio: con p = 7 e a = 3, si ha 3⁶ = 729 = 104 · 7 + 1, quindi 3⁶ ≡ 1 (mod 7).
Due conseguenze pratiche:
- Ridurre gli esponenti: modulo un primo p, gli esponenti si possono ridurre modulo p − 1. Per esempio 3¹⁰⁰ mod 7: 100 mod 6 = 4, quindi 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).
- Test di primalità: se per qualche a si trova aⁿ⁻¹ ≢ 1 (mod n), allora n è certamente composto. Il viceversa non vale: esistono numeri composti, detti di Carmichael, che superano il test per ogni base a priva di fattori comuni con n; il più piccolo è 561. I test usati in pratica, come quello di Miller-Rabin, rafforzano questa idea.
In sintesi
- a ≡ b (mod n) significa che n divide a − b, cioè che a e b hanno lo stesso resto.
- Somma, sottrazione e moltiplicazione si possono ridurre modulo n in ogni momento.
- La divisione è possibile solo per numeri invertibili, cioè senza fattori comuni con n.
- Con i negativi, l'operatore % cambia comportamento tra i linguaggi: attenzione agli indici circolari.
- Il piccolo teorema di Fermat permette di ridurre gli esponenti e di scartare numeri composti.
