.....ppp dove p

(1)

Matematica Discreta

Lezione dei giorni 2,4,8 e 9 febbraio 2011 La funzione di Eulero.

Dati 2 numeri naturali a,b, diremo che a,b sono numeri coprimi se mcd(a,b)=1.

Poiché il massimo comune divisore di a,b è il più grande dei divisori comuni di a,b, in pratica affermare che a,b sono coprimi equivale ad affermare che l’unico divisore comune di a,b è 1.

Fissato un numero naturale n, si chiama funzione di Eulero la funzione φ: N  N che associa ad ogni numero naturale nN il numero φ(n) di tutti i numeri naturali x tali che 1xn ed x,n sono coprimi.

E’ ovvio che φ(1)=1, dunque studieremo solo il caso n>1.

Esempio: se n=15, i numeri naturali x tali che 1x15 ed x,15 sono coprimi sono 1,2,4,7,8,11,13,14 quindi φ(15)=8 .

Cercheremo una formula che permetta di calcolare φ(n) conoscendo la fattorizzazione di n in prodotto di numeri primi. Premettiamo 2 risultati preliminari:

1) Siano p

1

, p

2

,….., p

r

dei numeri primi distinti e supponiamo che ognuno di essi sia divisore del numero naturale c. Allora anche il prodotto (p

1

p

2

…..p

r

) è divisore di c.

Dimostrazione: per ipotesi esiste un naturale b tale che p

1

b=c; se fattorizziamo sia c che b in prodotto di numeri primi:

b=q

1

q

2

…..q

s

, c=t

1

t

2

…..t

m

si ha l’eguaglianza:

p

1

q

1

q

2

…..q

s

= t

1

t

2

…..t

m

e per l’unicità della fattorizzazione segue che p

1

coincide con uno dei fattori t

1

, t

2, ….,

t

m

e (riordinando opportunamente i fattori) possiamo fare in modo che p

1

=t

1

.

Analogamente, ragionando su p

2

, si ottiene che p

2

coincide con uno dei fattori t

1

, t

2, ….,

t

m

(ma non con t

1

perché p

1

p

2

) e (riordinando opportunamente i fattori) possiamo fare in modo che p

2

=t

2

. Procediamo fino ad ottenere p

r

=t

r

da cui c = t

1

t

2

…..t

m

= (p

1

p

2

…..p

r

)t

r+1

…..t

m

e si ha la tesi.

2) Siano x

1

, x

2

,…,x

r

delle variabili (che possono assumere come valori numerici arbitrari) e calcoliamo il valore dell’espressione algebrica seguente:

(1-x

1

)(1-x

2

)……(1-x

r

)

Per r=2 si ha, utilizzando la proprietà distributiva e sviluppando i calcoli : (1-x

1

)(1-x

2

)=1-(x

1

+x

2

)+x

1

x

2

Per r=3 con calcoli analoghi si ha:

(1-x

1

)(1-x

2

)(1-x

3

)=1-(x

1

+x

2

+x

3

)+(x

1

x

2

+x

1

x

3

+x

2

x

3

)-x

1

x

2

x

3

Si può in generale dimostrare (con una dimostrazione per induzione che omettiamo) che per qualunque numero r di variabili vale la seguente formula:

(1-x

1

)(1-x

2

)……(1-x

r

)=1-α

1

+α

2

-α

3

+α

4

+…….±α

r

dove α

1

è la somma delle singole variabili ; α

2

è la somma dei prodotti delle variabili prese a 2 a 2;

α

3

è la somma dei prodotti delle variabili prese a 3 a 3; …….. ……; 

r

è il prodotto delle r variabili, preceduto da un segno + se r è pari, da un segno – se r è dispari.

Torniamo ora al calcolo della funzione di Eulero φ(n), per n>1. Possiamo considerare la fattorizzazione di n in prodotto di numeri primi: raccogliendo i fattori primi uguali sotto forma di potenza, n si può rappresentare nella forma

n = p ₁ ^k

¹

p ₂ ^k

²

...p _r ^k

^r

dove p

1

, p

2

, …., p

r

sono fattori primi distinti di n.

(2)

Dato un numero naturale x, affinché x,n siano coprimi (cioè affinché 1 sia l’unico divisore comune di x,n) si deve ovviamente avere che nessuno dei primi p

1

, p

2

,…,p

r

(che sono divisori di n) sia divisore di x.

Come conseguenza di tale risultato, per calcolare φ(n) dobbiamo calcolare il numero dei numeri naturali x tali che 1xn e che non soddisfano nessuna delle seguenti r proprietà:

p

1

è divisore di x; p

2

è divisore di x; ….. ; p

r

è divisore di x.

