Funzione φ di Eulero

Da Wikipedia, l'enciclopedia libera.

(Reindirizzamento da Funzione phi di Eulero)

I primi mille valori di $\varphi$

La funzione phi di Eulero φ(n), detta anche funzione totiente o semplicemente funzione di Eulero o totiente, è definita, per ogni intero positivo n, come il numero degli interi positivi minori di n tali che sono coprimi con n. Ad esempio, φ(8) = 4 poiché i numeri coprimi di 8 sono quattro: 1, 3, 5 e 7. Deve il suo nome al matematico svizzero Eulero, che per primo la descrisse.

$\varphi(n)$ è una funzione molto importante nella teoria dei numeri, principalmente perché è la cardinalità del gruppo moltiplicativo di interi di modulo n, più precisamente l'ordine del gruppo dell'anello Z/nZ (vedere aritmetica modulare). Questo fatto, unito con il teorema di Lagrange, dimostra il teorema di Eulero: se a è un numero coprimo con n, allora

$a^{\varphi(n)}\equiv 1\mod n$

[modifica] Moltiplicatività

La funzione phi di Eulero è moltiplicativa: per ogni coppia di interi a e b tali che MCD(a,b)=1 si ha

$\varphi(ab)=\varphi(a)\varphi(b)$

Questo fatto può essere dimostrato in molti modi: ad esempio, si può osservare che un numero è coprimo con ab se e solo se è coprimo sia con a che con b. Infatti, dato un x coprimo con ab, questo non ha fattori in comune con ab, e quindi non ha fattori in comune né con a né con b; viceversa, se x è coprimo con a e con b, ed esistesse un primo p che divide sia ab che x, p dovrebbe dividere, per il lemma di Euclide, almeno uno tra a e b, e quindi non può esser coprimo con entrambi.

Una volta dimostrato questo, si osserva che ogni coppia (y,z), con $y\in\mathbb{Z}_a$ e $z\in\mathbb{Z}_b$ corrisponde ad uno ed un solo elemento $w\in\mathbb{Z}_{ab}$ (o, per essere più formali, che esiste un isomorfismo tra gli anelli $\mathbb{Z}_a\times\mathbb{Z}_b$ e $\mathbb{Z}_{ab}$ ). Quindi il numero di elementi coprimi con ab è uguale a quello delle coppie (y,z) dove y è coprimo con a e z con b.

Per definizione i primi sono $\varphi(a)$ e i secondi $\varphi(b)$ , e quindi in definitiva ci sono $\varphi(a)\varphi(b)$ elementi coprimi con ab, che per definizione con $\varphi(ab)$

[modifica] Calcolo della funzione

Secondo la definizione, si può verificare che φ(1) = 1, e φ(n) vale (p-1)p^k-1 quando n è la k-sima potenza di un numero primo p, ovvero quando n = p^k.

Ancora: se m ed n sono coprimi, allora φ(mn) = φ(m)φ(n). Il valore di φ(n) può così essere calcolato utilizzando il teorema fondamentale dell'aritmetica:

se n = p₁^k₁ ... p_r^k_r

dove con p_j sono indicati r distinti numeri primi, allora:

$\varphi(n)=p_1^{k_1-1}(p_1-1)\cdot p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1)$

o, in forma più compatta:

$\varphi(n)=n\cdot \left[\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right)\right]$

Questa scrittura permette inoltre di dimostrare che i valori della funzione phi possono essere arbitrariamente piccoli rispetto ad n (cioè il rapporto $\varphi(n)/n$ è minore di qualunque $ε$ per qualche valore di n): estendendo infatti il prodotto a tutti i primi, si ottiene

$\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots=\left[\frac{p_1}{p_1-1}\cdot\frac{p_2}{p_2-1}\cdots\right]^{-1}$

Quella tra parentesi è la scrittura del prodotto di Eulero della funzione zeta di Riemann per s=1, cioè la somma

$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots$

ovvero la serie armonica, che diverge. Quindi il suo inverso è 0, e la successione

$\frac{\phi(n)}{n}$

diventa arbitrariamente vicina a 0.

[modifica] Altre proprietà

Il numero φ(n) è anche pari al numero di generatori del gruppo ciclico C_n. Da ciascun elemento di C_n si può generare un sottogruppo ciclico C_d dove d divide n (la notazione è d|n), ottenendo:

$\sum_{d\mid n}\varphi(d)=n$

dove la somma è estesa a tutti i divisori d di n.

Si può ora utilizzare la funzione di inversione di Möbius per invertire questa somma e ottenere un'altra formula per la φ(n):

$\varphi(n)=\sum_{d\mid n} d \cdot \mu\left({n\over d}\right)$

dove $μ$ è l'usuale funzione di Möbius definita sugli interi positivi.

Abbiamo inoltre che, se n è un numero primo:

$\varphi(n) = n - 1 \,$

Dato che, ovviamente, ogni numero minore di n gli è coprimo, essendo n primo.

Esiste una sequenza di valori di n tale che

$\varphi(n) = \varphi(n+1) \,$

i primi sono 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (sequenza A001274 dell'OEIS).

Esiste un solo numero $n < 10^{10} \,$ tale che

$\varphi(n) = \varphi(n+1) = \varphi(n+2) \,$

e si tratta di 5186, per il quale si ha infatti

$\varphi(5186) = \varphi(5186+1) = \varphi(5186+2) = 2^5 \cdot 3^4 \,$

Esiste una progressione aritmetica di ragione 30 composta da sei numeri, che generano tutti lo stesso valore di φ:

$\varphi(583200) = \varphi(583230) = \varphi(583260) = \,$

$\varphi(583290) = \varphi(583320) = \varphi(583350) = \,$

$= 155520 = 2^7 \cdot 3^5 \cdot 5 \,$

[modifica] Funzione generatrice

Una serie di Dirichlet che genera la φ(n) è

$\sum_{n=0}^{\infty} \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}$

dove $ζ$ è la funzione zeta di Riemann.

[modifica] Alcuni valori della funzione

$\varphi(n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

[modifica] Voci correlate

[modifica] Bibliografia

Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9, (Chapter 2)
H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 8808091546 - Capitolo II.4

[modifica] Collegamenti esterni

(EN) Totient Function
(EN) Euler Totient Function

Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica

Funzione φ di Eulero

Da Wikipedia, l'enciclopedia libera.

Indice

[modifica] Moltiplicatività

[modifica] Calcolo della funzione

[modifica] Altre proprietà

[modifica] Funzione generatrice

[modifica] Alcuni valori della funzione

[modifica] Voci correlate

[modifica] Bibliografia

[modifica] Collegamenti esterni

Visite

Strumenti personali

Navigazione

comunità

Ricerca

Strumenti

Altre lingue

$\varphi(n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

$\varphi(n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

$\varphi(n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60