Ultimo aggiornamento: 2026-06-05

L'aritmetica modulare è il ramo della teoria dei numeri che studia i numeri interi ridotti rispetto a un divisore fisso, detto modulo. Due interi sono congruenti modulo n se la loro differenza è un multiplo di n, e si scrive a ≡ b (mod n). Questo calcolatore valuta tre operazioni fondamentali: il resto della divisione intera, la potenza modulare veloce e l'inverso modulare.

L'operazione modulo

Per un modulo positivo n, il modulo matematico a mod n è definito come l'unico intero r nell'intervallo [0, n − 1] che soddisfa:

$a = q \times n + r$

dove q = ⌊a / n⌋ è il quoziente intero e r è il resto. Questa definizione garantisce sempre un risultato non negativo, a differenza del resto con troncamento verso zero usato in molti linguaggi di programmazione.

Esempio con valori positivi. Per a = 17 e n = 5:

$q = \lfloor 17 / 5 \rfloor = 3$

$r = 17 - 3 \times 5 = 2$

Quindi 17 mod 5 = 2. Il risultato corrisponde all'aritmetica dell'orologio: contando 17 posizioni su un quadrante di cinque tacche si arriva alla posizione 2.

Valori negativi. Per a = −7 e n = 5:

$q = \lfloor -7 / 5 \rfloor = -2$

$r = -7 - (-2) \times 5 = 3$

Quindi −7 mod 5 = 3, non −2. La definizione matematica mantiene r non negativo; l'operatore % di linguaggi come C, JavaScript e Python 2 restituirebbe invece −2.

Potenza modulare

Calcolare a^b mod n per via diretta — prima elevando a alla b e poi riducendo — è impraticabile per esponenti grandi, perché a^b cresce esponenzialmente. La potenza modulare veloce (algoritmo square-and-multiply) evita questo problema riducendo modulo n a ogni passo.

L'algoritmo decompone l'esponente in binario. Partendo da risultato = 1:

• Per ogni bit di b, dal meno significativo al più significativo, si eleva al quadrato la base corrente modulo n.
• Quando il bit vale 1, si moltiplica il risultato per la potenza della base corrente, riducendo modulo n.

Il numero di moltiplicazioni necessarie è al più 2 log₂(b), e ogni valore intermedio rimane nell'intervallo [0, n − 1].

Esempio. Per a = 17, b = 3, n = 5:

$17 \equiv 2 \pmod{5}$

$17^2 \equiv 4 \pmod{5}$

$17^3 = 17^2 \times 17 \equiv 4 \times 2 = 8 \equiv 3 \pmod{5}$

Quindi 17^3 mod 5 = 3. Verifica diretta: 17^3 = 4913 = 982 × 5 + 3.

Inverso modulare

L'inverso modulare di a modulo n è un intero x tale che:

$a \times x \equiv 1 \pmod{n}$

L'inverso esiste se e solo se MCD(a, n) = 1, ossia a ed n sono coprimi. Quando n è primo, ogni intero da 1 a n − 1 ha un inverso. Quando n è composto, i valori che condividono un fattore con n non ammettono inverso.

L'algoritmo di Euclide esteso calcola l'inverso quando questo esiste. Estende il calcolo del MCD standard tenendo traccia delle combinazioni lineari, ricavando interi s e t tali che:

$a \times s + n \times t = \gcd(a, n)$

Quando MCD(a, n) = 1, il valore s è l'inverso modulare di a mod n.

Esempio. Per a = 3, n = 5:

Si applica l'algoritmo di Euclide esteso:

• 5 = 1 × 3 + 2
• 3 = 1 × 2 + 1

Sostituendo a ritroso: 1 = 3 − 1 × 2 = 3 − 1 × (5 − 1 × 3) = 2 × 3 − 1 × 5

Quindi 3 × 2 ≡ 1 (mod 5), ossia 3⁻¹ ≡ 2 (mod 5).

Verifica: 3 × 2 = 6 = 1 × 5 + 1.

Identità euclidea e quoziente intero

Per ogni coppia (a, n) con n ≥ 1, il quoziente intero q = ⌊a / n⌋ e il resto r = a mod n soddisfano l'identità euclidea:

$a = q \times n + r, \quad 0 \leq r < n$

Questo calcolatore mostra sia r sia q, in modo da poter verificare l'identità direttamente per qualsiasi coppia di valori.

Applicazioni

L'aritmetica modulare è presente in molti ambiti della matematica e dell'informatica:

• Crittografia a chiave pubblica. RSA cifra un messaggio elevandolo a un grande esponente modulo il prodotto di due numeri primi. La decifratura utilizza l'inverso modulare dell'esponente di cifratura.
• Codici di controllo. ISBN-13, IBAN e l'algoritmo di Luhn per le carte di credito si basano sull'aritmetica modulare per rilevare errori di trascrizione.
• Calcoli calendariali. Il giorno della settimana dopo d giorni si ottiene tramite una congruenza modulo 7; la data della Pasqua segue cicli riducibili a congruenze.
• Tabelle hash. Una chiave viene mappata a un indice di secchio tramite chiave mod dimensione_tabella.
• Strutture dati cicliche. I buffer ad anello e gli array circolari avanzano il puntatore di lettura/scrittura tramite indice mod capacità.