(1)Matematica Discreta I Lezione del giorno 12 novembre 2007 Numeri primi Sia a un qualunque numero naturale

Matematica Discreta I

Lezione del giorno 12 novembre 2007 Numeri primi

Sia a un qualunque numero naturale. Dall’eguaglianza a=a•1 segue che a,1 sono in ogni caso divisori di a (detti divisori banali di a).

Definiamo numero primo un numero naturale a>1 i cui unici divisori sono i divisori banali 1,a . Nota: osserviamo che, nella definizione di numero primo, il numero naturale 1 non è considerato primo. Il motivo di questa esclusione del numero 1 dai numeri primi sarà chiarito nella dimostrazione del “Teorema di fattorizzazione unica”.

Per verificare se un numero naturale a>1 è primo o non lo è, un test (poco efficiente) consiste ovviamente nell’esaminare tutti i numeri naturali x compresi fra 2 e (a-1), e per ognuno di tali x testare se esso è divisore o no di a (cioè dividendo a per x e verificando se il resto è 0): se nessun valore x fra 2 ed (a-1) è divisore di a, si conclude che a non ha divisori non banali, quindi a è primo;

se qualche valore x fra 2 ed (a-1) è divisore di a, si è trovato un divisore non banale di a, quindi a non è primo.

Si devono dunque effettuare (al più) a-2 divisioni.

Esempio:

Dato il numero a=1009, non si trova nessun valore x con x=2,3,4,….,1008, che sia divisore di x (effettuando 1007 divisioni). Quindi a=1009 è primo.

Si può rendere più efficiente tale test basandosi sulla seguente osservazione: se un numero naturale a>1 non è primo, esso ha certamente qualche divisore non banale ≤ a (infatti se b è un divisore non banale di a allora esiste un naturale c tale che si abbia bc=a ; ma i divisori b,c non possono essere entrambi > a , perché altrimenti sarebbe a=cd>( a )²=a, contraddizione).

Dunque per verificare se un numero naturale a>1 è primo o non lo è, basta esaminare i numeri naturali x con x>1 ed x ^a , e se fra essi non vi è un divisore di a si può concludere che a è primo.

Questo riduce drasticamente il numero di divisioni da effettuare nel test.

Esempio: se a=1009, il test originario prevede di testare i naturali da 2 a 1008 (operando 1007 divisioni) per scoprire che nessuno è divisore di 1009 e concludere che 1009 è primo; invece con il secondo test (più efficiente), essendo 1009 circa =31,76, dovremmo testare solo i numeri naturali da 2 a 31 (30 divisioni in tutto) per concludere che 1009 è primo.

Il raffinamento del test sopra illustrato è spesso insufficiente nel caso di numeri molto grandi (con centinaia di cifre): attualmente i matematici sviluppano test di primalità sempre più efficienti e veloci.

Fattorizzazione in primi

Dimostreremo che i numeri primi sono come i “mattoni” elementari con cui si possono “costruire “ tutti i numeri naturali >1, nel senso che ogni naturale >1 è prodotto di numeri primi e tale rappresentazione è in un certo senso “unica”. Ricordiamo che per convenzione il termine “prodotto”

si intende al limite anche con 1 solo fattore.

Premettiamo un risultato preliminare sui numeri primi:

Teorema.

1) Se p, q sono numeri primi distinti, p,q sono coprimi.

2) Se p è un numero primo e se p é divisore del prodotto di n numeri naturali:

p (a1a2…..an)

allora p è divisore di almeno uno dei fattori a1a2…..an . Dimostrazione:

1) Posto d=mcd(p,q), si ha dp, dq, ed essendo p, q primi si ha d=1, p oppure d=1, q. Ma per ipotesi pq, dunque l’unica possibilità è che d=1.

2) Utilizziamo il principio di induzione.

Per n=1 l’affermazione è banale.

Supponiamola vera per n e dimostriamola per n+1.

Supponiamo dunque che p sia divisore del prodotto di n+1 numeri naturali:

p (a1a2…..anan+1) (quindi esiste un numero naturale c tale che pc= a1a2…..anan+1) e dimostriamo che p è divisore di almeno uno dei fattori a1, a2, ….., an, an+1.

Distinguiamo 2 casi.

Primo caso: se p è divisore di an+1, non vi è niente da dimostrare

Secondo caso: se p non è divisore di an+1, posto d=mcd(p, an+1), si ha dp (dunque d=1, p), dan+1

(quindi dp perché p non è divisore di an+1) e si conclude che 1=d=mcd(p, an+1). Per una proprietà del mcd, esistono interi relativi x, y tali che 1=px+an+1y. Moltiplicando ambo i membri per il prodotto a1a2…..an si ottiene a1a2…..an=pxa1a2…..an+ a1a2…..anan+1y=p(xa1a2…..an+cy), ossia p è divisore del prodotto pxa1a2…..an.

Essendo per ipotesi vera l’affermazione per n, si ha che è divisore di almeno uno dei fattori a1a2…..an, quindi p è divisore di almeno uno dei fattori a1, a2, ….., an, an+1, come si voleva.

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

allora:

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

2) riordinando opportunamente i fattori, si ha p1=q1,p2=q2 etc. (cioè i fattori coincidono 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:

Supponiamo:

a=p1p2….pr=q1q2…qs

con pi, qj numeri primi, e dimostriamo le tesi 1) e 2) dell’enunciato.

Da a=p1(p2….pr)=q1q2…qs segue che p1 è divisore del prodotto q1q2…qs. Per il Teorema precedente, il numero primo p1 è divisore di qualcuno 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 che, riordinando opportunamente i fattori, si abbia p2=q2 e così via. La tesi 2) è dunque dimostrata. Dimostriamo ora la tesi 1): se per assurdo la supponessimo falsa, si avrebbe rs (per esempio r>s) e dopo s passi del precedente procedimento iterativo, dividendo per ps, si avrebbe l’eguaglianza: ps+1ps+2….pr=1, contraddizione perché i numeri primi pi

sono tutti >1.

Nota: anche usando gli algoritmi di fattorizzazione più veloci attualmente conosciuti, il problema di fattorizzare un dato numero naturale in prodotto di numeri primi ha una complessità di calcolo molto grande; per esempio la fattorizzazione di un numero naturale con 600 cifre decimali richiede mediamente 10¹⁷ anni di calcolo di un computer che possa eseguire 1 miliardo di istruzioni al secondo.

Illustriamo 2 conseguenze del Teorema di fattorizzazione unica:

Teorema.

1) I numeri primi sono infiniti.

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

Dimostrazione:

1) 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 pa, ossia pc=a=(p1p2….pk)+1 dove c è un naturale, da cui 1=pc-(p1p2….pk). Ma p coinciderà con uno dei pi, 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.

2) 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, ottenenendo l’eguaglianza 2s+1=2r, contraddizione perché 2s+1 è dispari, 2r è pari.

Nota: nel settembre 2006 è stato trovato il più grande numero primo attualmente conosciuto (esso ha più di 9.800.000 cifre in base 10).

Utili notizie possono essere trovate sul sito www.mersenne.org