.....ppp dove p

(1)

Matematica Discreta I

Lezione del giorno 26 novembre 2007

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

La funzione di Eulero.

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 compresi fra 1 ed n che sono coprimi con n.

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

Esempio: se n=12, i numeri x compresi fra 1 ed 12 che sono coprimi con 12 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.

Infatti 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 :

(1-x

1

)(1-x

2

)=1-(x

1

+x

2

)-x

1

x

2

Per r=3 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

Per un valore generico di r 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 m è pari, da un segno – se m è dispari. (tale formula si dimostra formalmente per induzione, ma omettiamo la dimostrazione).

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.

(2)

Un numero naturale x compreso fra 1 ed n é coprimo quando 1 è l’unico divisore comune fra x ed n, cioè quando x non è multiplo di nessuno dei primi p

1

, p

2

,…,p

r

. Quindi per calcolare φ(n) dobbiamo calcolare il numero degli x fra 1 ed n 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 l’insieme A di tutti gli interi fra 1 ed n, e gli r sottoinsiemi di A:

A

i

= {xX / p

i

è divisore di x} ( al variare di i=1,2,…,r) e 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

m

=n/p

m

.

Poiché X

1

∩X

2

contiene tutti gli interi fra 1 ed n che sono multipli sia di p

1

che di p

2

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

1

p

2

(compresi fra 1 ed n: analogamente a quanto dimostrato sopra, i multipli di p

1

p

2

fra 1 ed n sono in numero di 1/(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 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