Usando in forma negativa il principio di inclusione-esclusione, costruiamo allora l’insieme X di tutti i numeri naturali x tali che 1xn, e gli r sottoinsiemi di X:

X

i

= {xX / p

i

è divisore di x} ( al variare di i=1,2,…,r) Si avrà:

φ(n)= X-X

1

X

2

…X

r

= n -X

1

X

2

…X

r

.

Calcolando la cardinalità dell’unione con la formula del principio di incluione-esclusione si ottiene:

X

1

X

2

…X

r

=α

1

-α

2

+α

3

-α

4

+…….±α

r

dove α

1

è la somma delle cardinalità dei singoli insiemi X

i

; α

2

è la somma delle cardinalità di tutte le possibili intersezioni a 2 a 2 degli insiemi X

i

;……, α

r

è la cardinalità dell’intersezione di tutti gli insiemi X

i

, preceduta da un segno + se r è dispari, da un segno – se r è pari.

Poiché X

1

contiene tutti i multipli di p

1

compresi fra 1 ed n si ha:

X

1

= {1•p

1

,2•p

1

,…,n=(n/p

1

)•p

1

}

dunque tali interi sono in numero di n/p

1

, quindi X

1

=n/p

1

. Analogamente X

2

=n/p

2

,

X

3

=n/p

3

,…., X

r

=n/p

r

.

Poiché X

1

∩X

2

contiene tutti i numeri naturali x tali che 1xn e che sono multipli sia di p

1

che di p

2

, per il risultato preliminare 1) essi sono esattamente tutti i multipli del prodotto p

1

p

2

: analogamente a quanto dimostrato sopra, i multipli di p

1

p

2

compresi fra 1 ed n sono in numero di n/

(p

1

p

2

), quindi X

1

∩X

2

=n/(p

1

p

2

) . Analogamente si ha X

1

∩X

3

=n/(p

1

p

3

) e così via . Così procedendo, alla fine si ottiene:

φ(n)=n-X

1

X

2

…X

r

= n-[(n/p

1

+n/p

2

+….+n/p

r

)-(n/(p

1

p

2

)+n/(p

1

p

3

)+….)+…..±n/(p

1

p

2

…p

r

)]=

=n[1-(1/p

1

+1/p

2

+….+1/p

r

)+ (1/(p

1

p

2

)+1/(p

1

p

3

)+….)-…..±1/(p

1

p

2

…p

r

)], dove l’ultimo segno é + se r é pari, - se r é dispari.

Applicando allora il risultato preliminare 2) (dove si fanno assumere alle variabili i valori x

1

=1/p

1

,

….,x

r

=1/p

r

) la formula si semplifica come segue:

φ(n)=n(1-1/p

1

)(1-1/p

2

)…..(1-1/p

r

) (dove p

1,

p

2

,…., p

r

sono sempre i fattori primi distinti di n) Esempio: se n=2000=2

⁴

5

³

, il calcolo della funzione di Eulero è:

φ(2000)=2000(1-1/2)(1-1/5)=800

Considerata la fattorizzazione di n in prodotto di potenze di numeri primi distinti n = p ₁ ^k

¹

p ₂ ^k

²

...p _r ^k

^r

si ha dalla formula precedente:

φ(n)=n(1-1/p

1

)(1-1/p

2

)…..(1-1/p

r

)=n[(p

1

-1)/p

1

][(p

2

-1)/p

2

]...[(p

r

-1)/p

r

]=

= p ₁ ^k

¹

p ₂ ^k

²

...p _r ^k

^r

^[(p

¹

^-1)/p

¹

^][(p

²

^-1)/p

²

^]...[(p

^r

^-1)/p

^r

^]=

= p ₁ ^k

¹

^ ¹ p ₂ ^k

²

^ ¹ ...p _r ^k

^r

^ ¹ ^(p

¹

^-1)(p

²

-1)...(p

r

-1)

e si ottiene così una formula alternativa per il calcolo della funzione di Eulero : φ(n)= p ₁ ^k

¹

^ ¹ p ₂ ^k

²

^ ¹ ...p _r ^k

^r

^ ¹ ^(p

¹

^-1)(p

²

-1)...(p

r

-1)

(nella quale però, oltre la conoscenza dei fattori primi distinti p

1

,p

2

,…..,p

r

, è anche necessaria la

conoscenza degli esponenti k

1

,k

2

,…..,k

r

).

(3)

Relazioni di equivalenza in un insieme.

Supponiamo che A sia un insieme non vuoto e che sia definita una relazione R dall’insieme A all’insieme A (si dice anche che R è una relazione definita in A): quindi la relazione R associa elementi di A con elementi di A (spesso mediante un predicato P(x,y) in 2 variabili). Ricordiamo che con il simbolo aRb (dove a,b sono elementi di A) si intende indicare che l’elemento a è associato all’elemento b nella relazione R (quindi i valori x=a, y=b rendono vera la proposizione P(a,b)).

