Funzione φ di Eulero

In matematica, la funzione φ di Eulero o semplicemente funzione di Eulero o toziente, è una funzione definita, per ogni intero positivo ${\displaystyle n}$, come il numero degli interi compresi tra ${\displaystyle 1}$ e ${\displaystyle n}$ che sono coprimi con ${\displaystyle n}$. Ad esempio, ${\displaystyle \varphi (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.

Disambiguazione – "Funzione di Eulero" rimanda qui. Se stai cercando altri significati, vedi Eulero (disambigua).

I primi mille valori di ${\displaystyle \varphi }$

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

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

Moltiplicatività

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

${\displaystyle \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 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 ${\displaystyle y\in \mathbb {Z} _{a}}$ e ${\displaystyle z\in \mathbb {Z} _{b}}$ corrisponde a uno e un solo elemento ${\displaystyle w\in \mathbb {Z} _{ab}}$ (o, per essere più formali, che esiste un isomorfismo tra gli anelli ${\displaystyle \mathbb {Z} _{a}\times \mathbb {Z} _{b}}$ e ${\displaystyle \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 ${\displaystyle \varphi (a)}$ e i secondi ${\displaystyle \varphi (b)}$, e quindi in definitiva ci sono ${\displaystyle \varphi (a)\varphi (b)}$ elementi coprimi con ab che è per definizione il valore ${\displaystyle \varphi (ab)}$

Calcolo della funzione

Un'espressione per la funzione è la seguente:

${\displaystyle \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]=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}$

dove i ${\displaystyle p_{i}}$ sono tutti i primi che compongono la fattorizzazione di n.

Dimostrazione

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

Per fare ciò, troviamo tutti i numeri m minori o uguali a ${\displaystyle p^{k}}$ per i quali ${\displaystyle MCD(p^{k},m)\neq \ 1}$. Ciò equivale a dire che m deve avere dei fattori in comune con ${\displaystyle 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 ${\displaystyle p,2p,3p,\ldots ,p^{k-1}\cdot p}$. Questi numeri sono ${\displaystyle p^{k-1}}$, e sono tutti i numeri che non sono coprimi con ${\displaystyle p^{k}}$. Tutti i numeri minori o uguali a ${\displaystyle p^{k}}$ sono ${\displaystyle p^{k}}$, quindi i numeri primi con ${\displaystyle p^{k}}$ minori di ${\displaystyle p^{k}}$ sono i restanti ${\displaystyle p^{k}-p^{k-1}}$.

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

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

${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\ldots p_{r}^{k_{r}}}$

dove i ${\displaystyle p_{i}}$ sono numeri primi distinti, e ogni ${\displaystyle k_{i}>0}$

Quindi ${\displaystyle \varphi (n)=\varphi (p_{1}^{k_{1}}p_{2}^{k_{2}}\ldots p_{r}^{k_{r}})}$

Ora, poiché ${\displaystyle \varphi }$ è moltiplicativa possiamo espandere la funzione:

${\displaystyle \varphi (n)=\varphi (p_{1}^{k_{1}})\varphi (p_{2}^{k_{2}})\ldots \varphi (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 ${\displaystyle p_{i}}$ sono tutti primi, e quindi primi tra loro)

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

${\displaystyle \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]=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}$

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 ${\displaystyle \varphi (n)/n}$ è minore di qualunque ${\displaystyle \epsilon }$ per qualche valore di n): estendendo infatti il prodotto a tutti i primi, si ottiene

${\displaystyle {\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

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

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

${\displaystyle {\frac {\varphi (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:

${\displaystyle \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):

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

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

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

${\displaystyle \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

${\displaystyle \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 ${\displaystyle n<10^{10}}$ tale che

${\displaystyle \varphi (n)=\varphi (n+1)=\varphi (n+2)}$

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

${\displaystyle \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 φ  :

${\displaystyle \varphi (583200)=\varphi (583230)=\varphi (583260)=\,}$

${\displaystyle \varphi (583290)=\varphi (583320)=\varphi (583350)=\,}$

${\displaystyle =155520=2^{7}\cdot 3^{5}\cdot 5}$

• ${\displaystyle a\mid b}$ implica ${\displaystyle \varphi (a)\mid \varphi (b)}$
• ${\displaystyle \varphi (n)}$ è pari per ${\displaystyle n\geq 3}$. Inoltre, se n ha r fattori primi distinti dispari, allora ${\displaystyle 2^{r}\mid \varphi (n)}$

Funzione generatrice

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

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

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

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

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

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

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

${\displaystyle \sum _{h=1}^{\infty }\left(\sum _{fg=h}\varphi (g)\right){\frac {1}{h^{s}}}=\sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}}$

${\displaystyle \sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}=}$${\displaystyle \sum _{h=1}^{\infty }{\frac {h}{h^{s}}}}$

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

La funzione generatrice di una serie di Lambert è

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

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

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

che è

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

Disuguaglianze

Alcune disuguaglianze riguardanti la funzione ${\displaystyle \varphi }$ sono:

${\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}}$ per n > 2, dove γ è la costante di Eulero-Mascheroni,^[1][2]

${\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}}$ per n > 0,

e

${\displaystyle \varphi (n)\geq {\sqrt {n}}{\text{ per }}n>6.}$

Se n è composto abbiamo

${\displaystyle \varphi (n)\leq n-{\sqrt {n}}}$

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

${\displaystyle \varphi (2n)\leq n-1}$

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

${\displaystyle \varphi (2n)=n}$

Per valori di n arbitrariamente grandi, si avrà

${\displaystyle \liminf {\frac {\varphi (n)}{n}}=0}$ e ${\displaystyle \limsup {\frac {\varphi (n)}{n}}=1.}$

Un paio di disuguaglianze che combinano la funzione ${\displaystyle \varphi }$ con la funzione ${\displaystyle \sigma }$ sono:

${\displaystyle {\frac {6n^{2}}{\pi ^{2}}}<\varphi (n)\sigma (n)<n^{2}{\mbox{ per }}n>1.}$

Alcuni valori della funzione

${\displaystyle \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