Congruenze modulo n

Questa appendice è fuori programma di Quinta scientifico, ma mostra come l’aritmetica elementare (mcd, divisori, congruenze) sia diventata — a partire dagli anni ‘70 — la base della sicurezza digitale moderna. È un esempio splendido di matematica “pura” che si rivela imprevedibilmente applicata. Il punto di partenza è la relazione di congruenza.

Definizione — Congruenza modulo $n$

Dati $a,b\in\mathbb{Z}$ e $n\in\mathbb{N}$ con $n\ge 2$, si dice che $a$ è congruo a $b$ modulo $n$, e si scrive $a \equiv b \pmod n,$ se $n$ divide $a-b$. Equivalentemente: $a$ e $b$ danno lo stesso resto nella divisione per $n$.

Esempi: $17\equiv 2\pmod 5$ (poiché $17-2=15$ è divisibile per $5$); $-3\equiv 4\pmod 7$. L’aritmetica modulare è quella dell’orologio: $14$ ore $+ 13$ ore $= 27\equiv 3\pmod{24}$ (le $3$ di mattina del giorno dopo).

Collegamenti

Argomenti: Distribuzioni probabilita
Concetti: Aritmetica modulare · Congruenza
Competenze: Usare formule