Ultimo aggiornamento: 2026-07-13

Definizione

La funzione toziente di Eulero $\varphi(n)$ conta quanti interi da $1$ a $n$ sono coprimi con $n$, cioè quanti non hanno alcun fattore in comune con $n$ oltre a $1$. Due interi sono coprimi quando il loro massimo comune divisore è $1$.

Per esempio, $\varphi(9) = 6$: tra $1, 2, \dots, 9$, i valori $1, 2, 4, 5, 7, 8$ sono coprimi con $9$, mentre $3, 6, 9$ non lo sono.

La funzione prende il nome da Leonhard Euler, che la introdusse nel 1763. Si scrive anche $\phi(n)$ ed è detta funzione phi.

La formula del prodotto

Non serve affatto provare ogni intero fino a $n$. Una volta scomposto $n$ nei suoi fattori primi distinti, il toziente segue subito:

$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

Il prodotto è esteso ai primi distinti che dividono $n$: gli esponenti non compaiono. Ogni primo $p$ toglie la frazione $1/p$ dei numeri (quelli divisibili per $p$), e poiché i primi agiscono in modo indipendente, le frazioni si moltiplicano.

Esempio svolto — n = 36. La fattorizzazione è $36 = 2^2 \cdot 3^2$, quindi i primi distinti sono $2$ e $3$:

$\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

I dodici interi coprimi con $36$ sono $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$.

Primi e potenze di primi

Due casi fondamentali rendono la formula facile da comprendere:

• Primo $p$: ogni intero da $1$ a $p - 1$ è coprimo con $p$, quindi $\varphi(p) = p - 1$. Per esempio $\varphi(7) = 6$.
• Potenza di primo $p^k$: gli unici interi non coprimi con $p^k$ sono i multipli di $p$, che sono $p^{k-1}$. Perciò

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$

Così $\varphi(8) = \varphi(2^3) = 2^2(2 - 1) = 4$ e $\varphi(27) = \varphi(3^3) = 3^2(3 - 1) = 18$.

Moltiplicatività

Il toziente è moltiplicativo: ogni volta che $m$ e $n$ sono coprimi,

$\varphi(mn) = \varphi(m)\,\varphi(n)$

È per questo che la formula del prodotto funziona: si scrive $n$ come prodotto di potenze di primi, si applica $\varphi(p^k) = p^{k-1}(p-1)$ a ciascuna e si moltiplica. Per esempio, $36 = 4 \cdot 9$ con $\gcd(4, 9) = 1$, quindi $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$.

Attenzione alla condizione di coprimalità: $\varphi(mn) = \varphi(m)\varphi(n)$ può non valere quando $m$ e $n$ condividono un fattore. Per esempio $\varphi(2 \cdot 2) = \varphi(4) = 2$, non $\varphi(2)\varphi(2) = 1$.

Il teorema di Eulero

Il toziente governa l'elevamento a potenza modulare. Il teorema di Eulero afferma che se $\gcd(a, n) = 1$, allora

$a^{\varphi(n)} \equiv 1 \pmod{n}$

Ciò generalizza il piccolo teorema di Fermat ($a^{p-1} \equiv 1 \pmod p$ per un primo $p$), che è semplicemente il caso particolare $n = p$, dove $\varphi(p) = p - 1$.

Esempio. Prendi $a = 3$, $n = 10$. Qui $\varphi(10) = 4$, quindi $3^4 = 81 \equiv 1 \pmod{10}$, e in effetti $81$ termina con $1$. Il teorema permette di ridurre esponenti enormi modulo $\varphi(n)$ prima di calcolare.

Applicazione a RSA

La crittografia a chiave pubblica RSA è costruita direttamente sul toziente. Un modulo si forma da due grandi primi, $n = p \cdot q$, dando

$\varphi(n) = (p - 1)(q - 1)$

L'esponente pubblico $e$ e quello privato $d$ sono scelti in modo che $e \cdot d \equiv 1 \pmod{\varphi(n)}$. Il teorema di Eulero garantisce allora che decifrare inverte cifrare: $(m^e)^d \equiv m \pmod n$.

