La funzione di Eulero
associa a un numero intero n il numero dei numeri interi primi con n e minori di n
(compreso l'uno); è una funzione basilare della teoria dei numeri ed
interviene in molti teoremi come quello di Fermat-Eulero,
oltre ad essere uno degli ingredienti fondamentali del cifrario RSA.
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
Φ(n).
Si dimostra che
Φ(n) = n(1 - 1/n1)(1 - 1/n2)...(1 - 1/nm)
dove n1, n2 ... nm sono i fattori primi distinti
di n.
Se n è primo allora ovviamente Φ(n) = n - 1
Se n è il prodotto di due numeri primi p e q, è
facile verificare che Φ(n) = (p - 1)(q - 1).
Infatti Φ(n) = pq(1 - 1/p)(1 - 1/q) e
svolgendo i prodotti p(1 - 1/p) e q(1 - 1/q) si ottiene la formula data.
N.B. Su alcuni testi la funzione di Eulero di N è chiamata indicatore di N.
Esempio
Prendiamo n = 18 = 32x2, i fattori primi sono 2 e 3 e la funzione di
Eulero vale:
Φ(18) = 18(1 - 1/2)(1 - 1/3) = 18(1/2)(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 - 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 - 1/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.
