Le congruenze nell'aritmetica modulare

La congruenza è una relazione di equivalenza tra numeri interi Z con i multipli di un numero intero positivo n.

$$ a \: p_n \: b \Leftrightarrow a \equiv b \mod n \Leftrightarrow a-b=n \cdot h $$

Dove h è un numero intero qualsiasi.

Dati due interi a,b con b>0 si dicono congrui modulo m se la loro differenza è divisibile per un intero m>0. $$ a \equiv b \mod m $$

In alternativa

Dati due numeri interi a e b>0 si dicono congrui modulo m>0 se hanno lo stesso resto nella divisione intera per m. $$ a \equiv b \mod m $$

Un esempio pratico

Metodo 1

Ecco un esempio di congruenza

$$ 26 \equiv 16 \mod 5 $$

Perché

$$ 26-16 = 10 $$

E il numero 10 è divisibile per 5.

Questo vuol dire che i due numeri divisi per 10 hanno lo stesso resto.

$$ \frac{26}{10} = 2 \mod 6 $$

$$ \frac{16}{10} = 1 \mod 6 $$

Metodo 2

Lo stesso esempio di congruenza dimostrato con il secondo metodo

$$ 26 \equiv 16 \mod 5 $$

Perché

$$ \frac{26}{5} = 5 \mod 1 $$

$$ \frac{16}{5} = 3 \mod 1 $$

La divisione per 5 restituisce lo stesso resto 1 con entrambi i numeri (16 e 26).

Pertanto, i numeri 16 e 26 sono congrui modulo 5.

A cosa servono le congruenze

Sono utili per stabilire una relazione tra l'insieme infinito dei numeri interi e un insieme finito detto insieme quoziente modulo m.

Nota. Molte discipline scientifiche ( matematica, informatica, ecc. ) usano l'insieme dei numeri interi Z. Tuttavia, non è facile lavorare con un insieme infinito. Le congruenze mi permettono di trasformarlo in un insieme finito. In questo modo tutto diventa più semplice.

Esempio

L'insieme A è composto dall'insieme dei numeri interi positivi Z+ ed è un insieme infinito.

L'insieme B è invece un insieme finito composto dai numeri 1, 2, 3

La relazione di equivalenza p mette in relazione ogni elemento di A con un elemento di B.

Il numero 4 di A è in relazione di congruenza modulo 3 con il numero 1 di B perché divisi per m=3 hanno lo stesso resto.

$$ \frac{4}{3}=1 \mod 1 $$

$$ \frac{1}{3}=0 \mod 1 $$

La stessa relazione vale per il numero 7 di A

$$ \frac{7}{3}=2 \mod 1 $$

$$ \frac{1}{3}=0 \mod 1 $$

e per il numero 10 di A

$$ \frac{10}{3}=3 \mod 1 $$

$$ \frac{1}{3}=0 \mod 1 $$

E via dicendo per tutti gli elementi (1+3n) dell'insieme A.

In conclusione, ogni numero intero dell'insieme A ha una relazione di equivalenza con un intero positivo dell'insieme B detto classe di equivalenza.

L'insieme quoziente modulo n

Nell'esempio precedente ho costruito una relazione di congruenza modulo 3.

Le classi di equivalenza della relazione sono :

$$ \bar{0} = \{ 3, 6, 9, 12, ... \} \\ \bar{1} = \{ 1, 4, 7, 10, ... \} \\ \bar{2} = \{ 2, 5, 8, 11, ... \} $$

L'insieme delle classi di equivalenza è detto insieme quoziente modulo n.

$$ Z_n = \{ \bar{0} , \bar{1} , \bar{2} \} $$

L'insieme quoziente modulo n è composto da n elementi a partire dallo zero.

Quindi, le classi variano da 0 a n-1.

Le operazioni sulle congruenze

Per trasformare un insieme quoziente modulo n in un anello, devo aggiungere due operazioni. $$ ( Z_n,+, \cdot ) $$

Le principali operazioni sulle congruenze sono

• Somma $$ \bar{a} + \bar{b} = \overline{a+b} $$
• Prodotto $$ \bar{a} \cdot \bar{b} = \overline{ab} $$

Esempio

La tavola dell'addizione e della moltiplicazione dell'anello (Z₆ ,+ ,·) è

La relazione di congruenza è compatibile con entrambe le operazioni ( somma, moltiplicazione ) definite sull'insieme dei numeri interi.

In pratica, la relazione è indipendente dalla scelta dei numeri interi.

Se la relazione di congruenza è definita per

$$ a≡b \:\:(mod \: n) $$

$$ c≡d \:\:(mod \: n) $$

allora è definita anche per

$$ a+c≡b+d \:\:(mod \: n) $$

$$ ac≡bd \:\:(mod \: n) $$

Dimostrazione. Se a≡b (mod n) allora a-b=kn. Se c≡d (mod n) allora c-d=jn. Quindi, vale la somma $$ (a-b)+(c-d)=(kn+jn) $$ $$ (a+c)-(b+d)=n(k+j) $$ Pertanto, anche (a+c)≡(b+d) (mod n) sono congruenti modulo n.

Esempio

Ho due relazioni di congruenza

$$ 7 ≡ 1 \:\: (mod \: 6) \\ 8 ≡ 2 \:\: (mod \: 6) \\ $$

per la somma vale

$$ 7+8 ≡ 1+2 \:\: (mod \: 6) $$

$$ 15 ≡ 3 \:\: (mod \: 6) $$

Verifica. La divisione 15/6 ha resto 3. La divisione 3/6 ha resto 3. Pertanto, 15 e 3 sono congruenti modulo 6.

e per la moltiplicazione

$$ 7*8 ≡ 1*2 \:\: (mod \: 6) $$

$$ 56 ≡ 2 \:\: (mod \: 6) $$

Verifica. La divisione 56/6 ha resto 2. La divisione 2/6 ha resto 2. Pertanto, 56 e 2 sono congruenti modulo 6.

La divisibilità e la congruenza

Un numero a è divisibile per m soltanto se $$ a \equiv 0 \mod m $$

Esempio

Il numero 26 è divisibile per 13?

Secondo la proprietà delle congruenze

$$ 26 \equiv 0 \mod 13 $$

$$ 26 - 0 = 26 $$

e 26 è divisibile per 13.

Altre proprietà delle congruenze

Le congruenze rispettano le seguenti proprietà

• Le congruenze che hanno lo stesso modulo possono essere sommate, sottratte, moltiplicate tra loro ordinatamente i primi membri per i secondi membri. $$ a \equiv b \mod m + c \equiv d \mod m \Rightarrow a+c \equiv b+d \mod m $$ $$ a \equiv b \mod m - c \equiv d \mod m \Rightarrow a-c \equiv b-d \mod m $$ $$ a \equiv b \mod m \cdot c \equiv d \mod m \Rightarrow ac \equiv bd \mod m $$
• Una congruenza può essere moltiplicata per un numero intero k qualsiasi. $$ k \cdot ( a \equiv b \mod m ) \Rightarrow ka \equiv kb \mod b $$
• Due congruenze uguali equivalgono a una potenza. $$ ( a \equiv b \mod m ) \cdot ( a \equiv b \mod m ) \Rightarrow a^2 \equiv b^2 \mod b $$
• Data una congruenza a≡b e un numero intero c qualsiasi valgono le seguenti $$ a+c ≡ b + c \\ ac ≡ bc \\ a^c ≡ b^c $$
• Data una congruenza a≡b mod n e l'intero d è un divisore di n allora a≡b mod d. $$ a≡ b \mod n \:\:, \:\: d|n \Rightarrow a ≡ b \mod d $$

  Esempio. I numeri 15 e 21 sono congruenti modulo 6 $$ 15≡ 21 \mod 6 $$ prendo un divisore 2|6 e verifico se sono congruenti. Sia 15/2 che 21/2 hanno resto 1. Quindi sono anche congruenti modulo 2. $$ 15≡ 21 \mod 2 $$ Lo stesso vale per il divisore 3|6 perché 15/3 e 21/3 hanno entrambi resto 0. Pertanto sono anche congruenti modulo 3. $$ 15≡ 21 \mod 3 $$

• Date due congruenze vale la seguente $$ a≡ b \mod r \:\:, \:\: a≡ b \mod s \Rightarrow a ≡ b \mod \: mcm(r,s) $$
• Date due congruenze vale la seguente $$ ac≡ bc \mod n \Rightarrow a ≡ b \mod \: n/MCD(c,n) $$
• Date due congruenze vale la seguente $$ ac≡ bc \mod n \:\: MCD(c,n)=1 \Rightarrow a ≡ b \mod \: n $$
• Ogni intero a è congruente modulo n a un intero r tale che 0≤r<n $$ a \equiv r \mod n $$

  Dimostrazione. Il resto (r) della divisione a/n non può essere uguale o superiore al divisore n. Se lo fosse, sarebbe ancora divisibile per n e non sarebbe un resto della divisione.

• Dati due interi a,b e un numero primo p, allora vale la congruenza $$ (a+b)^p ≡ a^p+ b^p \mod p $$

E così via.