Per esempio per $n = 6$ la funzione di Eulero vale $2$ perché gli interi primi con $6$ e minori di $6$ sono solo $1$ e $5$; per $n = 7$ la funzione vale $6$ perché essendo $7$ primo tutti i numeri che lo precedono sono primi con $7$.
La funzione di Eulero di un numero $n$ si indica di solito con $ \Phi(n) $. Da quanto detto sopra, segue immediatamente che per $n$ primo $ \Phi(n) = n - 1$
$ \Phi(n) = n \times \left( 1 - \frac{1}{n_1} \right) \left(1 - \frac{1}{n_2} \right) ... \left( 1 - \frac{1}{n_m} \right) $
dove $n_1, n_2 ... n_m$ sono i fattori primi distinti di $n$.
Se $n$ è il prodotto di due numeri primi p e q, è facile verificare che $ \Phi(n) = (p - 1)(q - 1)$.
Infatti $ \Phi(n) = pq \left(1 - \frac{1}{p} \right) \left(1 - \frac{1}{q} \right)$ e poiché $p \left(1 - \frac{1}{p} \right) = (p-1)$ e $q \left(1 - \frac{1}{q} \right) = (q-1)$ si ottiene la formula data.
In un'aritmetica modulare di ordine $N$ il valore di $\Phi(N)$ dà anche il numero di elementi che ammettono elemento inverso.
N.B. Su alcuni testi la funzione di Eulero è chiamata Indicatore.
Esempio
Prendiamo $n = 18 = 3^2 \times 2$, i fattori primi sono 2 e 3 e la funzione di
Eulero vale:
$ \Phi(18) = 18(1 - \frac{1}{2})(1 - \frac{1}{3}) = 18 \times \frac{1}{2} \times \frac{2}{3} = 6 $
ed effettivamente sono 6 i numeri primi con 18:
$1, 5, 7, 11, 13, 17$
Questo esempio ci permette anche di giustificare la formula, come una sorta di setaccio: all'inizio i numeri in gioco sono tutti e 18 (da 1 a 18); poi essendo 18 multiplo del due si escludono tutti i numeri pari, che sono la metà del totale e ne restano 9, come dalla prima parte della formula $18(1 - \frac{1}{2})$
$1,3,5,7,9,11,13,15,17$
A questo punto essendo anche 3 un fattore primo di 18, si escludono tutti i multipli del tre che sono un terzo del totale; ne restano i due terzi, appunto $(1 - \frac{2}{3})$, dei nove rimasti ovvero i sei già visti:
1,5,7,11,13,17
È evidente che il procedimento resta valido per qualsiasi numero e per qualsiasi numero di fattori e questo giustifica la formula di sopra.
Riferimenti bibliografici
X
Funzione di Eulero calcolata usando la formula $\Phi(N) = N \times \left (1-\frac{1}{n_1} \right) \times \left (1-\frac{1}{n_2} \right) \dots $.
X
Funzione di Eulero calcolata contando i numeri minori di $N$ e primi con $N$.
X
Sono ammessi solo numeri compresi tra 2 e 6. Numeri fuori di questo intervallo saranno forzati.