Calcolate Φ 21 Dove Φ E La Funzione Di Eulero

Calcola il valore della funzione φ di Eulero per n=21 e visualizza i risultati con spiegazioni dettagliate

Guida Completa al Calcolo di φ(21) con la Funzione di Eulero

La funzione di Eulero φ(n), anche conosciuta come funzione totiente, conta il numero di interi positivi fino a n che sono coprimi con n (ovvero il loro massimo comun divisore con n è 1). Questo concetto è fondamentale in teoria dei numeri e crittografia.

Cos’è la Funzione di Eulero?

La funzione φ(n) fu introdotta da Leonhard Euler nel 1763. Per un numero intero positivo n, φ(n) rappresenta:

• Il numero di interi k nell’intervallo [1, n] per cui MCD(n, k) = 1
• L’ordine del gruppo moltiplicativo degli interi modulo n
• Un componente chiave nel teorema di Eulero: a^φ(n) ≡ 1 mod n quando MCD(a, n) = 1

Metodi per Calcolare φ(21)

1. Fattorizzazione in Primi

Il metodo più efficiente sfrutta la formula:

φ(n) = n × ∏ (1 – 1/p) per tutti i primi p che dividono n

Per n = 21:

1. Fattorizzazione: 21 = 3 × 7
2. Applicazione formula: φ(21) = 21 × (1 – 1/3) × (1 – 1/7)
3. Calcolo: 21 × (2/3) × (6/7) = 21 × (12/21) = 12

2. Conteggio Diretto

Elenchiamo tutti i numeri da 1 a 21 e contiamo quelli coprimi con 21:

Numeri coprimi con 21: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20 → Totale: 12

Proprietà Importanti di φ(n)

Proprietà	Formula	Esempio con n=21
Moltiplicatività	φ(ab) = φ(a)φ(b) se MCD(a,b)=1	φ(21) = φ(3)×φ(7) = 2×6 = 12
Potenza di primo	φ(p^k) = p^k – p^k-1	φ(3^1) = 3 – 1 = 2
Teorema di Euler	a^φ(n) ≡ 1 mod n	2^12 ≡ 1 mod 21

Applicazioni Pratiche

La funzione di Eulero ha applicazioni crittografiche fondamentali:

• RSA: La sicurezza dell’algoritmo RSA si basa sulla difficoltà di fattorizzare n = p×q dove φ(n) = (p-1)(q-1)
• Firme digitali: Usate in protocolli come DSA che dipendono da proprietà dei gruppi di ordine φ(n)
• Generatori pseudo-casuali: Alcuni algoritmi usano φ(n) per determinare periodi di sequenze

Confronto con Altri Valori di φ(n)

n	Fattorizzazione	φ(n)	Densità φ(n)/n
10	2 × 5	4	0.400
21	3 × 7	12	0.571
30	2 × 3 × 5	8	0.267
100	2^2 × 5^2	40	0.400
101	primo	100	0.990

Risorse Accademiche

Per approfondimenti teorici sulla funzione di Eulero:

• University of California, Berkeley – Number Theory Notes (PDF con dimostrazioni complete)
• NIST FIPS 186-5 (Standard crittografici che usano φ(n))
• MIT OpenCourseWare – Lecture on Euler’s Theorem (Applicazioni in crittografia)

Errori Comuni da Evitare

1. Dimenticare la moltiplicatività: φ(ab) ≠ φ(a)φ(b) se a e b non sono coprimi
2. Confondere con la funzione Möbius: μ(n) è diversa da φ(n) anche se entrambe sono usate in teoria dei numeri
3. Calcoli errati per potenze: φ(p^k) = p^k – p^k-1, non p^k-1(p-1)
4. Trascurare il caso n=1: φ(1) = 1 per definizione

Esercizi Pratici

Prova a calcolare questi valori:

1. φ(15) [Risposta: 8]
2. φ(28) [Risposta: 12]
3. φ(36) [Risposta: 12]
4. φ(101) [Risposta: 100]