-
Eulero studiava le proprietà di numeri
-
in particolare la distribution dei numeri primi.
-
Un'importante funzione che definì
-
si chiama la funzione Φ (fi), o totiente.
-
Misura la divisibilità di un numero.
-
Ossia, dato un numero 'n'
-
produce il numero di interi ≤ n
-
che non hanno nessun divisore comune a n.
-
Per esempio, se vogliamo trovare il totiente di 8,
-
controlliamo tutti i valori fra 1 e 8,
-
e contiamo quanti di questi interi
-
non hanno in comune nessun divisore >1.
-
Nota che 6 non viene contato
-
perché 6 e 8 hanno in comune il divisore 2,
-
mentre 1, 3, 5 e 7 vengono contati
-
perché hanno solo in comune il divisore 1.
-
Perciò, Φ(8) = 4.
-
La cosa interessante da notare
-
è che calcolare Φ è difficile, eccetto in un caso.
-
Guardo questo grafico.
-
Traccia i valori di Φ per gli interi da 1 a 1000.
-
Vedi un modello prevedibile?
-
La linea diritta in alto
-
rappresenta tutti i numeri primi.
-
Visto che numeri primi non hanno un divisore maggiore a 1,
-
la Φ di ogni numero primo 'p' è semplicemente p-1.
-
Per calcolare Φ(7), un numero primo,
-
contiamo tutti gli interi eccetto 7
-
visto che nessuno di questi ha un divisore comune a 7.
-
Φ(7) = 6.
-
Quindi se ti viene chiesto di trovare Φ(21 377), un numero primo,
-
devi solo sottrarre 1 per ottenere la soluzione,
-
21 376.
-
Φ di qualsiasi numero primo è facile da calcolare.
-
Questo ci porta ad un'interessante risultato, basato sul fatto che
-
la funzione φ è anche 'moltiplicativa'.
-
Ossia, Φ(A x B) = Φ(A) x Φ(B).
-
Se sappiamo che un numero, N,
-
è il prodotto di due numeri primi, P1 e P2,
-
allora Φ(N) è semplicemente
-
il valore Φ di ogni numero primo moltiplicato insieme.
-
ossia (P1 - 1) x (P2 - 1).
