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