Diremo che R è una relazione di equivalenza se R soddisfa le seguenti 3 proprietà:

1) riflessiva: per ogni aA si ha aRa (quindi ogni elemento a di A è associato a sé stesso)

2) simmetrica: per ogni a,bA, se aRb allora bRa (quindi se un elemento a di A è associato ad un elemento b di A, allora l’elemento b è associato all’elemento a)

3) transitiva: per ogni a,b,cA, se aRb e bRc allora aRc (quindi se un elemento a di A è associato ad un elemento b di A, e se l’elemento b è associato ad un elemento c di A, allora l’elemento a è associato all’elemento c).

Esempio: definiamo la relazione R nell’insieme dei numeri naturali N mediante il predicato “x+y è pari”, e verifichiamo se è una relazione di equivalenza.

Proprietà riflessiva: per ogni aA si ha aRa, perché a+a=2a è pari. Proprietà simmetrica: per ogni a,bA, se aRb allora bRa, perché se a+b è pari anche b+a=a+b lo è (per la proprietà commutativa della somma). Proprietà transitiva: per ogni a,b,cA, se aRb e bRc allora aRc, perché se a+b, b+c sono pari, allora è pari la loro somma a+c+2b, dunque, sottraendo il pari 2b, anche a+c è pari.

Si conclude che R è un esempio di relazione di equivalenza definita nell’insieme N dei numeri naturali.

Classi di equivalenza

Sia definita nell’insieme A una relazione di equivalenza R.

Fissato un aA, possiamo costruire il sottoinsieme di A formato dagli elementi x che sono associati ad a nella relazione R :

{ xA / aRx } (notiamo che è equivalente scrivere aRx oppure xRa per la proprietà simmetrica) Tale sottoinsieme contiene almeno l’elemento a stesso (infatti per la proprietà riflessiva si ha aRa) dunque non è vuoto: esso è chiamato classe di equivalenza rappresentata dall’elemento a ed è indicato con il simbolo [a]:

[a] = { xA / aRx }

(l’elemento a è detto rappresentante della classe [a] ).

Esempio: nella relazione R dell’esempio precedente, costruiamo alcune classi di equivalenza fissando vari rappresentanti:

[3] = { xN / 3Rx } = { xN / 3+x è pari }= {1,3,5,7,….} = {numeri naturali dispari}

[8] = { xN / 8Rx } = { xN / 8+x è pari }= {2,4,6,8,….} = {numeri naturali pari}

[5] = { xN / 5Rx } = { xN / 5+x è pari }= {1,3,5,7,….} = {numeri naturali dispari}

In generale, ricordando che la somma di 2 numeri naturali è pari solo quando sono entrambi pari o

dispari, si ottiene che per un generico rappresentante aN la classe [a] da esso rappresentata

coincide con l’insieme dei numeri naturali dispari (se a è dispari) o con l’insieme dei numeri

(4)

naturali pari (se a è pari): dunque in questo esempio le diverse classi di equivalenza sono in tutto 2 sottoinsiemi di N: {numeri naturali dispari}, {numeri naturali pari}.

Come visto nell’ultimo esempio, elementi diversi dell’insieme possono essere rappresentanti di classi di equivalenza uguali: il numero 3 e il numero 5 sono rappresentanti della stessa classe di equivalenza [3]=[5]={numeri naturali dispari}. Il criterio per stabilire quando due elementi sono rappresentanti della stessa classe di equivalenza è il seguente:

Teorema. Sia definita nell’insieme A una relazione di equivalenza R.

Allora dati a,bA si ha:

[a ] = [b]  aRb Dimostrazione:

(): per ipotesi [a] = [b]; l’elemento a [a] (per la proprietà riflessiva), e dunque a[b] (essendo per ipotesi [a] = [b]), ossia aRb (tesi).

(): per ipotesi aRb; la tesi [a]=[b] richiede la dimostrazione di una doppia inclusione insiemistica [a]  [b] e [a]  [b].

Dimostriamo che [a]  [b] : preso un generico elemento x[a] si ha xRa; da xRa e dall’ipotesi aRb si ha bRx (per la proprietà transitiva), dunque x [b], e si può concludere che [a]  [b].

Viceversa dimostriamo che [b]  [a]: preso un generico elemento x[b] si ha xRb; dall’ipotesi aRb segue bRa (per la proprietà simmetrica); da xRb e da bRa si ha xRa (per la proprietà transitiva), dunque x [a], e si può concludere che [b]  [a].

Nota: nella dimostrazione precedente, tutte e 3 le proprietà simmetrica, riflessiva e transitiva sono utilizzate.

Le classi di equivalenza hanno una importante proprietà:

