La funzione di Eulero

Funzione di Eulero di
*

Fattori primi: 2 3
$\Phi(6)= 2$ *
$\Phi(6)= 2$ *
Numeri primi con 6
Ord	primo	reciproco (mod 6)
1°	$1$	$1$
2°	$5$	$5$

La funzione di Eulero associa a un numero intero positivo

$n$ il numero dei numeri interi primi con

$n$ e minori di

$n$ (compreso l'uno); detto altrimenti i

$p$ tali che

$MCD(n, p)=1$ ; si tratta di una funzione basilare della teoria dei numeri, che 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)$ . 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

La Crittografia da Atbash a RSA by Paolo Bonavoglia is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Based on a work at http://www.crittologia.eu/.
(In altri termini: Testi e figure possono essere riprodotti liberamente per usi non commerciali, a condizione che venga citata esplicitamente la fonte con un link e il nome dell'autore.)

Questo sito non fa uso di cookies propri. Possono peraltro essere presenti cookies di terze parti.

Pagina a cura di Paolo Bonavoglia (paolo@bonavoglia.eu) del

Spazio web di Paolo Bonavoglia: Scrivetemi via E-Mail; Glossario
Bibliografia: Bibliografia

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.