la funzione di Eulero dà il risultato corretto: 8.
Infatti sono otto i numeri minori di 15 e primi con 15: (1, 2, 4, 7, 8, 11, 13, 14). Curiosamente
in questa lista compare anche il numero 1.
Il numero 1 è un numero primo o no?
In base alla definizione elementare di numero primo riportata da alcuni testi e dizionari (un numero che ha come fattori solo 1 e se stesso) 1 sarebbe indiscutibilmente primo.
D'altra parte sui manuali di teoria dei numeri la definizione di numero primo viene leggermente modificata; p.es. il Carmichael (1 pag.4) dà le seguenti definizioni:
Numero primo: Un numero intero p diverso da 1 si dice primo assoluto o semplicemente primo quando non ammette altri divisori che 1 e se stesso.
Numero composto: Un numero si dice composto quando ammette almeno un divisore diverso da 1 e da se stesso.
Il numero 1 non rientra in nessuna di queste due definizioni e viene quindi a formare un caso a sè stante.
Perché questa strana esclusione del numero 1?
Il fatto è che in molti casi e applicazioni è conveniente escludere 1 dalla lista di numeri primi. Vediamo un paio di esempi.
Fattorizzazione di un numero intero positivo; nella tabella a destra si vede bene che considerando 1 come numero primo la fattorizzazione di un numero non è più unica, ma anzi esistono un'infinità di fattorizzazioni possibili. Si potrebbe ovviamente modificare la definizione di fattorizzazione escludendo esplicitamente il numero 1, ma è più semplice escludere in partenza 1 dalla lista dei numeri primi.
Un caso un po' paradossale è quello della funzione di Eulero Φ(N) illustrato nella tabella a destra in basso. Nel calcolo della funzione è conveniente escludere 1 dai primi. Il risultato
della funzione però comprende anche 1 tra i numeri minori di N e primi con N! D'altra parte qui si parla di numeri primi relativi e dunque si ricade in una differente definizione.
La distinzione può anche basarsi sul numero di fattori; allora i numeri interi positivi vengono a essere
divisi in tre classi:
Un solo fattore: il numero 1.
Due fattori (uno e se stesso): i numeri primi.
Più di due fattori: i numeri composti.
Fonti bibliografiche e collegamenti
Robert D.Carmichael Theorie des Nombres Paris 1929.
M.du Sautoy L'Enigma dei numeri primi Rizzoli Milano 2004
The Prime Pages: pagine sui numeri primi: ricerca di numeri primi, numeri primi più grandi ...
(in inglese, a cura dell'Università del Tennessee)
RSA Challenge:
La RSA mette in palio premi da 20000$ a 200000$ per chi riuscirà a fattorizzare alcuni grandi numeri (da 640 a 2048 bit)