Aritmetica modulare — aritmetica dell’orologio, mod e congruenza

L’aritmetica modulare consiste nel lavorare con i resti della divisione per un intero positivo fissato, chiamato modulo. Se due numeri lasciano lo stesso resto, si comportano allo stesso modo in quel sistema modulare, ed è per questo che spesso si parla di aritmetica dell’orologio.

Su un orologio da $12$ ore, le $13$ corrispondono all’$1$, e $29$ ore portano nello stesso punto di $5$ ore. Questo ciclo che si ripete è l’idea intuitiva alla base dell’aritmetica modulare.

Cosa significa mod nell’aritmetica modulare

Per un intero $a$ e un intero positivo $n$, l’espressione $a \bmod n$ indica il resto della divisione di $a$ per $n$.

Esempio:

$$29 \bmod 12 = 5$$

perché

$$29 = 12 \cdot 2 + 5$$

Il modulo è $12$, quindi aggiungere o sottrarre $12$ non cambia la posizione nel ciclo.

Cosa significa congruenza modulo $n$

La congruenza è il modo formale per dire che due interi si comportano allo stesso modo modulo $n$.

$$a \equiv b \pmod n$$

significa che $a$ e $b$ lasciano lo stesso resto quando vengono divisi per $n$. Un criterio equivalente è

$$n \mid (a-b)$$

che significa “$n$ divide $a-b$”.

Quindi

$$29 \equiv 5 \pmod{12}$$

perché $29 - 5 = 24$, e $12$ divide $24$.

Questa distinzione è importante:

• $29 \bmod 12 = 5$ è un’affermazione sul resto.
• $29 \equiv 5 \pmod{12}$ è un’affermazione di congruenza.

Sono collegate, ma non sono intercambiabili.

Esempio svolto: $29$ ore dopo le $8$

Supponi che adesso siano le $8$ e che tu voglia sapere che ora sarà $29$ ore dopo su un orologio da $12$ ore.

Per prima cosa riduci $29$ modulo $12$:

$$29 \bmod 12 = 5$$

Quindi aggiungere $29$ ore ha lo stesso effetto che aggiungere $5$ ore:

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

Poi

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

Quindi l’orologio segna l’$1$.

Il passaggio chiave è la riduzione. Modulo $12$, sostituire $29$ con $5$ lascia invariata la risposta e rende i calcoli più semplici.

Perché ridurre prima rende i problemi più semplici

Spesso i numeri grandi sono più facili da gestire dopo essere stati sostituiti con un numero più piccolo a essi congruente.

Per esempio, modulo $7$,

$$100 \equiv 2 \pmod 7$$

perché $100 - 2 = 98$ è divisibile per $7$. Se il problema riguarda solo i valori modulo $7$, puoi lavorare con $2$ invece che con $100$.

Errori comuni

Confondere uguaglianza e congruenza

$29 \equiv 5 \pmod{12}$ non significa $29 = 5$. Significa che appartengono alla stessa classe di resto modulo $12$.

Dimenticare che il modulo conta

$17 \equiv 5 \pmod{12}$ è vero, ma $17 \equiv 5 \pmod{10}$ è falso. La congruenza è sempre legata a un modulo specifico.

Trattare mod come una divisione ordinaria

$29 \bmod 12$ è il resto $5$, non il quoziente $2$ e nemmeno la frazione $29/12$.

Supporre che % nei software segua sempre la stessa convenzione matematica

Per numeri positivi, % nei linguaggi di programmazione spesso coincide con l’idea di resto che gli studenti imparano per prima. Con i numeri negativi, però, le convenzioni possono cambiare, quindi il risultato potrebbe non coincidere con il minimo resto non negativo usato in molti corsi di matematica.

Dove si usa l’aritmetica modulare

L’aritmetica modulare compare ogni volta che i valori si ripetono in cicli: orologi, giorni della settimana, sistemi di cifre di controllo, hashing e molte parti della teoria dei numeri.

Compare anche nella crittografia, ma l’idea di base resta la stessa: i numeri vengono raggruppati in base al loro resto, e i numeri congruenti possono essere trattati come equivalenti all’interno di quel sistema.

Prova un problema simile

Che giorno della settimana sarà $100$ giorni dopo un lunedì? Poiché i giorni si ripetono modulo $7$, inizia riducendo $100$ modulo $7$ prima di rispondere.

Se vuoi un altro caso da confrontare, prova la tua versione in GPAI Solver e verifica se ridurre prima rende il lavoro più breve.