Aritmetica modulare

L'aritmetica modulare (a volte detta aritmetica dell'orologio poiché su questo principio si basa il calcolo delle ore a cicli di 12 o 24) rappresenta un importante ramo della matematica. Trova applicazioni nella crittografia, nella teoria dei numeri (in particolare nella ricerca dei numeri primi) ed è alla base di molte delle più comuni operazioni aritmetiche e algebriche.

Si tratta di un sistema di aritmetica degli interi, in cui i numeri "si avvolgono su loro stessi" ogni volta che raggiungono i multipli di un determinato numero ${\displaystyle n}$, detto modulo. Per capire, si pensi al funzionamento di un orologio in formato da 12 ore: trascorse quest'ultime "si ricomincia" dal numero 1 a contare le ore. Dire "sono le 3 del pomeriggio" (formato 12 ore) equivale a dire "sono le 15" (formato 24 ore). Tradotto in termini matematici, significa che ${\displaystyle 15\equiv 3{\pmod {12}}}$. Si legge, ${\displaystyle 15}$ è congruente a ${\displaystyle 3}$, modulo ${\displaystyle 12}$.

L'aritmetica modulare e la notazione usuale delle congruenze vennero formalmente introdotte da Carl Friedrich Gauss nel suo trattato Disquisitiones Arithmeticae, pubblicato nel 1801.

L'aritmetica modulare si basa sul concetto di congruenza modulo ${\displaystyle n}$.

Dati tre numeri interi ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle n}$ con ${\displaystyle n\neq 0}$, diciamo che ${\displaystyle a}$ e ${\displaystyle b}$ sono congruenti modulo ${\displaystyle n}$, oppure che ${\displaystyle a}$ è congruo a ${\displaystyle b}$ modulo ${\displaystyle n}$, se la differenza ${\displaystyle a-b}$ è un multiplo di ${\displaystyle n}$. In questo caso scriviamo

${\displaystyle a\equiv b{\pmod {n}}.}$

In simboli la definizione di congruenza modulo ${\displaystyle n}$ si può esprimere

${\displaystyle a\equiv b{\pmod {n}}\iff \exists \ k\in \mathbb {Z} |\ a-b=k\cdot n}$

Per esempio, possiamo scrivere

${\displaystyle 38\equiv 14{\pmod {12}}}$

poiché ${\displaystyle 38-14=24}$, che è un multiplo di ${\displaystyle 12}$.

Nel caso entrambi i numeri siano positivi, si può anche dire che ${\displaystyle a}$ e ${\displaystyle b}$ sono congruenti modulo ${\displaystyle n}$ se hanno lo stesso resto nella divisione per ${\displaystyle n}$. Quindi possiamo anche dire che ${\displaystyle 38}$ è congruo a ${\displaystyle 14}$ modulo ${\displaystyle 12}$ poiché sia ${\displaystyle 38}$ sia ${\displaystyle 14}$ hanno resto ${\displaystyle 2}$ nella divisione per ${\displaystyle 12}$.

La congruenza è una relazione di equivalenza tra numeri interi, come si evince dalle seguenti proprietà:

• Proprietà riflessiva: ogni numero è congruo a sé stesso modulo ${\displaystyle n}$, per ogni ${\displaystyle n}$ diverso da ${\displaystyle 0}$:

${\displaystyle a\equiv a{\pmod {n}},\qquad \forall a\in \mathbb {N} ,\ \forall n\in \mathbb {N} _{0}.}$

Dimostrazione: si ha ${\displaystyle a-a=0}$ e, come è noto, ogni intero non nullo è divisore di ${\displaystyle 0}$. Quindi ${\displaystyle n}$ divide ${\displaystyle a-a}$.

• Proprietà simmetrica: se ${\displaystyle a}$ è congruo a ${\displaystyle b}$ modulo ${\displaystyle n}$ allora ${\displaystyle b}$ è congruo ad ${\displaystyle a}$ modulo ${\displaystyle n}$:

${\displaystyle a\equiv b{\pmod {n}}\implies b\equiv a{\pmod {n}},\qquad \forall a,b\in \mathbb {N} ,\forall n\in \mathbb {N} _{0}.}$

Dimostrazione: se ${\displaystyle n}$ divide ${\displaystyle a-b}$ , allora ${\displaystyle n}$ divide anche l'opposto ${\displaystyle b-a=-(a-b)}$.

• Proprietà transitiva: se ${\displaystyle a}$ è congruo a ${\displaystyle b}$ modulo ${\displaystyle n}$ e ${\displaystyle b}$ è congruo a ${\displaystyle c}$ modulo ${\displaystyle n}$, allora anche ${\displaystyle a}$ è congruo a ${\displaystyle c}$ modulo ${\displaystyle n}$:

