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.

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}$

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)}$

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.

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)}$

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.

• 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)}$

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}}}.}$

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.}$

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

• 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

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

• Wikimedia Commons contiene immagini o altri file sulla funzione φ di Eulero

• Eulero, funzione toziente di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Euler phi function, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Totient Function, su MathWorld, Wolfram Research.
• (EN) Euler function, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Euler Totient Function, su functions.wolfram.com.
• Kirby Urner, Computing totient function in Python and scheme, (2003)
• JavaScript totient calculator, su www25.brinkster.com. URL consultato il 14 gennaio 2011 (archiviato dall'url originale il 15 giugno 2011).
• Miyata, Daisuke & Yamashita, Michinori, Derived logarithmic function of Euler's function
• Bordellès, Olivier, Numbers prime to q in ${\displaystyle [1,n]}$
• Plytage, Loomis, Polhill Summing Up The Euler Phi Function Archiviato il 23 luglio 2011 in Internet Archive.
• Fabrizio Romano, Python implementation^{[collegamento interrotto]}

V · D · M Funzione totiente
Funzione totiente di Eulero ${\displaystyle \phi (n)}$ · Funzioni totiente di Jordan ${\displaystyle J_{k}(n)}$ · Nontotiente · Noncototiente · Numero altamente totiente · Numero scarsamente totiente · Numero altamente cototiente · Numero perfetto totiente

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri