Funzione phi di Eulero

La funzione phi di Eulero φ(n), detta anche funzione totiente o semplicemente funzione di Eulero, è 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 quattro numeri 1, 3, 5 e 7 sono coprimi di 8.

Così chiamata in onore del matematico svizzero Eulero, φ(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.

Table of contents

1 Calcolo della funzione 2 Altre proprietà 3 Funzione generatrice 4 Alcuni valori della funzione 5 Argomenti correlati e link esterni

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^k.

Ancora: se m ed n sono coprimi, allora φ(mn) = φ(m). 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 inidcati r distinti numeri primi, allora:

φ(n) = (p₁-1) p₁^k₁-1 ... (p_r-1) p_r^k_r-1.

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:

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 ottenede un'altra formula per la φ(n):

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

Funzione generatrice

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

Alcuni valori della funzione

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8

	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40
	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12	36	18	24	16

	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
	40	12	42	20	24	22	46	16	42	20	32	24	52	18	40	24	36	28	58	16

	61	62	63	64	65	66	67	68	69	...
	60	30	36	32	48	20	66	32	44	...

Argomenti correlati e link esterni

La funzione di Eulero è molto utile in diversi campi: oltre che in matematica, infatti, è utilizzata anche in crittografia (vedi, ad esempio, L'aritmetica modulare).

Alcune risorse esterne sulla funzione di Eulero, in inglese, sono:

• Totient Function
• Euler Totient Function

---

|