${\displaystyle a\equiv b{\pmod {n}}\quad \land \quad b\equiv c{\pmod {n}}\implies a\equiv c{\pmod {n}},\qquad \forall a,b,c\in \mathbb {N} ,\forall n\in \mathbb {N} _{0}.}$

Dimostrazione: se ${\displaystyle n}$ divide ${\displaystyle a-b}$ e ${\displaystyle n}$ divide ${\displaystyle b-c}$, allora, per la proprietà distributiva della divisione rispetto alla somma, ${\displaystyle n}$ divide anche ${\displaystyle (a-b)+(b-c)=a-b+b-c=a-c}$.

Un'altra importante caratteristica della relazione di congruenza è il fatto di essere preservata dalle usuali operazioni aritmetiche tra interi:

• Invarianza per addizione: aumentando o diminuendo della stessa quantità due numeri congruenti modulo ${\displaystyle n}$, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo ${\displaystyle n}$. Più sinteticamente

${\displaystyle a\equiv b{\pmod {n}}\Leftrightarrow (a+c)\equiv (b+c){\pmod {n}},\qquad \forall a,b,c\in \mathbb {Z} ,\forall n\in \mathbb {N} _{0}.}$

Dimostrazione: ${\displaystyle a-b=a-b+c-c=(a+c)-(b+c).}$

• Invarianza per moltiplicazione: moltiplicando per una stessa quantità due numeri congruenti modulo ${\displaystyle n}$, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo ${\displaystyle n}$.

${\displaystyle a\equiv b{\pmod {n}}\Rightarrow a\cdot c\equiv b\cdot c{\pmod {n}},\qquad \forall a,b,c\in \mathbb {Z} ,\forall n\in \mathbb {N} _{0}.}$

Dimostrazione: se ${\displaystyle n}$ divide ${\displaystyle a-b,}$ allora ${\displaystyle n}$ divide ${\displaystyle (a-b)\times c.}$

Nota: Si può invertire questa proprietà solo se ${\displaystyle \mathrm {MCD} (n,c)=1.}$

• Invarianza rispetto all'elevamento a potenza: elevando due numeri congrui modulo ${\displaystyle n}$ alla stessa potenza ${\displaystyle k}$, i numeri ottenuti sono ancora congrui tra loro modulo ${\displaystyle n}$.

${\displaystyle a\equiv b{\pmod {n}}\Rightarrow a^{k}\equiv b^{k}{\pmod {n}},\qquad \forall a,b\in \mathbb {Z} ,\forall k\in \mathbb {N} ,\forall n\in \mathbb {N} _{0}.}$

Dimostrazione: se ${\displaystyle a\equiv b\equiv 0{\pmod {n}},}$ la proposizione è banale. Se ${\displaystyle a\equiv b{\pmod {n}},}$ non è nullo, si supponga che ${\displaystyle a^{k-1}\equiv b^{k-1}{\pmod {n}}}$. Moltiplicando entrambi i termini per ${\displaystyle a}$ grazie all'invarianza per moltiplicazione, avremo ${\displaystyle a^{k}\equiv b^{k-1}\cdot a{\pmod {n}}}$. Partendo dalla congruenza ${\displaystyle a\equiv b{\pmod {n}}}$ e moltiplicando entrambi i membri per ${\displaystyle b^{k-1}{\pmod {n}}}$, sempre grazie all'invarianza per moltiplicazione, si ottiene: ${\displaystyle a\cdot b^{k-1}\equiv b^{k}{\pmod {n}}}$. Confrontando le due espressioni e utilizzando le proprietà simmetrica e transitiva si deduce che ${\displaystyle a^{k}\equiv b^{k}{\pmod {n}}}$. Poiché la proposizione è vera per ${\displaystyle k=1}$ e l'essere vera per ${\displaystyle k-1}$ implica che essa sia vera per ${\displaystyle k}$, per il principio di induzione la proposizione è vera per ogni ${\displaystyle k}$.

Le proprietà riflessiva, simmetrica e transitiva descritte sopra indicano che la relazione di congruenza modulo ${\displaystyle n}$ è una relazione di equivalenza e definisce quindi un insieme quoziente.

La divisione euclidea di un intero ${\displaystyle a}$ per ${\displaystyle n}$, con ${\displaystyle n\neq 0,}$ per cui

${\displaystyle a=k\times n+r}$

ovvero

${\displaystyle a-r=k\times n}$

