Funzione φ di Eulero

In matematica, la funzione φ  di Eulero o semplicemente funzione di Eulero o toziente, è una funzione definita, per ogni intero positivo , come il numero degli interi compresi tra  e  che sono coprimi con . Ad esempio,   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  è una funzione molto importante nella teoria dei numeri, principalmente perché è la cardinalità del gruppo moltiplicativo degli interi di modulo , più precisamente è l'ordine del gruppo moltiplicativo dell'anello  (vedere aritmetica modulare). Questo fatto, unito con il teorema di Lagrange, dimostra il teorema di Eulero: se  è un numero coprimo con , allora:

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

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  e  corrisponde a uno e un solo elemento  (o, per essere più formali, che esiste un isomorfismo tra gli anelli  e ). 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  e i secondi , e quindi in definitiva ci sono  elementi coprimi con ab che è per definizione il valore

Calcolo della funzione 
Un'espressione per la funzione è la seguente:

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

Dimostrazione
Mostriamo innanzitutto che, se p è un numero primo, allora  per ogni .

Per fare ciò, troviamo tutti i numeri m minori o uguali a  per i quali . Ciò equivale a dire che m deve avere dei fattori in comune con .
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 .
Questi numeri sono , e sono tutti i numeri che non sono coprimi con . Tutti i numeri minori o uguali a  sono , quindi i numeri primi con  minori di  sono i restanti .

Quindi 

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

 

dove i  sono numeri primi distinti, e ogni 

Quindi 

Ora, poiché  è moltiplicativa possiamo espandere la funzione:

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

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

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  è minore di qualunque  per qualche valore di n): estendendo infatti il prodotto a tutti i primi, si ottiene

Quella tra parentesi è la scrittura del prodotto di Eulero della funzione zeta di Riemann per s=1, cioè la somma

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

diventa arbitrariamente vicina a 0.

Altre proprietà 
Il numero φ(n) è anche pari al numero di generatori del gruppo ciclico Cn. Da ciascun elemento di Cn si può generare un sottogruppo ciclico Cd 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 ottenere un'altra formula per la φ(n):

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

Abbiamo inoltre che, se n è un numero primo:

Dato che, ovviamente, ogni numero minore di n gli è coprimo, essendo n primo.

Esiste una sequenza di valori di n tale che

i primi sono 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (sequenza A001274 dell'OEIS).

Esiste un solo numero  tale che

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

Esiste una progressione aritmetica di ragione 30 composta da sei numeri, che generano tutti lo stesso valore di φ  :

 implica 
 è pari per . Inoltre, se n ha r fattori primi distinti dispari, allora

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

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

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

La funzione generatrice di una serie di Lambert è

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

che è

Disuguaglianze
Alcune disuguaglianze riguardanti la funzione  sono:

 per n > 2, dove γ è la costante di Eulero-Mascheroni,

 per n > 0,

e

Se n è composto abbiamo

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

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

Per valori di n arbitrariamente grandi, si avrà

 e 

Un paio di disuguaglianze che combinano la funzione  con la funzione  sono:

Alcuni valori della funzione

Note

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

Altri progetti

Collegamenti esterni 
 

Kirby Urner, Computing totient function in Python and scheme, (2003)

Miyata, Daisuke & Yamashita, Michinori, Derived logarithmic function of Euler's function
 Bordellès, Olivier, Numbers prime to q in 
Plytage, Loomis, Polhill Summing Up The Euler Phi Function 
 Fabrizio Romano, 

Aritmetica modulare
Eulero