p=a/b dove a,b sono naturali. Si ha p=a

Matematica Discreta

Lezione del giorno 13 gennaio 2012

Teorema di fattorizzazione unica. Ogni numero naturale a>1 è fattorizzabile come prodotto di numeri primi (al limite con 1 solo fattore) e tale fattorizzazione è unica (a meno dell’ordine dei fattori), nel senso che, se sono date 2 fattorizzazioni dello stesso a in prodotto di numeri primi:

a=p1p2….pr=q1q2…qs (dove tutti i pi e i qj sono numeri primi) allora:

1) r=s (il numero dei fattori primi nelle 2 fattorizzazioni è uguale)

2) riordinando opportunamente i fattori, si ha p1=q1, p2=q2, …., pr=qr (cioè i fattori coincidono ordinatamente nelle due fattorizzazioni)

Dimostrazione:

Esistenza della fattorizzazione:

Supponiamo per assurdo che esistano numeri naturali non fattorizzabili nel prodotto di numeri primi, e costruiamo l’insieme S di tali numeri:

S = {x / xN, x>1, x non é fattorizzabile nel prodotto di numeri primi}

L’insieme non vuoto S, per l’Assioma del minimo, contiene un elemento minimo sS: sarà sN, s>1, s non fattorizzabile nel prodotto di numeri primi. In particolare s non è un numero primo (altrimenti s sarebbe fattorizzabile nel prodotto di numeri primi, con 1 solo fattore) quindi s ha un divisore non banale b, con b1,bs. Esiste allora un naturale c tale che s=bc, e ovviamente anche c1,cs. In totale si ha 1<b<s, 1<c<s, ed essendo s il minimo in S, si deduce che b,cS, dunque b,c sono entrambi fattorizzabili nel prodotto di numeri primi, ma allora anche a=bc sarebbe fattorizzabile nel prodotto di numeri primi, contraddizione.

Unicità della fattorizzazione:

Sia a un numero naturale >1 e siano date 2 fattorizzazioni di a in prodotto di numeri primi:

a=p1p2….pr=q1q2…qs (dove tutti i pi e i qj sono numeri primi) Le tesi sono allora le seguenti:

1) r=s (il numero dei fattori primi nelle 2 fattorizzazioni è uguale)

2) riordinando opportunamente i fattori, si ha p1=q1, p2=q2, …., pr=qr (cioè i fattori coincidono ordinatamente nelle due fattorizzazioni).

Dall’eguaglianza a=p1(p2….pr)=q1q2…qs segue che p1 è divisore del prodotto q1q2…qs. Per l’Osservazione nella precedente lezione, il numero primo p1 è divisore di almeno uno dei fattori q1,q2,…,qs e, riordinando opportunamente i fattori, possiamo fare in modo che p1q1. Essendo q1

primo, le possibilità per il suo divisore p1 sono p1=1 oppure p1=q1. Ma allora p1=q1 (perché per definizione di numero primo si ha p1>1).

Dividendo ambo i membri dell’eguaglianza per p1 si ottiene l’eguaglianza: p2p3….pr=q2q3…qs, e si può iterare il ragionamento ottenendo p2=q2 (riordinando di nuovo opportunamente i fattori). La tesi 2) è dunque dimostrata. Dimostriamo ora la tesi 1): se per assurdo la supponessimo falsa, si avrebbe rs. Supponiamo per esempio che sia r>s (se r<s si ragiona in modo simile): dopo s passi del precedente procedimento iterativo, dividendo per ps, si avrebbe alla fine l’eguaglianza:

ps+1ps+2….pr=1, contraddizione perché i numeri primi pi sono tutti >1.

Illustriamo una conseguenza del Teorema di fattorizzazione unica:

Teorema.

La radice quadrata di un numero primo p è un numero non razionale.

Dimostrazione:

Per assurdo supponiamo ^p=a/b dove a,b sono naturali. Si ha p=a²/b², b²p=a². Nel caso a=1, si ha b²p=1, contraddizione perché p>1.

Nel caso b=1 si ha p=a²=aa, contraddizione perché il primo p avrebbe un divisore a non banale.

Infine nel caso a>1, b>1, fattorizziamo a, b in prodotto di primi:

a=p1p2….pr , b=q1q2…qs

da cui si avrebbe:

b²p= q1q1q2q2…qsqsp=a²=p1p1p2p2…prpr

e per il Teorema di fattorizzazione unica sarebbe uguale il numero di fattori primi nelle 2 fattorizzazioni, ottenendo l’eguaglianza 2s+1=2r, contraddizione perché 2s+1 è dispari, 2r è pari.

Illustriamo un’altra conseguenza del Teorema di fattorizzazione unica:

Teorema.

I numeri primi sono infiniti.

Dimostrazione:

Per assurdo supponiamo che l’insieme dei numeri primi contenga un numero finito di elementi, e sia p1,p2,….,pk l’elenco completo di tutti i numeri primi. Consideriamo il seguente numero naturale ottenuto sommando 1 al prodotto di tutti i numeri primi: a=(p1p2….pk)+1 .

Per il Teorema di esistenza della fattorizzazione, a si può scomporre in fattori primi e se p è uno qualunque dei suoi fattori primi si ha ovviamente pa, ossia esiste un numero naturale c tale che pc=a=(p1p2….pk)+1, da cui 1=pc-(p1p2….pk). Ma p coinciderà con uno dei pi (perché per assurdo p1,p2,….,pk sono tutti i possibili numeri primi), dunque nel secondo membro dell’eguaglianza precedente si può mettere in evidenza il fattore comune p, e si conclude che p è divisore di 1, contraddizione perché p>1.