Funzione φ di Eulero

I primi mille valori di $\phi$

In matematica, la funzione φ di Eulero o semplicemente funzione di Eulero o toziente, è una funzione definita, per ogni intero positivo $n$, come il numero degli interi compresi tra $1$ e $n$ che sono coprimi con $n$. Ad esempio, $\phi (8)=4$ poiché i numeri coprimi di 8 sono quattro: 1, 3, 5, 7. Deve il suo nome al matematico svizzero Eulero, che per primo la descrisse.

La funzione $\phi (n)$ è una funzione molto importante nella teoria dei numeri, principalmente perché è la cardinalità del gruppo moltiplicativo degli interi modulo $n$, più precisamente è l'ordine del gruppo moltiplicativo dell'anello $\mathbb{Z}/n\mathbb{Z}$ (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^{\phi (n)}\equiv 1modn$

Moltiplicatività

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

$\phi (ab)=\phi (a)\phi (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 sia 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 sia x, p dovrebbe dividere, per il lemma di Euclide, almeno uno tra a e b, e quindi x 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 a uno e 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 $\phi (a)$ e i secondi $\phi (b)$, e quindi in definitiva ci sono $\phi (a)\phi (b)$ elementi coprimi con ab che è per definizione il valore $\phi (ab)$

Calcolo della funzione

Un'espressione per la funzione è la seguente:

$\phi (n)=n\cdot [(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})]=n\prod _{p\mid n}(1-\frac{1}{p})$

dove i $p_i$ sono tutti i primi che compongono la fattorizzazione di n.

Dimostrazione

Mostriamo innanzitutto che, se p è un numero primo, allora $\phi (p^k)=(p-1)p^{k-1}$ per ogni $k>0$.

Per fare ciò, troviamo tutti i numeri m minori o uguali a $p^k$ per i quali $MCD(p^k,m)\ne 1$. Ciò equivale a dire che m deve avere dei fattori in comune con $p^k$. Ma p è primo, quindi se m ha dei fattori in comune con p, questi devono essere multipli di una potenza di p. Quindi tutti i possibili valori di m sono $p,2p,3p,\dots ,p^{k-1}\cdot p$. Questi numeri sono $p^{k-1}$, e sono tutti i numeri che non sono coprimi con $p^k$. Tutti i numeri minori o uguali a $p^k$ sono $p^k$, quindi i numeri primi con $p^k$ minori di $p^k$ sono i restanti $p^k-p^{k-1}$.

Quindi $\phi (p^k)=p^k-p^{k-1}=(p-1)p^{k-1}$

Utilizzando il teorema fondamentale dell'aritmetica possiamo fattorizzare qualsiasi numero $n$ in un prodotto di numeri primi elevati a una certa potenza:

$n=p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r}$

dove i $p_i$ sono numeri primi distinti, e ogni $k_i>0$

Quindi $\phi (n)=\phi (p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r})$

Ora, poiché $\phi$ è moltiplicativa possiamo espandere la funzione:

$\phi (n)=\phi (p_1^{k_1})\phi (p_2^{k_2})\dots \phi (p_r^{k_r})=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)$

(La funzione è moltiplicativa tra due numeri se e solo se essi sono primi tra loro. Nel nostro caso, i numeri $p_i$ sono tutti primi, e quindi primi tra loro)

La formula può essere riscritta in una forma più compatta:

$\phi (n)=n\cdot [(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r})]=n\prod _{p\mid n}(1-\frac{1}{p})$

Andamento asintotico

La scrittura prima trovata permette inoltre di dimostrare che i valori della funzione φ possono essere arbitrariamente piccoli rispetto a n (cioè il rapporto $\phi (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 ={[\frac{p_1}{p_1-1}\cdot \frac{p_2}{p_2-1}\cdots ]}^{-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 è infinitesimale, e la successione

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

diventa arbitrariamente vicina a 0.

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}\phi (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):

$\phi (n)=\sum _{d\mid n}d\cdot \mu \left(\frac{n}{d}\right)$

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

• Abbiamo inoltre che, se n è un numero primo:

$\phi (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

$\phi (n)=\phi (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

$\phi (n)=\phi (n+1)=\phi (n+2)$

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

$\phi (5186)=\phi (5186+1)=\phi (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 φ  :

$\phi (583200)=\phi (583230)=\phi (583260)=$

$\phi (583290)=\phi (583320)=\phi (583350)=$

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

• $a\mid b$ implica $\phi (a)\mid \phi (b)$
• $\phi (n)$ è pari per $n\ge 3$. Inoltre, se n ha r fattori primi distinti dispari, allora $2^r\mid \phi (n)$

Funzione generatrice

Le due funzioni generatrici presentate qui sono entrambe conseguenze del fatto che

$\sum _{d|n}\phi (d)=n.$

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

$\sum _{n=0}^{\mathrm{\infty }}\frac{\phi (n)}{n^s}=\frac{\zeta (s-1)}{\zeta (s)}$

dove $\zeta$ è la funzione zeta di Riemann. Ciò deriva da quanto segue:

$\zeta (s)\sum _{f=1}^{\mathrm{\infty }}\frac{\phi (f)}{f^s}=\left(\sum _{g=1}^{\mathrm{\infty }}\frac{1}{g^s}\right)\left(\sum _{f=1}^{\mathrm{\infty }}\frac{\phi (f)}{f^s}\right)$

$\left(\sum _{g=1}^{\mathrm{\infty }}\frac{1}{g^s}\right)\left(\sum _{f=1}^{\mathrm{\infty }}\frac{\phi (f)}{f^s}\right)=\sum _{h=1}^{\mathrm{\infty }}(\sum _{fg=h}1\cdot \phi (g))\frac{1}{h^s}$

$\sum _{h=1}^{\mathrm{\infty }}(\sum _{fg=h}\phi (g))\frac{1}{h^s}=\sum _{h=1}^{\mathrm{\infty }}(\sum _{d|h}\phi (d))\frac{1}{h^s}$

$\sum _{h=1}^{\mathrm{\infty }}(\sum _{d|h}\phi (d))\frac{1}{h^s}=$$\sum _{h=1}^{\mathrm{\infty }}\frac{h}{h^s}$

$\sum _{h=1}^{\mathrm{\infty }}\frac{h}{h^s}=\zeta (s-1).$

La funzione generatrice di una serie di Lambert è

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)q^n}{1-q^n}=\frac{q}{(1-q{)}^2}$

che converge per |q| < 1. Ciò deriva da

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)q^n}{1-q^n}=\sum _{n=1}^{\mathrm{\infty }}\phi (n)\sum _{r=1}^{\mathrm{\infty }}{q}^{rn}$

che è

$\sum _{k=1}^{\mathrm{\infty }}{q}^k\sum _{n|k}\phi (n)=\sum _{k=1}^{\mathrm{\infty }}k{q}^k=\frac{q}{(1-q{)}^2}.$

Disuguaglianze

Alcune disuguaglianze riguardanti la funzione $\phi$ sono:

$\phi (n)>\frac{n}{e^{\gamma }\log \log n+\frac{3}{\log \log n}}$ per n > 2, dove γ è la costante di Eulero-Mascheroni,

$\phi (n)\ge \sqrt{\frac{n}{2}}$ per n > 0,

e

$\phi (n)\ge \sqrt{n}\text{ per }n>6.$

Se n è composto abbiamo

$\phi (n)\le n-\sqrt{n}$

Per ogni numero pari 2n, dove 2n non è della forma 2^k, abbiamo

$\phi (2n)\le n-1$

Se invece 2n è pari e della forma 2^k, abbiamo

$\phi (2n)=n$

Per valori di n arbitrariamente grandi, si avrà

$\mathrm{lim\; inf}\frac{\phi (n)}{n}=0$ e $\mathrm{lim\; sup}\frac{\phi (n)}{n}=1.$

Un paio di disuguaglianze che combinano la funzione $\phi$ con la funzione $\sigma$ sono:

$\frac{6n^2}{{\pi }^2}<\phi (n)\sigma (n)<n^2\text{ per }n>1.$

Alcuni valori della funzione

$\phi (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

Bibliografia

• Luca Barbieri Viale, Teorema 4.27, Che cos'è un numero ? Raffaello Cortina, 2013, ISBN 978-88-6030-604-3
• 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 88-08-09154-6 - Capitolo II.4

Voci correlate

• Aritmetica modulare
• Interi coprimi
• Nontotiente
• Noncototiente
• Funzione aritmetica
• Teorema di Eulero (aritmetica modulare)
• Campo ciclotomico

Collegamenti esterni

• Template:Collegamenti esterni
• Template:Cita web
• Kirby Urner, Computing totient function in Python and scheme, (2003)
• Template:Cita web
• Miyata, Daisuke & Yamashita, Michinori, Derived logarithmic function of Euler's function
• Bordellès, Olivier, Numbers prime to q in $[1,n]$
• Plytage, Loomis, Polhill Summing Up The Euler Phi Function Template:Webarchive
• Fabrizio Romano, Template:Collegamento interrotto