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 venne formalmente introdotta 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 Bibliografia

[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 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] 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).

Algebra