p 1 p 2 …..p r = q 1 q 2 …..q s con p i , q j primi si ha r=s, e (riordinando opportunamente i fattori) p i =q i per ogni i . Dimostrazione:

Lezione del 26 marzo 2008

Teorema di fattorizzazione unica.

Ogni numero naturale n>2 è fattorizzabile nel prodotto di un numero finito di numeri primi. Inoltre tale fattorizzazione è unica a meno dell’ordine dei fattori, nel senso che se:

p 1 p 2 …..p r = q 1 q 2 …..q s con p i , q j primi si ha r=s, e (riordinando opportunamente i fattori) p i =q i per ogni i . Dimostrazione:

Esistenza della fattorizzazione. Per assurdo sia non vuoto l’insieme S di tutti i numeri naturali >1 non fattorizzabili nel prodotto di un numero finito di numeri primi, e sia a il minimo in S.

In particolare a non è primo, e sia b un divisore naturale non banale di a:

a=bc per un opportuno c numero naturale, con b1, ba quindi 1<b<a

Simmetricamente si ha anche c1, ca quindi 1<c<a. Essendo a minimo in S si ha b,cS, ossia b,c sono fattorizzabili nel prodotto di un numero finito di numeri primi, dunque lo è a, contraddizione.

Unicità della fattorizzazione. Sia p 1 p 2 …..p r = q 1 q 2 …..q s con p i , q j primi.

Poiché p 1 (q 1 q 2 …..q s ) , per il Lemma si ha p 1 q i per qualche i=1,…,s, e (riordinando opportunamente i fattori) possiamo supporre p 1 q 1 . Essendo p 1 ,q 1 primi (quindi >1), si ha p 1 =q 1 . Dividendo per p 1 si ha p 2 …..p r = q 2 …..q s e si può iterare il procedimento ottenendo p i =q i per ogni i . Resta da verificare che r=s: se per assurdo fosse (per esempio) r>s, si avrebbe, dopo s iterazioni del processo precedente:

p s+1 …..p r =1 contraddizione perché ogni p i >1 . Corollario (Euclide).

Esistono infiniti numeri primi.

Dimostrazione. Per assurdo supponiamo finito l’insieme P di tutti i numeri primi e consideriamo il seguente numero naturale >1: a=( 

p P

p )+1 .

Per il teorema precedente, esiste un divisore primo p 0 P di a (basta scegliere a piacere un fattore primo nella fattorizzazione di a), da cui, essendo p 0  

p P

p , si ottiene p 0 1, contraddizione perché p>1 .

Nota storica: il più grande numero primo conosciuto attualmente è il numero 2 ^32,582,657 -1 (è uno dei cosiddetti numeri di Mersenne della forma 2 ⁿ -1, che studieremo in seguito). Esso ha 9,808,358 cifre (in base 10) ed è stato trovato nel Settembre 2006 nell’ambito del progetto GIMPS (Great Internet Mersenne Primes Search: www.mersenne.org).

Problemi:

1) Trovare un algoritmo di complessità polinomiale che, dato in input un naturale a>1, testi se a è primo o no (test di primalità).

2) Trovare un algoritmo di complessità polinomiale che, dato in input un naturale a>1, calcoli tutti i suoi fattori primi (algoritmi di fattorizzazione).

Fra i test di primalità distingueremo i test deterministici nei quali, dato in input un numero naturale

n>1, l’algoritmo fornisce come output “n è numero primo” se e solo se n è un numero primo, e i

test probabilistici nei quali vi è la scelta casuale di alcuni elementi utilizzati dall’algoritmo e dove ,

se l’input n è primo, l’output è sempre “n è un numero primo”, ma se n non è primo l’output può

essere egualmente (non correttamente) “n è un numero primo”, e la probabilità di tale errore è

maggiorata da una costante indipendente dall’input e dagli elementi casuali (in questo caso

eseguendo più volte il test, la probabilità che un numero non primo superi erroneamente il test si può rendere piccola a piacere).

Inoltre fra i test deterministici ne presenteremo alcuni che sono validi solo per numeri naturali particolari (per esempio i numeri di Fermat della forma ₂ ²

+1, oppure i numeri di Mersenne della forma 2 ^k -1).

Il problema di trovare un test deterministico che risolva il problema 1) è stato risolto solo nel 2003 da Agrawal, Kayal, Saxena nel loro articolo “Primes in P”, con la costruzione di un test deterministico di primalità avente complessità polinomiale, ormai noto come “test AKS” (di cui ci occuperemo in seguito). Sono invece ben noti da tempo test probabilistici di primalità di complessità polinomiale (test di Rabin-Miller etc.).

Invece, come già accennato, il problema 2) attualmente non è stato risolto (e molti matematici sono convinti che non abbia soluzione).

Distribuzione dei numeri primi

Nella successione dei numeri naturali, i numeri primi sono distribuiti in modo irregolare.

Si possono per esempio costruire intervalli di k naturali consecutivi (con k intero >0 arbitrariamente grande) che non contengono nessun numero primo: basta considerare i k naturali consecutivi della forma (k+1)!+j dove j assume i valori 2,3,…,k+1 (ognuno di essi è multiplo di j, perché j (k+1)!, quindi non è primo).

Se ordiniamo in ordine crescente i numeri primi in una successione p 1 , p 2 , ….., p n ,….. (quindi p 1 =2, p 2 =3, p 3 =5, etc..) non esiste una formula algebrica che permetta di calcolare il numero primo p n di posto n, ma si può dare un maggiorante per l’ordine di grandezza di p n :

Teorema.

Per ogni naturale n si ha p n  ₂ ⁽²

⁾ .

Dimostrazione:Per induzione su n (II ^a forma). Per n=1 si ha p 1 =2= ₂ ⁽²

⁾ . Dato n>1, supponiamo la tesi vera per ogni k=1,….,n-1, e dimostriamola per n: se poniamo a=(  ^

 1 1

p i n i

)+1, per il Teorema di Fattorizzazione unica esisterà un primo p divisore di a, e sarà p p 1 ,p 2 ,…,p n-1 (altrimenti si avrebbe p1, contraddizione), dunque (essendo i primi p i ordinati in modo crescente) :

p n pa=(  ^

 1 1

p i n

i )+1(  ^

 1 1

) (2

2 n

i )+1= ^ _ ^{  } _ ^



 1  n

1 i

1

2 i

2 +1 (per l’ipotesi induttiva).

Ma è facile dimostrare (per induzione) che  ^

 1  n

1 i

1

2 i =2 ^n-1 -1 , dunque:

p n  ₂ ⁽²

^{- 1)} +1=

2

2 ⁽²

⁾ +1

2 2 ⁽²

⁾ +

2

2 ⁽²

⁾ = ₂ ⁽²

⁾ e si ha la tesi.

Nota: il maggiorante ₂ ⁽²

⁾ per p n è molto “debole”, e in generale ₂ ⁽²

⁾ è molto più grande di p n ;

per esempio per n=4 si ha p 4 =7 ma ₂ ⁽²

⁾ =256.