La funzione di Eulero
La funzione di Eulero φ(n) di un numero intero n>0 conta quanti numeri interi compresi tra \(1\) e \(n\) sono coprimi con \(n\).
La funzione di Eulero \( \phi(n) \) è nota anche come "indicatrice di Eulero" o "toziente di Eulero"-
In pratica, la funzione di Eulero φ(n) mi permette di sapere quanti i numeri coprimi di un numero n. Ma soltanto il sottoinsieme dei numeri coprimi inferiori di n.
Non mi dice quali sono i numeri coprimi di $ n $ ma solo "quanti sono".
Cosa sono i numeri coprimi? Due numeri sono coprimi (o relativamente primi) se non hanno fattori primi in comune, cioè quei numeri che hanno come massimo comun divisore con \(n\) il valore \(1\). Ad esempio, i numeri 10 e 9 sono coprimi perché le loro scomposizioni 10=5·2 e 9=32 non hanno alcun fattore primo in comune.
Un esempio pratico
La funzione di Eulero del numero n=20 è
$$ φ(20) = 8 $$
Perché?
I numeri minori di n relativamente primi ( coprimi ) con n sono
$$ 1,3,7,9,11,13,17,19 $$
Nota. Il massimo comune divisore tra n e uno di questi numeri è sempre uguale a 1. Per questa proprietà sono detti coprimi ( o relativamente primi ) con n.
Complessivamente sono 8 numeri.
Questo spiega il risultato della funzione di Eulero φ(20) = 8.
Come si calcola la funzione di Eulero
Il calcolo di \( \phi(n) \) dipende dalla fattorizzazione di \(n\) nei suoi fattori primi.
Ecco come si calcola:
- Fattorizzo il numero \(n\) nei suoi fattori primi
Scrivo \(n\) come il prodotto di potenze di numeri primi distinti: $$ n = p_1^{e_1} \cdot p_2^{e_2} \cdot \cdots \cdot p_k^{e_k} $$ dove \(p_1, p_2, \dots, p_k\) sono i primi distinti e \(e_1, e_2, \dots, e_k\) sono le loro potenze. - Applico la formula della funzione di Eulero
La formula generale per calcolare \( \phi(n) \) è: $$ \phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \cdots \cdot \left(1 - \frac{1}{p_k}\right) $$ dove \(p_1, p_2, \dots, p_k\) sono i fattori primi di \(n\).
Nota. Se \(n\) è il prodotto di due numeri primi distinti \(p\) e \(q\), posso semplificare la formula generale in $$ \varphi(n) = (p - 1) \cdot (q - 1) $$ Il risultato finale è lo stesso.
Esempio
Devo calcolare il valore della funzione di Eulero \( \phi(12) \)
Trovo i fattori primi del numero $ n = 12 $
$$ 12 = 2^2 \cdot 3 $$
Poi applico la formula
$$ \phi(12) = 12 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) $$
$$ \phi(12) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} $$
$$ \phi(12) = 12 \cdot \frac{1}{3} $$
$$ \phi(12) = 4 $$
Quindi, \( \phi(12) = 4 \). In altre parole, il numero $ n=12 $ ha 4 numeri coprimi tra 1 e 12.
Verifica. I numeri coprimi con 12 compresi tra 1 e 12 sono i seguenti: $$ 1, 5, 7, 11 $$ Sono effettivamente 4 numeri.
In questo caso non posso usare la formula semplificata $ \varphi(n) = (p - 1) \cdot (q - 1) $ perché il numero è il prodotto di tre numeri primi non tutti distinti $ 12 = 2 \cdot 2 \cdot 3 $
Esempio 2
Provo a calcolare il valore della funzione di Eulero \( \phi(22) \)
Trovo i fattori primi del numero $ n = 22 $ che sono $ p =2 $ e $ q=11 $.
In questo caso sono due numeri primi distinti, quindi posso usare la formula di Eulero semplificata.
$$ \varphi(n) = (p - 1) \cdot (q - 1) $$
$$ \varphi(22) = (2 - 1) \cdot (11 - 1) $$
$$ \varphi(22) = 1 \cdot 10 $$
$$ \varphi(22) = 10 $$
Complessivamente, ci sono dieci numeri relativamente primi con 22 tra 1 e 22.
Verifica. I numeri coprimi con 22 compresi tra 1 e 22 sono i seguenti: $$ 1, 3, 5, 7, 9, 13, 15, 17, 19, 21 $$ Sono effettivamente 10 numeri.
Le proprietà della funzione di Eulero
Una proprietà particolarmente importante è la proprietà moltiplicativa che mi permette la fattorizzazione in numeri relativamente primi.
Se due numeri k,j sono relativamente primi $$ MCD(k,j)=1 $$ allora $$ φ(k \cdot j) = φ(k) \cdot φ(j) $$
Se i fattori del numero n sono più di due, devono comunque essere tutti relativamente primi tra loro presi a coppia di due.
Esempio
Riprendo la funzione di Eulero precedente
$$ φ(20) = 8 $$
Il numero n=20 può essere scomposto in fattori primi 22·5
$$ φ(20) = φ(2^2·5) = φ(2^2)·φ(5) = φ(4)·φ(5) = 2·4 = 8 $$
Il risultato finale è lo stesso
Nota. La funzione φ(4)=2 perché i numeri minori di 4 e relativamente primi con 4 sono 1,3 ossia due. La funzione φ(5)=4 perché i numeri minori di 5 e relativamente primi con 5 sono 1,2,3,4 ossia quattro.
La fattorizzazione permette di sfruttare un'altra proprietà utile per calcolare il valore della funzione di Eulero
Se il numero intero p è un numero primo, allora la funzione di Eulero φ(p) è $$ φ(p^x) = p^x - p^{x-1} $$
In questo modo posso calcolare il risultato della funzione di Eulero calcolando le potenze dei numeri primi.
Esempio
Scompongo in fattori primi il numero n=20
$$ φ(20) = φ(2^2·5) = φ(2^2)·φ(5) $$
Ho scomposto la funzione φ(20) nel prodotto di due funzioni φ(22)·φ(5)
I numeri 2 e 5 sono numeri primi.
Posso applicare il teorema precedente per calcolare le rispettive funzioni di Eulero
$$ φ(2^2) = 2^2-2 = 4-2 = 2 $$
$$ ·φ(5) = 5^1-5^0 = 5 - 1 = 4 $$
Pertanto
$$ φ(2^2)·φ(5) = 2 \cdot 4 = 8 $$
Nota. Il calcolo è decisamente più rapido e più facile. In particolar modo, quando si lavora con numeri primi molto grandi diventa difficoltoso elencare tutti i numeri relativamente primi inferiori al numero. Il ricorso alle potenze semplifica il lavoro.
Il teorema di Eulero
La funzione di Eulero mi permette di applicare il piccolo teorema di Fermat anche al modulo di un numero non primo.
Nota. Secondo il teorema del piccolo teorema di Fermat se a p un numero primo e l'intero a non è un multiplo di p, allora $$ a^{p-1} \equiv 1 \mod p $$ E' un teorema molto utile. Tuttavia, si può usare soltanto con i numeri primi p. E questo è un limite.
Sostituendo p con la funzione di Eulero φ(n) ottengo il Teorema di Eulero
Dati due numeri interi relativamente primi a e n, il numero intero a elevato alla funzione di Eulero φ(n) è congruente a 1 modulo n. $$ a^{φ(n)} \equiv 1 \mod n $$
che posso usare con qualsiasi numero intero positivo (n).
Esempio
Prendo come esempio il numero intero n=20. Non è un numero primo.
E lo applico al numero intero a=3. I due numeri sono coprimi.
$$ 3^{φ(20)} \equiv 1 \mod 20 $$
Ora sostituisco il risultato della funzione di Eurelo ossia φ(20)=8.
$$ 3^8 \equiv 1 \mod 20 $$
$$ 6561 \equiv 1 \mod 20 $$
$$ 1 \equiv 1 \mod 20 $$
Nota. La divisione 6561 diviso 20 ha resto 1.
Note a margine
Alcune osservazioni e note a margine sulla funzione di Eulero.
- Quali sono i numeri coprimi di un numero?
La funzione di Eulero \( \phi(n) \) mi dice "quanti" numeri sono coprimi con \(n\), ma non mi dice "quali" siano esattamente. Tuttavia, posso determinare quali numeri sono coprimi con un dato \(n\) analizzando il Massimo Comune Divisore (MCD) tra $ n $ e ciascun numero intero da \(1\) a \(n-1\). Se il MCD è uguale a \(1\), allora i numeri sono coprimi.Esempio: Voglio trovare i numeri coprimi con \(n = 10\). I numeri da \(1\) a \(9\) sono: \(1, 2, 3, 4, 5, 6, 7, 8, 9\). Ora verifico se il MCD di ciascuno con \(10\) è uguale a \(1\):
- \( \gcd(1, 10) = 1 \) → 1 è coprimo con 10.
- \( \gcd(2, 10) = 2 \) → 2 non è coprimo con 10.
- \( \gcd(3, 10) = 1 \) → 3 è coprimo con 10.
- \( \gcd(4, 10) = 2 \) → 4 non è coprimo con 10.
- \( \gcd(5, 10) = 5 \) → 5 non è coprimo con 10.
- \( \gcd(6, 10) = 2 \) → 6 non è coprimo con 10.
- \( \gcd(7, 10) = 1 \) → 7 è coprimo con 10.
- \( \gcd(8, 10) = 2 \) → 8 non è coprimo con 10.
- \( \gcd(9, 10) = 1 \) → 9 è coprimo con 10.
Quindi, i numeri coprimi con \(10\) sono: \(1, 3, 7, 9\).
E così via.
