- Primi, sulla retta φ(p) = p − 1
- Altri numeri
- Il tuo n
Calcolatore della funzione φ di Eulero
Tra i numeri da 1 a 12, solo 1, 5, 7 e 11 non hanno fattori in comune con 12, quindi φ(12) = 4. La funzione φ di Eulero conta questi numeri coprimi per qualsiasi n. Inserisci un numero fino a 10^18 per ottenere φ(n) con i suoi fattori primi e la formula del prodotto scritta per esteso, vedere i numeri da 1 a n con quelli coprimi evidenziati, verificare il teorema di Eulero, tracciare φ(k) per un massimo di 100.000 numeri alla volta o trovare ogni n con un dato φ(n). Inserisci un numero intero n fino a 10^18, oppure scegli un esempio svolto. I riquadri mostrano φ(n), i fattori primi di n, la quota dei numeri da 1 a n coprimi con n e il numero di divisori, e i passaggi scrivono la formula del prodotto con i tuoi numeri. Fino a n = 500 i numeri da 1 a n vengono disegnati: quelli coprimi sono pieni, gli altri hanno il colore del più piccolo primo che hanno in comune con n. Punta un numero per vedere il suo MCD con n, e fai clic per usarlo come a nel teorema di Eulero. Grafico mostra φ(k) per ogni k fino a un limite; fai clic su un punto per aprire quel numero. Inversa elenca ogni n con φ(n) = m; fai clic su uno per aprirlo.
Come funziona
- Inserisci un numero intero n fino a 10^18, oppure scegli un esempio svolto come φ(60), un modulo RSA o il numero di Carmichael 561.
- Leggi φ(n), i fattori primi e la formula del prodotto con i tuoi numeri. Fino a 500, punta i numeri da 1 a n per vedere il loro MCD con n, e fai clic su uno per verificarci il teorema di Eulero.
- Passa a Grafico per vedere φ(k) per ogni k fino a 100.000, o a Inversa per elencare ogni n con φ(n) = m.
Come si calcola φ(n)
Scomponi n in fattori primi e moltiplica n per (1 − 1/p) per ogni primo p che lo divide. Per 60 = 2² × 3 × 5 si ottiene 60 × 1/2 × 2/3 × 4/5 = 16. Cancellando si ottiene lo stesso conteggio: dei 60 numeri, 30 sono pari; dei 30 dispari, 10 sono multipli di 3; dei 20 rimasti, 4 sono multipli di 5, e ne restano 16. Per una potenza di un primo la formula è φ(p^k) = p^(k−1)(p − 1), e i valori si moltiplicano: φ(60) = 2 × 2 × 4. La parte difficile è la scomposizione. Il calcolatore usa divisioni per tentativi, un test di primalità di Miller-Rabin e il metodo rho di Pollard, così anche un prodotto di 18 cifre di due primi di 9 cifre richiede una frazione di secondo.
Dove si usa la funzione φ
φ(n) conta le frazioni k/n tra 0 e 1 già ridotte ai minimi termini, i passi che portano una lancetta su ogni ora di un orologio con n ore (1, 5, 7 e 11 su un orologio di 12 ore) e i numeri che hanno un inverso modulo n. Eulero dimostrò che a^φ(n) ≡ 1 (mod n) per ogni a coprimo con n, e la crittografia RSA si basa su questo: con n = 3233 = 61 × 53, φ(n) = 60 × 52 = 3.120, e l'esponente pubblico 17 ha come partner privato 2.753, perché 17 × 2.753 = 15 × 3.120 + 1.
Domande frequenti
Che cos'è la funzione φ di Eulero?
φ(n) è il numero di interi da 1 a n che non hanno fattori in comune con n oltre a 1. φ(9) = 6, perché 1, 2, 4, 5, 7 e 8 sono coprimi con 9, mentre 3, 6 e 9 condividono il fattore 3. Per convenzione φ(1) = 1. Eulero studiò la funzione negli anni Sessanta del Settecento; Gauss le diede il simbolo φ nel 1801 e James Joseph Sylvester il nome inglese totient nel 1879.
Quanto vale φ di un numero primo?
p − 1, perché ogni numero da 1 a p − 1 è coprimo con un primo p, quindi φ(97) = 96. Per una potenza di un primo, φ(p^k) = p^k − p^(k−1), perché solo i multipli di p hanno un fattore in comune con essa: φ(81) = 81 − 27 = 54.
Che cosa dice il teorema di Eulero?
Se a e n sono coprimi, allora a^φ(n) dà resto 1 nella divisione per n. Per n = 60 e a = 7: φ(60) = 16, e 7^16 ≡ 1 (mod 60). Il piccolo teorema di Fermat è il caso di n primo. Spesso basta già un esponente più piccolo: 7^4 = 2.401 = 40 × 60 + 1. Il più piccolo esponente che funziona per ogni a coprimo con n è la funzione di Carmichael λ(n), che per 60 vale 4.
Due numeri possono avere la stessa φ?
Sì, e di solito sono diversi: φ(n) = 24 per n = 35, 39, 45, 52, 56, 70, 72, 78, 84 e 90. Alcuni numeri pari non sono mai un valore di φ, il più piccolo è 14, e nessun numero dispari maggiore di 1 lo è, perché φ(n) è pari da n = 3 in poi. Robert Carmichael affermò nel 1907 che nessun valore viene assunto esattamente una volta. Non è ancora dimostrato, e Kevin Ford mostrò nel 1998 che un'eccezione dovrebbe essere maggiore di 10^(10^10).
Quanto grande può essere il numero?
Qualsiasi intero fino a 10^18. Il calcolatore lo scompone con aritmetica intera esatta nel tuo browser, così φ(10^18) = 4 × 10^17 e φ(999.999.866.000.004.473) = 999.999.864.000.004.608 risultano esatti fino all'ultima cifra. I numeri da 1 a n vengono disegnati fino a 500, il grafico arriva a 100.000 e l'inversa funziona per valori fino a 10^10.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor