Aritmetica modulare

Da Wikipedia, l'enciclopedia libera.

L'aritmetica modulare (a volte detta aritmetica dell'orologio poiché su tale principio si basa il calcolo delle ore a cicli di 12 o 24) rappresenta un importante ramo della matematica. Essa 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, nel quale i numeri "si avvolgono su se stessi" ogni volta che raggiungono i multipli di un determinato numero n, detto modulo. L'aritmetica modulare e la notazione usuale delle congruenze vennero formalmente introdotte da Carl Friedrich Gauss nel suo trattato Disquisitiones Arithmeticae, pubblicato nel 1801.

Indice

1 La relazione di congruenza
- 1.1 Proprietà delle congruenze
  - 1.1.1 Relazione di equivalenza
  - 1.1.2 Invarianza rispetto alle operazioni aritmetiche
2 Le classi di resto modulo n
- 2.1 L'aritmetica delle congruenze modulo n
3 Polinomi in aritmetica modulare
- 3.1 Irriducibilità
4 Equazioni diofantee
5 Bibliografia
6 Voci correlate

[modifica] La relazione di congruenza

L'aritmetica modulare si basa sul concetto di congruenza modulo n . Dati tre numeri interi a, b, n, con n ≠ 0, diciamo che a e b sono congruenti modulo n se la loro differenza (a − b) è un multiplo di n. In questo caso scriviamo

$a \equiv b \pmod{n} \,$

e diciamo che a è congruo a b modulo n. Per esempio, possiamo scrivere

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

poiché 38 − 14 = 24, che è un multiplo di 12.

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

[modifica] Proprietà delle congruenze

[modifica] Relazione di equivalenza

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

Proprietà riflessiva: ogni numero è congruo a sé stesso modulo n, per ogni n diverso da 0 fissato.

$a \equiv a \pmod{n} \qquad \forall a \in \mathbb{N},\forall n \in \mathbb{N}_0$

Dimostrazione: si ha a - a = 0. Ma come è noto, ogni intero non nullo è divisore di 0. Quindi n divide (a - a)

Proprietà simmetrica: se a è congruo a b modulo n allora b è congruo ad a modulo n

$a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n} \qquad \forall a,b \in \mathbb{N},\forall n \in \mathbb{N}_0$

Dimostrazione: se n divide (a - b) , allora n divide anche l'opposto (b - a) = - (a - b)

Proprietà transitiva: se a è congruo a b modulo n e b è congruo a c modulo n allora anche a è congruo a c modulo n.

$a \equiv b \pmod{n} \quad\land\quad b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n} \qquad \forall a,b,c \in \mathbb{N},\forall n \in \mathbb{N}_0$

Dimostrazione: se n divide (a - b) e n divide (a - c) allora, per la proprietà distributiva della divisione rispetto alla sottrazione, n divide anche [(a - c) - (a - b)]=[a - c - a + b] = (b - c).

[modifica] Invarianza rispetto alle operazioni aritmetiche

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 n, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo n. Più sinteticamente

$a \equiv b \pmod{n} \Leftrightarrow (a + c ) \equiv (b + c) \pmod{n} \qquad \forall a,b,c \in \mathbb{N},\forall n \in \mathbb{N}_0$

Dimostrazione: scriviamo (a - b) = (a - b + c - c) = (a + c) - (b + c)

Invarianza per moltiplicazione: moltiplicando per una stessa quantità due numeri congruenti modulo n, i nuovi numeri ottenuti sono ancora congruenti tra loro modulo n.

$a \equiv b \pmod{n} \Rightarrow a\cdot c \equiv b \cdot c \pmod{n} \qquad \forall a,b,c \in \mathbb{N},\forall n \in \mathbb{N}_0$

Dimostrazione: se n divide (a - b) allora n divide (a - b)×c

Nota: Questa proprietà si può invertire solo se n non divide c, cioè se c non è congruo a 0 (mod n).

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

$a \equiv b \pmod{n} \Rightarrow a^{k} \equiv b^{k} \pmod{n} \qquad \forall a,b,c \in \mathbb{N},\forall k \in \mathbb{N},\forall n \in \mathbb{N}_0$

Dimostrazione: se a ≡ b ≡ 0 (mod n) la proposizione è banale. Se a ≡ b (mod n) non sono nulli, supponiamo di sapere che $a^{k-1}\equiv b^{k-1} \pmod{n}$ . Moltiplicando entrambi i termini per a grazie all'invarianza per moltiplicazione, avremo $a^{k}\equiv b^{k-1}\cdot a \pmod{n}$ . Partiamo ora dalla congruenza a ≡ b (mod n) e moltiplichiamo entrambi i membri per

b k - 1 (mod n)

, sempre grazie all'invazianza per moltiplicazione. Otteniamo: $a\cdot b^{k-1}\equiv b^{k} \pmod{n}$ . Confrontando le due espressioni, ed utilizzando le proprietà simmetrica e transitiva, si deduce che $a^{k}\equiv b^{k} \pmod{n}$ . Poiché la proposizione è vera per k = 1 e il fatto che sia vera per k-1 implica che essa è vera per k, per il principio di induzione la proposizione è vera per ogni k.

Nota: Questa proprietà si può invertire solo se k è diverso da 0.

[modifica] Le classi di resto modulo n

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

La divisione con resto di un intero a per n

a= k×n + r

indica che ogni elemento a è equivalente ad un intero r tra 0 e n-1: il resto della divisione di a per n. Ne segue che l'insieme quoziente è formato dagli n elementi

[0],[1],...,[n - 2],[n - 1].

L'insieme quoziente è chiamato insieme delle classi di resto modulo n.

Ciascuna classe di resto [r] rappresenta, oltre a r stesso, tutti i numeri interi della forma a= k×n + r per qualche intero 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.

[modifica] L'aritmetica delle congruenze modulo n

Le invarianze descritte sopra rispetto a somma e moltiplicazione indicano che tali 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 [0] e [1].

Le classi modulo 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:

[2] * [3] = [6] = [0]

n = 6

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

Tra le proprietà delle operazioni troviamo le seguenti:

$[a] + [b] = [a + b]$
$[a b] = [a][b]$

[modifica] Polinomi in aritmetica modulare

Per approfondire, vedi la voce Congruenze polinomiali.

Anche in $\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 $\mathbb{Q}$ o $\mathbb{R}$ , oppure su anelli come $\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 $\mathbb{Z}_n$ : quando n è primo e quando n è composto. In quest'ultimo caso, non essendo $\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 $x^2-1\equiv 0\mod 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.

[modifica] Irriducibilità

Gli anelli $\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 polinomi è riducibile nell'anello $\mathbb{Z}[X]$ dei polinomi a coefficienti interi come f(x)=g(x)h(x), allora lo stesso vale modulo un qualsiasi primo p:

$[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 $\mathbb{Z}_p[X]$ , con p primo che non divide il coefficiente del termine di grado massimo, allora non si fattorizza (ovvero è irriducibile) nell'anello $\mathbb{Z}[X]$ .

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

$x^2+1\equiv (x+2)(x+3)\mod 5$

[modifica] Equazioni diofantee

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

x 3 + 7 y 3 = 2

non può avere soluzioni intere, perché se esistesse una soluzione $(x 0, y 0)$ tale soluzione sarebbe tale anche nell'anello delle congruenze modulo 7; cioè dovrebbe essere risolubile la congruenza

$x^3+7y^3\equiv 2\mod 7$

$x^3\equiv 2\mod 7$

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

[modifica] Bibliografia

H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 8808091546 - Capitolo II
Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9 (Chapter 5).