Teorema. Sia definita nell’insieme A una relazione di equivalenza R.

Allora le diverse classi di equivalenza formano una partizione dell’insieme A.

Dimostrazione:

Dimostriamo le proprietà che caratterizzano una partizione di A

1) Le classi di equivalenza sono sottoinsiemi non vuoti di A: questo è già stato notato prima, sfruttando la proprietà riflessiva (la classe rappresentata da a contiene almeno l’elemento a)

2) Date 2 generiche classi diverse [a]≠[b], esse sono disgiunte, ossia hanno intersezione vuota: per assurdo supponiamo che abbiano un elemento in comune x; dunque xRa (perché x [a]) e anche xRb (perché x[b]). Ma allora da aRx segue xRa (per la simmetrica) e da aRx e xRb segue aRb (per la transitiva). Infine da aRb segue, per il teorema precedente, l’eguaglianza [a]=[b], contraddizione.

3) L’unione di tutte le classi di equivalenza è uguale all’insieme A: ciò è ovvio, perché preso un generico elemento aA, tale elemento appartiene ad almeno una classe di equivalenza (per esempio alla classe [a], sempre per la proprietà riflessiva).

Esempio: nell’esempio precedente si sono ottenute 2 diverse classi di equivalenza {numeri naturali

pari} e {numeri naturali dispari}, e in effetti esse costituiscono una partizione di N, come affermato

dal Teorema.

(5)

Congruenze aritmetiche

Esamineremo alcune particolari relazioni di equivalenza definite nell’insieme Z dei numeri interi relativi (cioè positivi, negativi e lo 0).

Estendiamo dapprima i concetti di divisore e di multiplo dall’insieme N dei numeri naturali all’insieme Z dei numeri interi relativi: se a,bZ diremo che a è divisore di b (o che b è multiplo di a) e scriveremo ab , se esiste un cZ tale che ac=b.

Per esempio (-3)15 perché esiste –5Z tale che (-3)(-5)=15.

Osservazioni:

1) Per ogni aZ si ha 1a per l’identità 1a = a 2) Per ogni aZ si ha a0 per l’identità a0 = 0

3) L’unico aZ tale che 0a è a = 0 (in quanto se 0a esiste un cZ tale che 0c = a da cui a = 0).

Fissiamo un intero relativo mZ (detto modulo) e definiamo una particolare relazione nell’insieme Z mediante il predicato P(x,y)=”m(x-y)”. Dunque un numero intero relativo a è associato (in tale relazione) ad un numero intero relativo b quando m è divisore della differenza (a-b), o equivalentemente quando la differenza (a-b) è un multiplo di m.

Tale relazione è detta congruenza aritmetica modulo m, e se un intero relativo a è associato (in tale relazione) ad un intero relativo b, diremo che a è congruo b modulo m e scriveremo:

a≡b (mod m)

Per esempio: 12≡2 (mod 5) perché 5 è divisore della differenza (12-2)=10;-16≡5 (mod -7) perché -7 è divisore della differenza -16-5=-21.

Teorema. Fissato un qualunque intero relativo mZ, la relazione di congruenza modulo m è una relazione di equivalenza.

Dimostrazione:

Proprietà riflessiva: per ogni aZ si ha a≡a (mod m) perché a-a=0=m0 è multiplo di m.

Proprietà simmetrica: per ogni a,bZ se a≡b (mod m) allora si ha b≡a (mod m) perché se a-b=mk con kZ, allora b-a=-(a-b)=m(-k) con (-k)Z.

Proprietà transitiva: per ogni a,b,cZ se a≡b (mod m) e se b≡c (mod m) allora si ha a≡c (mod m) perché se a-b=mk, b-c=mh con k,hZ, allora a-c=(b+mk)-(b-mh)=m(h+k) con (h+k)Z.

Notiamo che se a≡b (mod m) allora esiste cZ tale che (a-b)=mc, da cui (a-b)=(-m)(-c) quindi si ha anche a≡b (mod -m); viceversa se a≡b (mod -m) allora si ha anche (con ragionamenti analoghi) che a≡b (mod m). Dunque la relazione di congruenza modulo m coincide con la relazione di congruenza modulo –m, da cui si deduce che possiamo limitarci a studiare le congruenze con modulo non negativo.

Quindi supporremo d’ora in poi che il modulo m sia sempre 0 . Studiamo alcuni casi particolari con moduli 0

a) il caso del modulo m=0: in tale caso si ha a≡b (mod 0) se (a-b) è multiplo di 0, quindi se esiste

cZ tale che a-b=0c=0 ossia se a=b. Dunque la relazione di congruenza modulo 0 coincide con la

relazione di eguaglianza: ogni classe di equivalenza contiene un solo elemento (il rappresentante

della classe) e si ottengono infinite classi.