consente di suddividere l'insieme ${\displaystyle \mathbb {Z} }$ degli interi in ${\displaystyle n}$ classi (sottoinsiemi) secondo la seguente relazione di equivalenza: si dice che un intero ${\displaystyle a}$ è equivalente a ${\displaystyle r{\pmod {n}}}$ se e solo se la differenza ${\displaystyle a-r}$ è un multiplo relativo di ${\displaystyle n}$. Si definisce così l'insieme quoziente di ${\displaystyle \mathbb {Z} }$ rispetto a tale relazione di equivalenza e formato dalle ${\displaystyle n}$ classi

${\displaystyle [0],[1],\ldots ,[n-2],[n-1]}$

chiamate classi di resto modulo ${\displaystyle n}$.

Ciascuna classe di resto ${\displaystyle [r]}$ rappresenta, oltre a ${\displaystyle r}$ stesso, tutti i numeri interi della forma ${\displaystyle a=k\times n+r}$ per qualche intero ${\displaystyle k}$.

Ad esempio, nella congruenza modulo 7, la classe di resto [5] rappresenta, oltre al numero 5, anche il numero 12 (=1×7 + 5), il numero 19 (=2×7 + 5), il numero 2308 (=329×7 + 5) ecc. Inoltre [5] rappresenta anche il numero -2 (= -1×7 + 5), il numero -9 (= -2×7 + 5) e così via.

Le invarianze descritte sopra rispetto a somma e moltiplicazione indicano che queste operazioni sono ben definite anche al quoziente. Queste operazioni continuano a soddisfare le proprietà commutativa, associativa e distributiva. Gli elementi neutri per l'addizione e la moltiplicazione sono le classi ${\displaystyle [0]}$ e ${\displaystyle [1].}$

Le classi modulo ${\displaystyle n}$ con la somma formano un gruppo abeliano: più precisamente, formano un gruppo ciclico finito. Con somma e prodotto formano un anello. Diversamente da quanto accade per i numeri interi, il prodotto di due elementi non nulli può essere nullo. Ad esempio:

${\displaystyle [2]\cdot [3]=[6]=[0]}$ se ${\displaystyle n=6.}$

Questo non succede però quando ${\displaystyle n}$ è un numero primo: infatti in questo caso le classi formano un dominio d'integrità e anche un campo.

Tra le proprietà delle operazioni troviamo le seguenti:

• ${\displaystyle [a]+[b]=[a+b];}$
• ${\displaystyle [ab]=[a][b].}$

A causa dell'eventuale presenza dei divisori dello 0, generalmente ${\displaystyle \mathbb {Z} _{n}-\{0\}}$ non è un gruppo con il prodotto. Infatti i divisori dello 0 non hanno inversi. Invece quando non esistono divisori dello 0 non nulli, cioè nei casi con ${\displaystyle n}$ primo, la moltiplicazione forma un gruppo moltiplicativo e l'anello ${\displaystyle \mathbb {Z} _{n}}$ è un campo. Tuttavia se ci si restringe alle classi i cui rappresentati sono coprimi con ${\displaystyle n}$, questa proprietà riappare. È facile dimostrarlo facendo ricorso all'identità di Bézout: se ${\displaystyle a}$ è coprimo con ${\displaystyle n}$, esistono due interi ${\displaystyle x}$ e ${\displaystyle y}$ tali che

${\displaystyle ax+ny=1}$

ossia, riducendo modulo ${\displaystyle n}$,

${\displaystyle ax\equiv 1\mod n}$

e quindi ogni ${\displaystyle a}$ ha un inverso. Inoltre la moltiplicazione continua a essere interna all'anello e a possedere le proprietà associativa e commutativa, e la classe ${\displaystyle [1]}$ è l'elemento neutro.

Un risultato importante, trovato già da Gauss, è che questo gruppo è ciclico se e solo se ${\displaystyle n}$ è 2, 4, la potenza di un numero primo dispari oppure il doppio della potenza di un numero primo dispari. I generatori di questo gruppo ciclico sono a volte detti radici primitive modulo ${\displaystyle n}$.

Anche in ${\displaystyle \mathbb {Z} _{n}}$ è possibile, attraverso le operazioni definite prima, parlare di polinomi. Le proprietà di questi differiscono in molti casi dalle proprietà "abituali" osservate quando si considerano polinomi su campi come ${\displaystyle \mathbb {Q} }$ o ${\displaystyle \mathbb {R} }$, oppure su anelli come ${\displaystyle \mathbb {Z} }$. Ad esempio, il principio di identità dei polinomi (due polinomi assumono valori uguali se e solo se i loro coefficienti sono ad uno ad uno uguali) non vale, sebbene valga una sua versione modificata.

