Calcolatrice della funzione φ di Eulero (funzione toziente)

Inserendo un intero N compreso fra 1 e 1.000.000, mostra all'istante quanti interi da 1 a N siano coprimi con esso, cioè il valore della funzione φ di Eulero, insieme alla scomposizione in fattori primi e alla formula. Comprende un prospetto dei valori da 1 a 100.

Prospetto dei valori di φ da 1 a 100

Un prospetto che raccoglie, per gli interi da uno a cento, la scomposizione in fattori primi e il valore della funzione φ di Eulero.

N Scomposizione φ(n)
1 1 1
2 2 1
3 3 2
4 2² 2
5 5 4
6 2 × 3 2
7 7 6
8 2³ 4
9 3² 6
10 2 × 5 4
11 11 10
12 2² × 3 4
13 13 12
14 2 × 7 6
15 3 × 5 8
16 2⁴ 8
17 17 16
18 2 × 3² 6
19 19 18
20 2² × 5 8
21 3 × 7 12
22 2 × 11 10
23 23 22
24 2³ × 3 8
25 5² 20
26 2 × 13 12
27 3³ 18
28 2² × 7 12
29 29 28
30 2 × 3 × 5 8
31 31 30
32 2⁵ 16
33 3 × 11 20
34 2 × 17 16
35 5 × 7 24
36 2² × 3² 12
37 37 36
38 2 × 19 18
39 3 × 13 24
40 2³ × 5 16
41 41 40
42 2 × 3 × 7 12
43 43 42
44 2² × 11 20
45 3² × 5 24
46 2 × 23 22
47 47 46
48 2⁴ × 3 16
49 7² 42
50 2 × 5² 20
51 3 × 17 32
52 2² × 13 24
53 53 52
54 2 × 3³ 18
55 5 × 11 40
56 2³ × 7 24
57 3 × 19 36
58 2 × 29 28
59 59 58
60 2² × 3 × 5 16
61 61 60
62 2 × 31 30
63 3² × 7 36
64 2⁶ 32
65 5 × 13 48
66 2 × 3 × 11 20
67 67 66
68 2² × 17 32
69 3 × 23 44
70 2 × 5 × 7 24
71 71 70
72 2³ × 3² 24
73 73 72
74 2 × 37 36
75 3 × 5² 40
76 2² × 19 36
77 7 × 11 60
78 2 × 3 × 13 24
79 79 78
80 2⁴ × 5 32
81 3⁴ 54
82 2 × 41 40
83 83 82
84 2² × 3 × 7 24
85 5 × 17 64
86 2 × 43 42
87 3 × 29 56
88 2³ × 11 40
89 89 88
90 2 × 3² × 5 24
91 7 × 13 72
92 2² × 23 44
93 3 × 31 60
94 2 × 47 46
95 5 × 19 72
96 2⁵ × 3 32
97 97 96
98 2 × 7² 42
99 3² × 11 60
100 2² × 5² 40

Consigli

  • La funzione φ di Eulero indica quanti interi da uno a n siano coprimi con n. Per esempio φ di nove vale sei, perché uno, due, quattro, cinque, sette e otto sono coprimi con nove.
  • Se n è un numero primo p, allora φ di p vale p meno uno: sono coprimi con un primo tutti i numeri da uno a p tranne il primo stesso.
  • Se n è il prodotto di due numeri primi distinti, φ è il prodotto dei due primi ciascuno diminuito di uno: è la proprietà usata direttamente nella generazione delle chiavi della crittografia RSA.
  • La formula moltiplica n per il prodotto, esteso a tutti i fattori primi distinti, di uno meno il reciproco di ciascun primo. Gli esponenti non incidono sul risultato.
  • Lo strumento copre l'intervallo da uno a un milione e ricava il valore all'istante scomponendo il numero con le divisioni successive.

Domande frequenti

Oltre che come teoria di base dei numeri, svolge un ruolo centrale nella crittografia, in particolare nella generazione delle chiavi RSA, dove il calcolo della chiave privata richiede il valore della funzione φ del prodotto dei due numeri primi.