(6)

b) il caso del modulo m=1: si ha a≡b (mod 1) se (a-b) è multiplo di 1, ma ciò è sempre vero (ogni xZ è multiplo di 1 per l’identità x =1x) . Dunque nella congruenza modulo 1 tutti gli interi relativi sono congrui fra loro: esiste allora un’unica classe di equivalenza, coincidente con l’intero insieme Z.

Avendo studiato in dettaglio tali casi particolari, ci limiteremo a studiare solo i casi rimanenti:

quindi supporremo sempre d’ora in poi che il modulo m sia >1.

Cercheremo di risolvere i seguenti problemi relativi alla relazione di congruenza modulo m:

1) Fissato il rappresentante aZ, quali sono i numeri interi relativi contenuti nella classe [a] ? 2) Quante sono le diverse classi di equivalenza ?

Per quanto riguarda il problema 1), se scegliamo ad arbitrio un rappresentante aZ, dalla teoria delle classi di equivalenza sappiamo che la classe di congruenza [a] rappresentata da a è definita come segue:

[a] = { xZ / x≡a (mod m) } = { xZ / m è divisore di x-a } = { xZ / x-a=mk con kZ }=

= { xZ / x=a+mk con kZ }.

Dunque gli elementi di [a] sono della forma x=a+mk con k che varia in Z: al variare del parametro k fra tutti gli interi relativi, si ottengono tutti gli elementi della classe [a] (che sono dunque infiniti numeri interi relativi).

Possiamo calcolare qualche elemento di [a] facendo assumere al coefficiente k alcuni particolari valori interi relativi (k=0,1,-1,2,-2,…..): [a] = {a , a+m , a-m , a+2m , a-2m ,….}

Esempio: nella congruenza modulo m=9, la classe [5] rappresentata da a=5 contiene i numeri della forma x=5+9k, con k che varia in Z: [5] = { 5, 14, -4, 23, -13, ….}.

Per quanto riguarda il problema 2), abbiamo visto che ogni classe di congruenza modulo m contiene infiniti numeri interi relativi, e conosciamo la struttura che hanno i numeri di ogni classe, ma quante sono in tutto le distinte classi di congruenza modulo m ?

Esaminiamo prima un esempi particolare.

Esempio. Studiamo le classi di congruenza modulo m=3.

Costruiamo una di tali classi, fissando per esempio il rappresentante a=5:

[5] = { xZ / x≡5 (mod 3) } = { xZ / x=5+3k con kZ } = {5, 8, 2, 11, -1, …}

Se vogliamo costruire una classe di congruenza diversa da [5], dobbiamo scegliere un rappresentante che non sia congruo 5 modulo 3 (perché sappiamo da un Teorema precedente che se aRb allora [a]=[b]). Possiamo per esempio scegliere a=9 (la differenza 9-5=4 non è multiplo di m=3):

[9] = { xZ / x≡9 (mod 3) } = { xZ / x=9+3k con kZ } = {9, 12, 6, 15, 3, …}

Se vogliamo costruire una classe di equivalenza diversa dalle 2 classi già costruite, dobbiamo scegliere un rappresentante a che non sia congruo 5 modulo 3 e che non sia congruo 9 modulo 3.

Possiamo per esempio scegliere a=-2 (le differenze -2-5=-2, -2-9=-11 non sono multipli di m=3):

[-2] = { xZ / x≡-2 (mod 3) } = { xZ / x=-2+3k con kZ } = {-2, 1, -5, 4, -8, …}

A questo punto, anche facendo diversi tentativi, ci accorgiamo di non riuscire a costruire una classe di equivalenza diversa dalle 3 già costruite, perché non riusciamo a trovare un rappresentante a che non sia congruo 5 modulo 3, che non sia congruo 9 modulo 3, e che non sia congruo -2 modulo 3.

Da questo ragionamento un po’ empirico, possiamo concludere che le classi di congruenza distinte modulo 3 sono:

[5], [9], [-2]

ossia le classi sono in numero di 3, cioè in numero uguale al modulo.

(7)

Il prossimo teorema dimostrerà che ciò non è casuale.

Premettiamo però una generalizzazione dell’algoritmo della divisione, che abbiamo dimostrato già valido per una coppia di numeri naturali a,b, ma che estenderemo anche al caso in cui il primo numero a è <0.

Teorema (Algoritmo della divisione generalizzato).

Dati comunque i numeri interi non nulli a,b tali che sia b>0, esistono (e sono unici) due numeri interi relativi q,r (detti quoziente e resto) tali che a=bq+r, con r0 ed r<b.

(notare che non si pretende più che il quoziente q sia 0).

Dimostrazione:

