Funzione totiente di Eulero phi(n)

La funzione totiente di Eulero phi(n) (o Euler phi-function) conta gli interi positivi minori o uguali a n che sono coprimi a n (cioè gcd(k, n) = 1). Introdotta da Eulero nel 1763, e una delle funzioni fondamentali della teoria dei numeri.

Definizione

phi(n) = |{k : 1 <= k <= n, gcd(k, n) = 1}|. Esempi: phi(

• = 1 (solo k=1), phi(
• = 1, phi(
• = 2 (1, 2), phi(

6) = 2 (1, 5), phi(12) = 4 (1, 5, 7, 11). Per p primo: phi(p) = p - 1 (tutti gli interi 1..p-1 sono coprimi a p).

Formula via fattorizzazione

Se n = p_1^a_1 * p_2^a_2 * ... * p_k^a_k, allora:

phi(n) = n * prod_{i=1}^{k} (1 - 1/p_i)

Equivalentemente: phi(p^a) = p^(a-1) * (p - 1) per p primo. Esempi: phi(12) = 12 * (1 - 1/2)(1 - 1/3) = 12 * 1/2 * 2/3 = 4. phi(100) = 100 * (1/2)(4/5) = 40. phi(p) = p - 1.

Multiplicativita

phi e MULTIPLICATIVA: se gcd(m, n) = 1, allora phi(m * n) = phi(m) * phi(n). Esempio: phi(15) = phi(3) * phi(5) = 2 * 4 = 8 (verifica: 1, 2, 4, 7, 8, 11, 13, 14). Conseguenza: basta calcolare phi sui fattori primi.

Identità di Eulero

Sum_{d | n} phi(d) = n (somma su divisori d di n da n). Esempio per n = 12: divisori 1, 2, 3, 4, 6, 12. Sum phi = 1 + 1 + 2 + 2 + 2 + 4 = 12. Questa identità e la base del crivello di Mobius e della teoria dei caratteri di Dirichlet.

Teorema di Eulero (generalizzazione di Fermat)

Se gcd(a, n) = 1, allora a^phi(n) = 1 (mod n). Generalizzazione del piccolo teorema di Fermat (caso n primo: a^(p-1) = 1 mod p). Base teorica della crittografia RSA: chiave pubblica (e, n) con e coprimo a phi(n), chiave privata d con e * d = 1 (mod phi(n)).

Funzione sommatoria Phi(n)

Phi(n) = sum_{k=1}^{n} phi(k). Asintotica di Mertens (1874): Phi(n) ~ 3 n^2 / pi^2. Per n = 10^4: Phi = 30396356, asintotica = 30396355.09 (errore 0.000003%). La costante 6/pi^2 ~ 0.6079 e la densità asintotica delle coppie coprime: probabilità che due interi random siano coprimi.

Densità asintotica

(1/N) sum_{n 6/pi^2 quando N -> infty. Significa: in media, frazione di interi minori di n coprimi a n e ~ 6/pi^2 ~ 60.79%. phi(n)/n minimizza per n con tanti piccoli fattori primi (numeri primorial 2*3*5*7*11*...). Massimizza per n = primo (phi(p)/p = (p-1)/p -> 1).

Applicazioni

• Crittografia RSA: phi(n) = (p-1)(q-1) per n = pq prodotto di primi.
• Modulo aritmetico: ordine moltiplicativo di a mod n divide phi(n).
• Funzioni multiplicative: phi e prototipo, base per teoria di Dirichlet.
• Polinomi ciclotomici: grado di Phi_n(x) = phi(n).
• Combinatoria: contatore di permutazioni con punti fissi.
• Sistemi dinamici: indici di gruppi rotazionali.

Inverso di Euler

Per dato m, trovare tutti gli n con phi(n) = m. Difficile! Esempi: phi^{-1}(1) = {1, 2}, phi^{-1}(2) = {3, 4, 6}, phi^{-1}(4) = {5, 8, 10, 12}, phi^{-1}(6) = {7, 9, 14, 18}. Carmichael (1907) congettura: |phi^{-1}(m)| diverso da 1 per ogni m (no soluzione unica). Aperta. Ford (1998) dimostra |phi^{-1}(m)| illimitato.

Storia

Eulero introduce phi nel 1763 (nella Theorema Arithmeticum). Gauss in Disquisitiones Arithmeticae (1801) studia proprietà. Mertens (1874) dimostra asintotica Phi(n). Lehmer congettura: phi(n) divide n - 1 implica n primo. Erdos, Pomerance studiano valori medi. Ford (1998) risolve molte questioni inverse aperte.

Modalita del calcolatore

Cinque modalita: phi(n) esatta via fattorizzazione, tabella phi(k) per range, funzione sommatoria Phi(n) con confronto Mertens, valore medio phi(n)/n e densità asintotica, ricerca inverso phi^{-1}(m). Limite n <= 100000 per calcolo veloce.

Il gruppo moltiplicativo e le radici primitive

La funzione totiente ha un'interpretazione algebrica profonda: phi(n) e esattamente l'ordine del gruppo moltiplicativo degli interi modulo n, cioe il numero di classi di resto invertibili modulo n. Questo gruppo, indicato con (Z/nZ)*, raccoglie proprio gli interi coprimi con n, ed e la struttura su cui poggia tutta l'aritmetica modulare. La sua dimensione phi(n) determina il comportamento delle potenze modulo n.

Il gruppo e ciclico, cioe generato da un unico elemento detto radice primitiva, solo per valori speciali di n: 1, 2, 4, le potenze di un primo dispari p^k e i loro doppi 2p^k. In questi casi esiste un intero g le cui potenze percorrono tutti i phi(n) elementi invertibili prima di ripetersi. L'esistenza di radici primitive e cruciale in crittografia, per esempio nel protocollo di Diffie-Hellman e nella firma digitale DSA, dove la difficolta del logaritmo discreto garantisce la sicurezza.

Il ruolo di phi(n) nella crittografia RSA

La funzione totiente e il cuore matematico del sistema crittografico RSA. Scelti due grandi primi p e q, si pone n = pq e si calcola phi(n) = (p-1)(q-1) sfruttando la multiplicativita. Le chiavi si costruiscono scegliendo un esponente pubblico e coprimo con phi(n) e calcolandone l'inverso d modulo phi(n), cioe l'intero d tale che e*d sia congruo a 1 modulo phi(n). Il teorema di Eulero garantisce allora che elevare un messaggio alla e e poi alla d lo riporta al valore originale.

La sicurezza di RSA dipende interamente dal fatto che, pur essendo n pubblico, calcolare phi(n) senza conoscere la fattorizzazione p, q e computazionalmente proibitivo: richiederebbe di fattorizzare n, problema ritenuto intrattabile per numeri di centinaia di cifre. Chi conosce p e q calcola phi(n) istantaneamente e puo generare la chiave privata; chi non li conosce resta bloccato. E l'esempio piu celebre di come una funzione della teoria dei numeri del Settecento sostenga la sicurezza digitale moderna.

Aggiornato a luglio 2026