φ(n)
Fattori primi
Quota di coprimi
Divisori

          Mostra

          Altro sulla funzione φ di Eulero

          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

          1. 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.
          2. 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.
          3. 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