Se a>0 la tesi è ovvia, perché si tratta dell’algoritmo della divisione per numeri naturali, già dimostrato in precedenza. Quindi supponiamo a<0.

Essendo a<0 si ha (–a)>0, dunque possiamo applicare l’algoritmo della divisione per numeri naturali, dividendo il numero –a>0 per il numero b>0 e trovando quoziente q

0

e resto r

0

(interi 0) tali che (-a)=bq

0

+r

0

con r

0

<b. Distinguiamo 2 casi possibili:

I° caso: r

0

=0. In questo caso si ha (-a)=bq

0

quindi a=(-bq

0

)=b(-q

0

)+0 e basta porre q=-q

0

, r=0, per ottenere l’esistenza di q,r e quindi la tesi.

II° caso: r

0

>0. In questo caso si ha a= -bq

0

-r

0

= -bq

0

-b+b-r

0

= b(-q

0

-1)+b-r

0

e basta porre q=-q

0

-1, r=b-r

0

, per ottenere l’esistenza di q,r e quindi la tesi (notare che la proprietà r<b è soddisfatta perché r

0

>0).

L’unicità del quoziente q e del resto r si dimostra con metodi simili a quelli utilizzati nell’algoritmo della divisione per i numeri naturali.

Nel prossimo Teorema dimostreremo quali e quante sono le classi di congruenza distinte modulo m>1.

Teorema. Fissato il modulo intero m>1, le seguenti classi di congruenza modulo m:

[0], [1], ………., [m-1] (*)

sono tutte distinte ed esauriscono tutte le classi di congruenza modulo m. In particolare vi sono dunque esattamente m distinte classi di congruenza modulo m.

Dimostrazione:

La tesi richiede la dimostrazione di 2 affermazioni:

**a) le classi (*) sono tutte le classi di congruenza modulo m.**

**b) le classi (*) sono distinte**

Dimostriamo la a): comunque preso un rappresentante aZ la tesi è che [a] coincide con una delle classi (*). Se a è uno dei numeri 0,1,….,m-1, non c’è niente da dimostrare. Sia dunque a diverso da 0,1,….,m-1.

Possiamo applicare l’algoritmo della divisione generalizzato ai numeri a,m, trovando quoziente q e resto r (interi relativi) tali che a=mq+r, con r0 ed r<m.

Si ha allora a-r=mq, ossia a≡r (mod m) e da ciò si ricava [a]=[r].

Ma i valori possibili del resto r sono i numeri 0,1,…,m-1, dunque [a] coincide con una delle classi (*), come volevamo dimostrare nella a).

Dimostriamo la b): la tesi è che le classi (*) sono distinte. Se per assurdo 2 di tali classi coincidessero, si avrebbe [x] = [y], con 0≤x,y≤m-1, e con xy (per esempio sia x>y: nel caso opposto x<y si ragiona in modo analogo). Da [x]=[y] seguirebbe x≡y(mod m), ossia x-y sarebbe un multiplo di m, cioè x-y=kt con k intero; ma x-y>0 (perché x>y) ed inoltre x-y<m (perché x<m) e ciò implicherebbe k>0 e k<1, contraddizione perché k è intero.

Esempio: consideriamo il modulo m=6. Per il Teorema precedente vi sono 6 distinte classi di

congruenza modulo 6 ed esse sono [0], [1], [2], [3], [4], [5]. Se prendiamo una qualunque classe di

congruenza modulo 6, essa coinciderà con una di queste 6 classi.

(8)

Nell’esempio precedente in cui abbiamo studiato empiricamente le classi di congruenza modulo 3, trovando le 3 classi:

[5], [9], [-2]

possiamo notare che [5]=[2], [9]=[0], [-2]=[1]

dunque le 3 classi di congruenza distinte modulo 3 sono:

[0], [1], [2]

coerentemente con l’ultimo teorema dimostrato.

Operazioni in un insieme.

In aritmetica é ben noto il concetto di “operazione” fra numeri: un esempio sono le operazioni di somma e prodotto fra numeri naturali.

Ma cos’è formalmente un’operazione ?

Se esaminiamo la somma fra numeri naturali, essa non è altro che una regola che associa ad ogni coppia (x,y) di numeri naturali (detti “addendi”) un unico numero naturale x+y (detto “somma”).

Nel linguaggio insiemistico dunque la somma fra numeri naturali è una funzione f. NxNN.

Da queste osservazioni si perviene facilmente alla seguente definizione più generale:

Un’operazione definita nell’insieme (non vuoto) A è una funzione f : AxA → A

(dove AxA = {(x,y) / x,yA } è il prodotto cartesiano contenente le coppie ordinate di elementi di A) che associa ad ogni coppia ordinata (x,y) di elementi di A uno e un solo elemento f(x,y)A.