La sicurezza poggia su un divario: chiunque può pubblicare $n$, ma calcolare $\varphi(n) = (p-1)(q-1)$ richiede di conoscere $p$ e $q$. Recuperarli dal solo $n$ significa fattorizzare un grande semiprimo, cosa ritenuta computazionalmente impraticabile per primi abbastanza grandi. Di fatto, conoscere $\varphi(n)$ equivale a fattorizzare $n$.

Esempi svolti

$n$	Fattorizzazione	Forma prodotto	$\varphi(n)$
$10$	$2 \cdot 5$	$10\,(1 - \tfrac12)(1 - \tfrac15)$	$4$
$12$	$2^2 \cdot 3$	$12\,(1 - \tfrac12)(1 - \tfrac13)$	$4$
$36$	$2^2 \cdot 3^2$	$36\,(1 - \tfrac12)(1 - \tfrac13)$	$12$
$100$	$2^2 \cdot 5^2$	$100\,(1 - \tfrac12)(1 - \tfrac15)$	$40$
$101$	$101$ (primo)	$101\,(1 - \tfrac{1}{101})$	$100$

Casi particolari

• $n = 1$: per convenzione $\varphi(1) = 1$. L'unico intero dell'intervallo, $1$, è coprimo con se stesso.
• $n$ primo: $\varphi(n) = n - 1$, il massimo possibile per quella dimensione: i primi hanno il maggior numero di resti coprimi.
• $n$ pari: il fattore $(1 - \tfrac12)$ toglie almeno metà degli interi, quindi $\varphi(n) \le n/2$.
• Somma sui divisori: i tozienti di tutti i divisori di $n$ sommano a $n$: $\sum_{d \mid n} \varphi(d) = n$. Per $n = 12$: $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$.

Riferimento rapido

Concetto	Formula
Definizione	$\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}$
Formula del prodotto	$\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$
Primo	$\varphi(p) = p - 1$
Potenza di primo	$\varphi(p^k) = p^{k-1}(p - 1)$
Moltiplicativa	$\varphi(mn) = \varphi(m)\varphi(n)$ se $\gcd(m, n) = 1$
Teorema di Eulero	$a^{\varphi(n)} \equiv 1 \pmod n$ se $\gcd(a, n) = 1$
Somma dei divisori	$\sum_{d \mid n} \varphi(d) = n$

Domande frequenti (FAQ)

Che cos’è la funzione toziente di Eulero?

La funzione toziente di Eulero φ(n) conta gli interi positivi fino a n che sono coprimi con n, cioè quelli che non hanno alcun fattore in comune con n oltre a 1. Per esempio, φ(9) = 6, perché 1, 2, 4, 5, 7 e 8 sono coprimi con 9, mentre 3, 6 e 9 non lo sono. Per convenzione φ(1) = 1.

Come si calcola φ(n)?

Fattorizza n nei suoi primi distinti p₁, p₂, …, pₖ e applica φ(n) = n · ∏(1 − 1/p) su quei primi. Per n = 36 = 2² · 3², φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · 1/2 · 2/3 = 12. Contano solo i primi distinti, non i loro esponenti.

Qual è il toziente di un numero primo?

Per un primo p, ogni intero da 1 a p − 1 è coprimo con p, quindi φ(p) = p − 1. Per una potenza di primo pᵏ la formula dà φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1). Per esempio φ(7) = 6 e φ(8) = φ(2³) = 8 − 4 = 4.

Perché il toziente è importante in RSA e nel teorema di Eulero?

Il teorema di Eulero afferma che se MCD(a, n) = 1, allora a^φ(n) ≡ 1 (mod n), una generalizzazione del piccolo teorema di Fermat. RSA vi si basa: per un modulo n = p·q di due primi, φ(n) = (p − 1)(q − 1), e gli esponenti pubblico e privato sono scelti in modo che e·d ≡ 1 (mod φ(n)). Conoscere φ(n) equivale a fattorizzare n, ed è ciò che rende RSA sicuro.