La funzione φ di Eulero spiegata

Scrivi i numeri da 1 a 10 e cancella ognuno che ha un fattore in comune con 10. Ne restano quattro: 1, 3, 7 e 9. Questo conteggio, φ(10) = 4, è la funzione φ di Eulero, una delle funzioni più usate della teoria dei numeri, dalle frazioni e dagli orologi fino alla crittografia che protegge i pagamenti online.

I numeri da 1 a 30 in una griglia con pieni gli otto coprimi con 30, la formula φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 e un grafico di φ(k) con i primi su una retta
I numeri da 1 a 30 in una griglia con pieni gli otto coprimi con 30, la formula φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 e un grafico di φ(k) con i primi su una retta

Contare i numeri coprimi

Due numeri sono coprimi quando il loro massimo comune divisore è 1. φ(n) conta i k da 1 a n con MCD(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 e φ(1) = 1. Lo stesso conteggio compare in molti posti. È il numero di frazioni k/n tra 0 e 1 già ridotte ai minimi termini, il numero di passi che portano una lancetta su ogni ora di un orologio con n ore e il numero di k che hanno un inverso modulo n, così che k × x ≡ 1 (mod n) si possa risolvere.

La formula del prodotto

Se i primi che dividono n sono p₁, p₂ …, allora φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Il motivo è un crivello. Metà di tutti i numeri sono pari, quindi togliere i multipli di 2 lascia la frazione 1 − 1/2; dei numeri rimasti, uno su tre è multiplo di 3, e così via. Per il teorema cinese del resto le condizioni per primi diversi sono indipendenti, quindi le frazioni si moltiplicano semplicemente. Per 100 = 2² × 5² si ottiene 100 × 1/2 × 4/5 = 40. Due proprietà danno lo stesso risultato in un'altra forma: φ(p^k) = p^(k−1)(p − 1) e φ(mn) = φ(m) φ(n) quando m e n sono coprimi, quindi φ(100) = φ(4) × φ(25) = 2 × 20 = 40.

Il teorema di Eulero

Fermat notò nel 1640 che a^(p−1) ≡ 1 (mod p) per un primo p e ogni a non divisibile per p. Eulero dimostrò la versione generale, pubblicata nel 1763: a^φ(n) ≡ 1 (mod n) ogni volta che MCD(a, n) = 1. La dimostrazione è breve. Moltiplica per a i φ(n) numeri coprimi con n; i prodotti sono ancora coprimi con n e tutti diversi modulo n, quindi sono gli stessi numeri in un altro ordine, e confrontando i due prodotti resta a^φ(n) ≡ 1. Il più piccolo esponente che funziona per un dato a è il suo ordine, che divide sempre φ(n); il più piccolo che funziona per tutti gli a insieme è la funzione di Carmichael λ(n). Per 561 = 3 × 11 × 17, λ(561) = 80 divide 560, quindi a^560 ≡ 1 (mod 561) per ogni a coprimo con 561, anche se 561 non è primo. È il più piccolo numero di Carmichael, e il motivo per cui il test di Fermat da solo non può dimostrare che un numero è primo.

Leonhard Euler, in un ritratto di Jakob Emanuel Handmann. Nel 1763 pubblicò la forma generale dell’osservazione di Fermat: a^φ(n) ≡ 1 (mod n) quando a e n sono coprimi.
Leonhard Euler, in un ritratto di Jakob Emanuel Handmann. Nel 1763 pubblicò la forma generale dell’osservazione di Fermat: a^φ(n) ≡ 1 (mod n) quando a e n sono coprimi.

La somma sui divisori di Gauss e la media

Somma φ(d) sui divisori d di n e ottieni sempre di nuovo n: per 12, φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss lo dimostrò nelle sue Disquisitiones Arithmeticae del 1801; lo si vede riducendo ai minimi termini le frazioni 1/12, 2/12 … 12/12 e ordinandole per denominatore. In media φ(k) è circa 0,61 k: la media di φ(k)/k tende a 6/π² ≈ 0,6079, che è anche la probabilità che due interi presi a caso siano coprimi, e φ(1) + … + φ(N) è vicina a 3N²/π². Per N = 1.000 la somma è 304.192, contro 3N²/π² ≈ 303.964.

Carl Friedrich Gauss, in un ritratto di Christian Albrecht Jensen del 1840. Introdusse la notazione di congruenza a ≡ b (mod n) nelle Disquisitiones Arithmeticae del 1801.
Carl Friedrich Gauss, in un ritratto di Christian Albrecht Jensen del 1840. Introdusse la notazione di congruenza a ≡ b (mod n) nelle Disquisitiones Arithmeticae del 1801.

Valori che non compaiono mai

φ(n) è pari per ogni n da 3 in poi, perché i numeri coprimi con n vanno a coppie k e n − k. Nemmeno ogni numero pari è un valore: 14, 26, 34, 38 e 50 sono i primi che non compaiono mai, mentre 24 è il valore di dieci numeri diversi, da 35 a 90. Trovarli è una ricerca finita, perché per ogni primo p che divide n, p − 1 deve dividere φ(n). Nel 1907 Robert Carmichael affermò che nessun valore viene assunto esattamente una volta. La sua dimostrazione era sbagliata, la questione è ancora aperta, e ogni eccezione dovrebbe essere maggiore di 10^(10^10). D. H. Lehmer chiese nel 1932 se φ(n) possa dividere n − 1 per un n composto; non se ne conosce alcun esempio.

La funzione φ in RSA

RSA sceglie due grandi primi p e q e pubblica n = pq e un esponente e. Poiché φ(n) = (p − 1)(q − 1), chi sa scomporre n può calcolare φ(n), e da questo l'esponente privato d con e × d ≡ 1 (mod φ(n)); il teorema di Eulero garantisce allora che (m^e)^d ≡ m (mod n). Nell'esempio da manuale n = 3233 = 61 × 53, φ(n) = 3.120, e = 17 e d = 2.753. Molte implementazioni usano invece λ(n) = mcm(p − 1, q − 1), qui 780, che dà il d più piccolo 413. Calcolare φ(n) per un modulo RSA di 600 cifre è difficile quanto scomporlo: da n e φ(n) i due primi si ricavano con una sola radice quadrata.

Ron Rivest, Adi Shamir e Len Adleman (da sinistra a destra)
Ron Rivest, Adi Shamir e Len Adleman (da sinistra a destra)

Esplora

Apri il calcolatore e inserisci qualsiasi n fino a 10^18 per vedere φ(n) con i fattori primi e la formula. Fino a 500 i numeri da 1 a n vengono disegnati, quelli coprimi pieni e gli altri colorati secondo il più piccolo primo che hanno in comune con n, così la formula del prodotto diventa un crivello che si può contare. Scegli un numero a per verificare il teorema di Eulero, passa a Grafico per vedere φ(k) fino a 100.000 con i primi sulla retta φ(p) = p − 1, o a Inversa per trovare ogni n con φ(n) = m.

Domande frequenti

Perché φ(1) = 1?

Perché MCD(1, 1) = 1: l'unico numero da 1 a 1 è coprimo con 1. La convenzione mantiene valide anche le formule, per esempio la somma di Gauss sui divisori di n, che per n = 1 è semplicemente φ(1) = 1.

φ è la stessa cosa della funzione che conta i primi?

No. π(n) conta i primi fino a n, φ(n) i numeri fino a n coprimi con n. φ(10) = 4 conta 1, 3, 7 e 9, mentre π(10) = 4 conta 2, 3, 5 e 7. Qui coincidono per caso: φ(12) = 4, ma π(12) = 5.

Quanto velocemente si calcola φ(n)?

Tanto velocemente quanto si riesce a scomporre n. Con i fattori primi noti bastano poche moltiplicazioni; senza di essi non si conosce alcun metodo veloce, ed è su questo che si basa RSA. Per numeri fino a 10^18 la scomposizione richiede millisecondi in un browser, per numeri con centinaia di cifre può richiedere anni.

Quali numeri hanno la φ(n) più piccola rispetto a n?

I numeri con molti piccoli fattori primi. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… dipende solo da quali primi dividono n, non dalle loro potenze: per ogni potenza di 2 vale esattamente 1/2, e per 30 = 2 × 3 × 5 vale 8/30, circa il 27 %. Il prodotto dei primi 15 numeri primi, 614.889.782.588.491.410, ha φ(n)/n ≈ 14 %, il valore più basso tra tutti i numeri fino a 10^18.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Apri il calcolatore