Vai al contenuto
OneKitly

Un primo è il numero coprimo con quasi tutto ciò che sta sotto

Pubblicato il 27/10/2026 · 3 min di lettura · Calcolatrici quotidiane

Daniel Okonkwo

Daniel Okonkwo — Sviluppatore front-end e redattore Tech presso OneKitly

Performance web · Formati di file

Verificato su 2 fonti

Vedi il profilo →
In breve

La funzione totiente di Eulero conta quanti numeri sotto n non condividono fattori con esso. Per un primo la risposta è tutto: φ(97) = 96, perché 97 non divide nulla al di sotto. Per un numero con piccoli fattori ripetuti la risposta crolla — φ(36) = 12 e φ(100) = 40, poiché 36 è 2² × 3² e 100 è 2² × 5², e ogni pari e ogni multiplo dell'altro primo è squalificato. La formula moltiplica n per uno meno il reciproco di ciascun fattore primo distinto, quindi i fattori ripetuti non costano nulla in più e quelli nuovi costano molto. È tutta lì la ragione per cui le costruzioni crittografiche preferiscono i primi: massimizzano il numero di partner utilizzabili.

Pubblicità

φ(97) = 96, il valore più grande che un numero sotto cento possa raggiungere. φ(36) è 12 e φ(100) è 40 — più fattori primi distinti ha un numero, meno compagni conserva.

La molteplicità è gratis, la varietà costa cara

Trentasei e cento sono entrambi quadrati di numeri privi di quadrati e perdono allo stesso modo, ma cento conserva una quota maggiore perché il cinque toglie solo un quinto dei candidati mentre il tre ne toglie un terzo. Aggiungi un terzo primo distinto e se ne va un'altra frazione: un numero pari a due per tre per cinque per sette conserva meno di un quarto di tutto ciò che sta sotto. Elevare uno di quei primi a una potenza superiore non cambia nulla — 2 × 3 e 2⁵ × 3⁷ conservano esattamente la stessa proporzione. È per questo che la funzione si descrive tramite i primi che dividono n e non tramite la grandezza di n.

Il teorema che la rende utile

Il teorema di Eulero dice che elevare qualsiasi numero coprimo con n alla potenza φ(n) lascia resto uno. Quel solo fatto consente di ridurre un esponente prima ancora di calcolarlo — l'esponente conta solo modulo φ(n) — ed è il cardine matematico su cui ruota la costruzione a chiave pubblica standard. Gli esponenti pubblico e privato di quello schema sono scelti per moltiplicarsi a uno modulo φ(n), sicché applicarli in sequenza restituisce il messaggio originale. Tutto il resto della costruzione è ingegneria; questa è la parte che deve essere vera.

φ(n)
Come la fattorizzazione comanda la risposta
nFattorizzazioneφ(n)Quota di n
362² × 3²1233 %
1002² × 5²4040 %
97979699 %

Esempio calcolato con il nostro strumento

Calcolatore della funzione φ di Eulero

Dati

n (intero positivo)
36

Risultato

φ(n)
12
Numero di coprimi in 1…n
12

Queste cifre sono prodotte dal calcolatore qui sotto, non digitate a mano — vengono ricalcolate a ogni modifica dello strumento.

Rifarlo con i tuoi numeri →
Pubblicità

Domande frequenti

Perché φ(1) vale uno?
Per convenzione, e la convenzione si guadagna il posto. L'uno è contato come coprimo con sé stesso perché il loro massimo comune divisore è uno, che è la definizione usata, e porre φ(1) = 1 mantiene funzionanti tutte le formule che coinvolgono la funzione senza casi speciali. Le definizioni al bordo si scelgono di norma proprio per questo: non perché la risposta sia ovvia, ma perché una scelta rende veri ovunque gli enunciati generali e l'altra costringe eccezioni nel testo.
Si può calcolare φ(n) senza fattorizzare n?
Con nessun mezzo noto, e quell'ignoranza è portante. Conoscere φ(n) per un grande prodotto di due primi equivale a conoscere la fattorizzazione — dati entrambi, l'uno produce l'altro in due righe di algebra — quindi un metodo efficiente per la totiente sarebbe un metodo efficiente di fattorizzazione. La sicurezza dello schema a chiave pubblica standard poggia sul fatto che nessuno abbia né l'uno né l'altro. È uno dei casi più netti in cui un pezzo di teoria dei numeri pura sorregge qualcosa di uso quotidiano.

Articoli che potrebbero interessarti

Tutte le guide →

Strumenti correlati

Fonti

Hai notato un errore in questo articolo?