La funzione totiente di Eulero

La funzione totiente di Eulero

a cura di Flavio Cimolin

(pagina a cura di Marco Frigerio) (ultimo aggiornamento: 24/08/2006)

Ecco un'altra bella formula di teoria dei numeri che non può che destare stupore in chi la vede per la

prima volta.

Chiamiamo Φ la funzione totiente di Eulero, che per ogni numero naturale k restituisca il valore

Φ(k) pari al numero di interi positivi minori o uguali a k che sono primi con esso. Ricordiamo che

due numeri sono primi fra loro se e solo se non hanno alcun divisore in comune.

Ad esempio, risulta Φ(1) = 1 e Φ(p) = p - 1 se p è un numero primo. Si dimostra che in generale

vale la seguente formula per il calcolo di Φ(N):

dove n è il numero dei fattori primi distinti di N e p sono i fattori primi stessi (l'ordine è

i

ininfluente). Applicando la formula appena vista si trova, per esempio: Φ(2)=1,

Φ(3)=Φ(4)=Φ(6)=2, Φ(12)=4,…Vediamo ad esempio come funziona il calcolo per N=12. I suoi

fattori primi sono 2, 3 quindi applicando la formula si ottiene Φ(12) = 12 * (1 - 1/2) * (1- 1/3) = 12

* 1/2 * 2/3 = 4. E infatti gli interi minori o uguali a 12 e primi con esso sono quattro: 1, 5, 7, 11.

Sulla funzione totiente esiste un'altra interessante proprietà, che può essere espressa dalla formula

dove d percorre tutti i divisori di N (inclusi 1 e lo stesso N). Ad esempio, per il numero N=12, i cui

divisori sono 1, 2, 3, 4, 6, 12, si ottiene:

12 = Φ(1) + Φ(2) + Φ(3) + Φ(4) + Φ(6) + Φ(12)= 1+1+2+2+2+4.

Un'interpretazione elementare di tale proprietà può essere data in questi termini. Prendiamo tutte le

frazioni aventi denominatore N=12 e numeratore (intero) 0<X<=12. Scritte nell'ordine sono:

1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12, 12/12

Ridotte, diventano: http://www.matematicamente.it