Calcolatrice della Funzione φ di Eulero (Funzione Toziente, Numeri Coprimi)

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, non solo il risultato ma anche la scomposizione in fattori primi e la formula. Comprende gratis 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

Che cos’è la funzione φ di Eulero

La funzione φ di Eulero conta quanti degli interi da 1 a n siano coprimi con n. Coprimi significa che il loro massimo comune divisore è 1, ossia che non condividono alcun fattore primo. Così φ(9) vale 6, perché 1, 2, 4, 5, 7 e 8 non condividono con 9 alcun fattore primo.

Questo strumento ricava φ(N) dall’intero che lei inserisce e mostra, oltre alla risposta, **la scomposizione in fattori primi di N e la formula che da essa conduce a φ(N)**. La formula è φ(n) = n × Π(1 − 1/p), col prodotto esteso ai fattori primi distinti p di n. Per quante volte un primo si ripeta, entra nel prodotto una sola volta: l’esponente non muta il risultato. Si accetta ogni valore da 1 a 1.000.000 e più sotto compare una tavola di φ(n) da 1 a 100.

Come si usa il calcolatore

Inserisca l’intero N Indichi un numero intero da 1 a 1.000.000. Ogni valore fuori da questo intervallo, o non intero, provoca un avviso.
Legga il valore di φ(N) Mentre digita compare il numero degli interi da 1 a N coprimi con N.
Verifichi la scomposizione Le viene mostrato in quali primi N si scompone: un filo da seguire se vuole vedere donde provenga il valore di φ(N).
Segua la deduzione con la formula La formula φ(n) = n × Π(1 − 1/p) compare con i fattori primi reali già sostituiti, pronta a controllare un calcolo svolto a mano.
Confronti con la tavola Più sotto sta un elenco di φ(n) da 1 a 100, nel quale si colgono a occhio delle regolarità: per esempio che φ di un primo vale quel primo meno uno.

Consigli per sfruttarlo al meglio

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.

Dove la funzione φ è utile

Studiare teoria dei numeri e correggere i compiti

Verifichi se il φ(n) ricavato a mano sia esatto. Poiché accanto compaiono scomposizione e formula, si scopre un errore anche nella deduzione e non solo nel risultato.

Capire come funziona l’RSA

L’RSA prende il prodotto n = pq di due primi come parte della chiave pubblica, e per costruire la chiave privata occorre φ(n) = (p−1)(q−1). Svolgendolo con primi piccoli, quel legame diventa concreto.

Verificare il teorema di Eulero

Il teorema di Eulero afferma che, per a coprimo con n, a elevato a φ(n) lascia resto 1 nella divisione per n. Ottenuto prima φ(n), può provare il teorema su numeri piccoli.

Osservare la proprietà moltiplicativa

Quando m e n sono coprimi, φ(mn) = φ(m)φ(n). Combinando i valori della tavola si vede che ciò vale davvero.

Quando cerca la scomposizione in sé

Se le occorrono i soli fattori, usi la scomposizione in fattori primi; per sapere se un numero sia primo, il test di primalità.

Termini sulla funzione φ

Funzione φ di Eulero: La funzione che restituisce quanti interi da 1 a n siano coprimi con n. Si scrive φ(n) e fu introdotta da Leonhard Euler nel Settecento.
Coprimi: Condizione di due interi il cui massimo comune divisore è 1, il che equivale a non condividere alcun fattore primo.
Scomposizione in fattori primi: Lo scrivere un intero come prodotto di primi. Poiché φ(n) dipende solo dai fattori primi distinti di n, il calcolo muove da questa scomposizione.
Funzione moltiplicativa: Funzione per cui f(mn) = f(m)f(n) ogni volta che m e n siano coprimi. φ possiede questa proprietà, ed è per questo che il valore di un numero grande si può comporre a partire dai suoi fattori primi.
Teorema di Eulero: Il teorema secondo cui, per ogni a coprimo con n, a elevato a φ(n) lascia sempre resto 1 nella divisione per n. Ristretto a un modulo primo, è il piccolo teorema di Fermat.
RSA: Cifratura a chiave pubblica che adopera come chiave pubblica il prodotto di due grandi primi. La chiave privata richiede φ(n), e il fatto che φ(n) non si ottenga senza scomporre n è uno dei fondamenti della sua sicurezza.

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.

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.

Vedi tutte le curiosità