.....ppp dove p

(1)

Matematica Discreta

Lezione del giorno 15 marzo 2012

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 p1, p2, …., pr sono fattori primi distinti di n.

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 p1, p2,…,pr (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à:

p1 è divisore di x; p2 è divisore di x; ….. ; pr è 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:

Xi = {xX / pi è divisore di x} ( al variare di i=1,2,…,r) Si avrà:

φ(n)= X-X1X2…Xr= n -X1X2…Xr.

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

X1X2…Xr=α1-α2+α3-α4+…….±αr

dove α1 è la somma delle cardinalità dei singoli insiemi Xi; α2 è la somma delle cardinalità di tutte le possibili intersezioni a 2 a 2 degli insiemi Xi;……, αr è la cardinalità dell’intersezione di tutti gli insiemi Xi, preceduta da un segno + se r è dispari, da un segno – se r è pari.

Poiché X1 contiene tutti i multipli di p1 compresi fra 1 ed n si ha:

X1 = {1•p1,2•p1,…,n=(n/p1)•p1}

dunque tali interi sono in numero di n/p1, quindi X1=n/p1 . Analogamente X2=n/p2,

X3=n/p3 ,…., Xr=n/pr .

Poiché X1∩X2 contiene tutti i numeri naturali x tali che 1xn e che sono multipli sia di p1 che di p2, per il risultato preliminare 1) essi sono esattamente tutti i multipli del prodotto p1p2: analogamente a quanto dimostrato sopra, i multipli di p1p2 compresi fra 1 ed n sono in numero di n/

(p1p2), quindi X1∩X2=n/(p1p2) . Analogamente si ha X1∩X3=n/(p1p3) e così via . Così procedendo, alla fine si ottiene:

φ(n)=n-X1X2…Xr= n-[(n/p1+n/p2+….+n/pr)-(n/(p1p2)+n/(p1p3)+….)+…..±n/(p1p2…pr)]=

=n[1-(1/p1+1/p2+….+1/pr)+ (1/(p1p2)+1/(p1p3)+….)-…..±1/(p1p2…pr)], dove l’ultimo segno é + se r é pari, - se r é dispari.

Applicando allora il risultato preliminare 2) (dove si fanno assumere alle variabili i valori x1=1/p1,

….,xr=1/pr) la formula si semplifica come segue:

φ(n)=n(1-1/p1)(1-1/p2)…..(1-1/pr) (dove p1, p2,…., pr 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/p1)(1-1/p2)…..(1-1/pr)=n[(p1-1)/p1][(p2-1)/p2]...[(pr-1)/pr]=

=p₁^k¹p₂^k²...p_r^k^r ^[(p¹^-1)/p¹^][(p²^-1)/p²^]...[(p^r^-1)/p^r^]=

(2)

=p₁^k¹^¹p₂^k²^¹...p_r^k^r^¹^(p¹^-1)(p²-1)...(pr-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)...(pr-1)

(nella quale però, oltre la conoscenza dei fattori primi distinti p1,p2,…..,pr, è anche necessaria la conoscenza degli esponenti k1,k2,…..,kr).

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

(3)

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 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: come si può notare nella dimostrazione precedente, tutte e 3 le proprietà simmetrica, riflessiva e transitiva sono utilizzate.