Gli elementi x,y sono detti operandi (l’elemento x è il primo operando, l’elemento y è il secondo operando), mentre l’elemento f(x,y) è detto risultato dell’operazione sugli operandi x,y.

Useremo spesso il simbolo xy per indicare il risultato f(x,y) dell’operazione sugli operandi x,y.

Esempio.

Nell’insieme N dei numeri naturali sono esempi di operazioni quelle definite ponendo:

xy = x+y (somma) xy = x∙y (prodotto)

xy = x

^y

(elevamento a potenza)

Poiché un’operazione non è altro che una funzione, un’operazione in un insieme A può essere definita:

- in modo implicito: dati 2 operandi variabili x,y in A si definisce un’operazione ponendo xy = ………

dove dopo il segno di eguaglianza vi è una “formula” nelle variabili x, y che permette di calcolare il risultato, dati gli operandi x,y.

Gli esempi precedenti di operazioni di somma, prodotto, elevamento a potenza in N sono definiti in modo implicito. Ovviamente nello stesso insieme N potremmo definire in modo implicito altre operazioni, ovviamente meno “utili” di quelle precedenti (che sono legate al procedimento di

“contare”).

Per esempio potremmo definire in modo implicito un’operazione in N ponendo:

xy = x + y + xy

Se volessimo allora calcolare in particolare in questa operazione il risultato 32 dovremmo calcolare:

32 = 3 + 2 + 32 = 11

- in modo esplicito (tale modalità è praticabile solo nel caso in cui l’insieme A sia finito): per

ognuna delle possibili coppie di operandi x,y in A si indica esplicitamente il risultato xy (che deve

essere un unico elemento di A).

(9)

Per esempio nell’insieme A = {a, b, c} delle prime 3 lettere dell’alfabeto, possiamo definire un’operazione indicando, per ognuna delle 9 coppie possibili di operandi in A, il risultato nel modo seguente:

aa=b, bb=b, cc=a, ab=c, ba=a, ac=b, ca=c, bc=a, cb=a

Si può rendere la definizione esplicita di una operazione (definita in un insieme finito A di cardinalità n) utilizzando una tavola operazionale: è una matrice quadrata di n

²

caselle disposte in n righe e n colonne, in cui si fanno corrispondere alle righe e alle colonne ordinatamente gli elementi di A (in un ordine prefissato), e inserendo in ogni casella il risultato xy, dove x è l’operando corrispondente alla riga della casella, y è l’operando corrispondente alla colonna della casella.

Nell’ esempio precedente, l’operazione definita nell’insieme A = {a, b, c} di cardinalità 3 avrebbe la seguente tavola operazionale 3x3 (rispetto all’ordine prefissato a,b,c):

a b c a

b c

Operazioni compatibili con una relazione di equivalenza.

Consideriamo un insieme A in cui sia definita una relazione di equivalenza R: ricordiamo che se l’elemento xA è associato nella relazione R all’elemento yA scriviamo il simbolo xRy.

Inoltre per ipotesi R soddisfa le proprietà riflessiva, simmetrica e transitiva.

Sappiamo che, fissato xA, si può costruire la classe di equivalenza rappresentata da x, contenente tutti gli elementi di A che sono associati ad x nella relazione R:

[x] = { yA / xRy }

Ricordiamo inoltre che le distinte classi di equivalenza formano una partizione di A (cioè 2 classi diverse hanno intersezione vuota, e l’unione di tutte le classi è l’insieme A).

Si ha inoltre, per un risultato già dimostrato:

[x]=[y]  xRy .

Indicheremo con il simbolo A/R l’insieme delle classi di equivalenza della relazione R in A (è detto anche insieme quoziente dell’insieme A rispetto alla relazione di equivalenza R).

Supponiamo anche che nell’insieme A sia definita (oltre alla relazione di equivalenza R) anche un’operazione *.

Potremmo allora provare a definire nell’insieme A/R delle classi di equivalenza un’operazione fra classi (che indichiamo sempre con il simbolo ) servendoci dell’operazione (che è definita nell’insieme A) nel modo seguente:

[a][b] = [ab]

(quindi per calcolare il risultato dell’operazione sulle classi [a],[b] prima si calcola il risultato dell’operazione * sui rappresentanti a,b, ottenendo un elemento a*b in A, e poi si considera la classe rappresentata da tale elemento, e questa classe si considera come risultato dell’operazioni fra le 2 classi [a],[b]).

Ciò solleva però un problema: il concetto di operazione implica l’unicità del risultato (perché l’operazione è una funzione che associa ad ogni coppia di operandi uno e un solo risultato). Quindi per essere certi che la nostra operazione fra classi abbia risultato unico (fissate le 2 classi su cui si opera) dobbiamo essere sicuri che se [a]=[c] e se [b]=[d] (abbiamo lasciato invariate le 2 classi ma

b c b

a b a

c a a

(10)

cambiato il rappresentante) allora si ha sempre [ab]=[cd] (il risultato deve essere invariato). Tale proprietà si può esprimere in modo equivalente nel modo seguente:

se aRc, e se bRd allora necessariamente (ab)R(cd)

**(tale proprietà è detta compatibilità della relazione di equivalenza R con l’operazione *).**

Riassumendo dunque: se in un insieme A sono definite sia una relazione di equivalenza R che un’operazione , e se R è compatibile con (cioè se da aRc, bRd segue sempre (ab)R(cd)) allora nell’insieme A/R delle classi di equivalenza si può definire un’operazione * fra classi (con risultato unico) ponendo [a][b] = [ab].

**Tale operazioni fra classi di equivalenza è detta operazione indotta dall’operazione * definita in A.**

Operazioni fra classi congruenza.

Ricordiamo che, fissato un intero m>1 (modulo), abbiamo definito nell’insieme Z degli interi relativi una relazione di equivalenza, detta congruenza modulo m: dati gli interi x,yZ, x associato con y quando (x-y) è multiplo di m (cioè se esiste kZ tale che x-y=mk).

Ricordiamo anche che se x è associato con y si scrive xy (mod m) invece di xRy (e si legge x congruo y modulo m).

Si possono costruire dunque le classi di equivalenza di tale relazione, che sono dette classi di congruenza modulo m.

Abbiamo dimostrato anche che le classi di congruenza distinte modulo m sono le seguenti:

[0], [1], ……, [m-1]

e quindi sono in numero di m (cioè in numero uguale al modulo).

L’insieme quoziente di Z rispetto alla relazione di congruenza modulo m (cioè l’insieme delle classi di congruenza modulo m) sarà indicato con il simbolo Z

m

: quindi

Z

m

= { [0], [1], ……, [m-1] }

Esempi: l’insieme delle classi di congruenza distinte modulo 7 è il seguente:

Z

7

= { [0], [1], [2], [3], [4], [5], [6] }

Dimostreremo ora che sia l’operazione di somma che quella di prodotto esistenti fra numeri interi relativi in Z sono compatibili con la relazione di congruenza modulo m.

Compatibilità della congruenza modulo m con la somma di numeri interi relativi:

se ac (mod m), e se bd (mod m) allora m è divisore delle differenze a-c, b-d, dunque a-c=mk, b-d=mh (con k,h interi)

da cui:

(a+b)-(c+d)=m(h+k)

ossia m è divisore della differenza (a+b)-(c+d) e si conclude che (a+b)(c+d) (mod m) Compatibilità della congruenza modulo m con il prodotto:

con le stesse notazioni, si ha:

(ab)-(cd)=a(b-d)+d(a-c)=m(ah+dk)

ossia m è divisore della differenza (ab)-(cd) e si conclude che (ab)(cd) (mod m).

Dalla compatibilità delle operazioni di somma e prodotto con la relazione di congruenza modulo m, segue che é possibile definire, nell’insieme Z

m

delle classi di congruenza modulo m, le operazioni di somma e prodotto fra classi di congruenza, operazioni indotte dalle operazioni di somma e prodotto fra numeri interi e definite nel modo seguente:

[a]+[b] = [a+b] [a][b] = [ab]

(11)

Esempio.

Consideriamo l’insieme Z

7

delle 7 classi di congruenza modulo 7:

Z

7

= { [0],[1],[2],[3],[4],[5],[6] } e le seguenti classi di congruenza modulo 7 [5], [6]Z

7

Possiamo allora calcolare la somma e il prodotto di queste 2 classi:

[5]+[6] = [5+6] = [11] = [4] (perché 114 (mod 7)) [5][6] = [56] = [30] = [2] (perché 302 (mod 7)) Esempio.

Consideriamo l’insieme Z

4

delle 4 classi di congruenza modulo 4:

Z

4

= {[0],[1],[2],[3]}

Se costruiamo la tavola operazionale della somma fra classi (rispetto all’ordine [0],[1],[2],[3]) otteniamo la seguente matrice 4x4:



 









 







] 2 [ ] 1 [ ] 0 [ ] 3 [

] 1 [ ] 0 [ ] 3 [ ] 2 [

] 0 [ ] 3 [ ] 2 [ ] 1 [

] 3 [ ] 2 [ ] 1 [ ] 0 [

(per calcolare per esempio [2]+[3] si calcola [2+3]=[5]=[1], notando che 51 (mod 4) etc…..) Se invece costruiamo la tavola operazionale del prodotto fra classi (rispetto sempre all’ordine [0], [1],[2],[3]) otteniamo la seguente matrice 4x4: