Matematica Discreta I Lezione del giorno 8 gennaio 2009

(1)

Matematica Discreta I

Lezione del giorno 8 gennaio 2009

Un’altra interessante applicazione dell’uso negativo del principio di inclusione-esclusione è il calcolo della cosiddetta funzione di Eulero.

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 di n la funzione φ(n) che associa ad n il numero 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=12, i numeri naturali x tali che 1x12 ed x,12 sono coprimi sono 1,5,7,11, quindi φ(12)=4 .

Cercheremo una formula che permetta di calcolare φ(n) conoscendo la fattorizzazione di n in prodotto di fattori 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 dei generici numeri reali) e cerchiamo di calcolare il valore dell’espressione:

(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.

(2)

Torniamo ora al calcolo della funzione di Eulero φ(n). Essendo n>1, possiamo considerare la fattorizzazione di n in prodotto di 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.

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 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 m è dispari, da un segno – se m è 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 m é pari, - se m é 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 :

(3)

φ(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

).