Teoria dei numeri - Aritmetiche finite
La funzione di Eulero
Il cifrario RSA - Il gruppo moltiplicativo

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 $ \Phi(n) $.

Si dimostra che

$ \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 è primo allora ovviamente $ \Phi(n) = n - 1$.

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.

N.B. Su alcuni testi la funzione di Eulero di N è chiamata indicatore di N.


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.


Valido HTML 4.01!
Riferimenti bibliografici