È una convenzione. L'unico intero non superiore a uno e coprimo con esso è l'uno stesso, e porre il valore pari a uno è il trattamento standard, che preserva la coerenza matematica della funzione come funzione moltiplicativa.

Sì. Un numero primo non ha divisori oltre a uno e a sé stesso: fra gli interi da uno al primo stesso, tutti tranne quest'ultimo gli sono coprimi, e il valore è dunque il primo diminuito di uno.

La crittografia RSA usa come parte della chiave pubblica il numero composto ottenuto moltiplicando due grandi numeri primi. Per calcolare la chiave privata occorre il valore della funzione φ, pari al prodotto dei due primi ciascuno diminuito di uno; poiché senza la scomposizione non lo si può ricavare, la difficoltà di scomporre i numeri grandi è il fondamento della sicurezza del sistema.
Tool-kun

A proposito — la funzione con cui Eulero contò i numeri coprimi nel Settecento

La funzione φ, detta anche funzione toziente, sarebbe stata introdotta intorno al 1763 dal matematico svizzero Leonhard Euler. Nacque nel corso degli studi volti a estendere ai numeri composti il piccolo teorema di Fermat, e il simbolo φ si affermò più tardi, per opera di altri matematici.

L'operazione di contare i numeri coprimi appare semplice, eppure la funzione ha proprietà eleganti. Sommando i valori di φ su tutti i divisori di n si riottiene esattamente n: è una delle identità fondamentali della teoria elementare dei numeri.

Oggi la funzione svolge un ruolo indispensabile nella generazione delle chiavi della crittografia RSA. Quel sistema usa come parte della chiave pubblica il prodotto di due grandi numeri primi, ma per costruire la chiave privata occorre il valore della funzione φ di quel prodotto, pari al prodotto dei due primi ciascuno diminuito di uno. Il fatto che senza scomporre il numero non si possa calcolare quel valore, almeno con gli algoritmi oggi noti, è uno dei fondamenti della sicurezza della crittografia RSA.

Leggi le curiosità collegate

Vedi tutte le curiosità

Chi consulta questo strumento guarda anche

Verifica dei numeri primi (gratis) — fino a mille cifre, con scomposizione

Stabilisce all'istante se un numero fino a mille cifre sia primo. Strumento gratuito che mostra anche la scomposizione in fattori primi, i numeri primi precedente e successivo, i passaggi delle divisioni successive e il...

Generatore con il crivello di Eratostene (gratis) — elenco dei primi e ricerca dell'ennesimo

Basta indicare un limite superiore per generare l'elenco dei numeri primi con il crivello di Eratostene, visualizzandone i passaggi. Comprende un prospetto da 1 a 100, copre intervalli fino a un milione e permette di cer...

Scomposizione in fattori primi (gratis, da 2 a un milione)

Strumento gratuito di scomposizione in fattori primi. Scompone all'istante qualunque intero fra 2 e 1.000.000 e mostra automaticamente i passaggi, l'elenco dei divisori, il loro numero e la loro somma. Comprende un prosp...

Calcolatrice del massimo comune divisore e del minimo comune multiplo

Inserendo due interi positivi, ricava il massimo comune divisore con l'algoritmo di Euclide e ne mostra i passaggi uno per uno. Calcola contemporaneamente anche il minimo comune multiplo.

Calcolatrice dell'aritmetica modulare (congruenze)

Calcolatrice per le congruenze con quattro modalità: resto elementare, addizione, sottrazione e moltiplicazione, elevamento a potenza con il metodo dei quadrati ripetuti e inverso modulare con l'algoritmo di Euclide este...

Calcolatrice del teorema cinese del resto — sistemi di congruenze

Calcolatrice che risolve con il teorema cinese del resto i sistemi di congruenze del tipo x congruo ad a modulo n. Verifica automaticamente che i moduli siano coprimi e ricava la soluzione intera non negativa minima e la...