Funzione φ di Eulero

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

• 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]}

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