Funzione phi di Eulero
La funzione φ (si legge fi) di Eulero è una funzione molto utile nello studio dell'aritmetica modulare.Questa funzione φ (n) esprime il numero di tutti gli interi k minori o uguali ad n tali che
[math]MCD(n, k) = 1[/math]
, oppure, detto in altre parole, che n e k siano coprimi.Calcoliamo il valore di φ (n) per alcuni interi:
Calcoliamo il valore di φ (5)
5 è primo, per cui solo 5 divide 5. Allora φ (5) = 4, come ogni numero primo p: φ (p) = p-1
Inoltre per ogni coppia di numeri interi (a, b) primi tra loro: φ (ab) = φ (a) φ (b)
È importante dire che anziché verificare di forza bruta tutti i numeri minori o uguali ad n che siano coprimi con n, la funzione phi di Eulero si può calcolare nel seguente modo.
Se
[math]n = p_1^{a_1}*p_2^{a_2}...[/math]
, dove p sono i fattori primi di n, allora:φ (n) =
[math]p_1^{a_1-1}(p_1-1)p_2^{a_2-1}(p_2-1)...[/math]
Calcoliamo φ (100).Il primo passo da fare è scomporre 100. 100 = 22*52
A questo punto φ (n) =
[math]2^{2-1}*5^{2-1}*(2-1)*(5-1) = 2*5*1*4 = 40[/math]
Ora calcoliamo φ (86)86 = 2*43, allora:
φ (86) =
[math]2^{1-1}*43{1-1}*{2-1}*{43-1}=1*1*1*42 = 42[/math]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
