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).