Anche nello studio di questo soggetto, così come nella maggior parte dell'aritmetica modulare, si distinguono due tipi molto diversi di comportamento di ${\displaystyle \mathbb {Z} _{n}}$: quando ${\displaystyle n}$ è primo e quando ${\displaystyle n}$ è composto. In quest'ultimo caso, non essendo ${\displaystyle \mathbb {Z} _{n}}$ né un campo né un dominio d'integrità, il comportamento dei polinomi può essere molto "strano": ad esempio, la congruenza polinomiale di 2º grado ${\displaystyle x^{2}-1\equiv 0{\bmod {8}}}$ ha quattro soluzioni (1, 3, 5 e 7) quando in campi infiniti come i razionali, i reali o i complessi il numero delle soluzioni non può superare il grado del polinomio.

Gli anelli ${\displaystyle \mathbb {Z} _{p}}$ forniscono anche un modo per studiare l'irriducibilità dei polinomi a coefficienti interi e quindi, per il lemma di Gauss, anche di quelli a coefficienti razionali. Infatti se un polinomio è riducibile nell'anello ${\displaystyle \mathbb {Z} [x]}$ dei polinomi a coefficienti interi come ${\displaystyle f(x)=g(x)h(x),}$ allora lo stesso vale modulo un qualsiasi primo ${\displaystyle p}$:

${\displaystyle [f(x)]_{p}\equiv [g(x)]_{p}[h(x)]_{p}\mod p.}$

Questa proprietà può essere sfruttata per costruire un criterio di irriducibilità: se un polinomio non si fattorizza in ${\displaystyle \mathbb {Z} _{p}[x]}$, con ${\displaystyle p}$ primo che non divide il coefficiente del termine di grado massimo, allora non si fattorizza, ossia è irriducibile, nell'anello ${\displaystyle \mathbb {Z} [x]}$.

Il viceversa non è vero: ${\displaystyle f(x)=x^{2}+1}$ è irriducibile in ${\displaystyle \mathbb {Z} [x]}$, ma in ${\displaystyle \mathbb {Z} _{5}[x]}$ si fattorizza come

${\displaystyle x^{2}+1\equiv (x+2)(x+3)\mod 5.}$

Allo stesso modo dello studio dell'irriducibilità dei polinomi, nello studio delle equazioni diofantee si studia a volte la stessa equazione modulo un intero ${\displaystyle n}$ per fornire condizioni necessarie alla risolubilità dell'equazione stessa. Ad esempio l'equazione

${\displaystyle x^{3}+7y^{3}=2}$

non può avere soluzioni intere, perché se esistesse una soluzione ${\displaystyle (x_{0},y_{0})}$ questa sarebbe tale anche nell'anello delle congruenze modulo 7; cioè dovrebbe essere risolubile la congruenza

${\displaystyle x^{3}+7y^{3}\equiv 2\mod 7}$

${\displaystyle x^{3}\equiv 2\mod 7}$

che non ha soluzioni, perché i possibili valori che assume ${\displaystyle x^{3}\mod 7}$ sono 0, 1 e 6.

L'insieme di tutte le classi di congruenza di modulo ${\displaystyle m}$ è chiamato anello degli interi di modulo ${\displaystyle m}$ e può essere indicato con le notazioni ${\textstyle \mathbb {Z} /m\mathbb {Z} }$, ${\displaystyle \mathbb {Z} /m}$ oppure ${\displaystyle \mathbb {Z} _{m}}$.^[1] Tuttavia, la notazione ${\displaystyle \mathbb {Z} _{m}}$ è solitamente sconsigiata perché può essere confusa con quella che indica un numero p-adico e appartenente al sistema numerico corrispondente.

• Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New York, 1976. ISBN 0-387-90163-9, capitolo 5.
• H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 88-08-09154-6, capitolo II.
• (EN) T. Sengadir, Discrete Mathematics and Combinatorics, Chennai, India, Pearson Education India, 2009, ISBN 978-81-317-1405-8.

• Divisione euclidea
• Piccolo teorema di Fermat
• Operazione modulo
• Prova del nove

• Wikibooks contiene testi o manuali di aritmetica modulare
• Wikimedia Commons contiene immagini o altri file sull'aritmetica modulare

• aritmetica modulare, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) John L. Berggren, modular arithmetic, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Aritmetica modulare, su MathWorld, Wolfram Research.
• (EN) Denis Howe, modular arithmetic, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri