<< Capitolo precedente Indice Capitolo successivo >>

EUCLIDE E I NUMERI PRIMI

"I numeri primi sono la materia grezza che serve a costruire l'aritmetica e il teorema di Euclide ci assicura che per tale compito noi disponiamo di gran quantità di materiale"
da -Apologia di un matematico- di G.H.Hardy.

Perché trattare di numeri primi?
La matematica si occupa di numeri ed in modo particolare di numeri interi e poiché, come vedremo, ogni numero intero o è primo o è il prodotto di numeri primi è chiara l'importanza che i numeri primi vengono ad assumere all'interno della teoria dei numeri.
Gia Euclide aveva trattato di numeri dando dei contributi originali nei libri VII VIII e IX degli Elementi. Il libro VII inizia con una serie di 22 definizioni sui diversi tipi di numero, e prosegue con 39 proposizioni tra le quali il famoso 'Algoritmo di Euclide' per determinare il massimo comune divisore (o come dice Euclide stesso 'la misura') tra due numeri; il libro VIII tratta di numeri in progressione e di alcune proprietà di numeri 'quadrati' o 'cubi'; l'ultimo, il IX, contiene alcuni risultati molto interessanti, quali la dimostrazione dell'infinità dei numeri primi, e una proposizione riguardante i numeri perfetti (vedi anche l'applicazione ai numeri di Mersenne), con la quale si afferma che se 2^(n)-1 è un numero primo allora 2^(n-1)(2^(n)-1) è un numero perfetto.

Dal Libro VII degli ELEMENTI di Euclide

Definizione 1
Una unità è ciò per cui ogni singola cosa che esiste è chiamata uno

Definizione 2
Un numero è una moltitudine composta da unità

Definizione 11
Un numero primo è quello che è misurato soltanto dall'unità

Definizione 12
I numeri primi tra loro sono quelli che sono misurati soltanto dall'unità come misura comune

Definizione 13
Un numero composto è quello che è misurato da qualche numero

Definizione 22
Un numero perfetto è quello che è uguale alla somma delle proprie parti

Nel seguito con il termine numero intenderemo un numero intero positivo.
Si definisce primo ogni numero maggiore di uno che risulti divisibile soltanto per uno e per se stesso e, i numeri diversi da zero e da uno, che non sono primi, si dicono composti.
Tutti i numeri composti possono essere ottenuti, in uno ed un solo modo, come prodotto di numeri primi.
La dimostrazione di quest'ultima proposizione, nota anche come Teorema fondamentale dell'aritmetica è basata sull'algoritmo euclideo di ricerca del massimo comune divisore di due numeri.

ALGORITMO DI EUCLIDE

Premettiamo che se a e b sono due numeri tali che a=bq+r allora il massimo comune divisore tra a e b è uguale al massimo comune divisore tra b ed r cioè MCD(a,b)=MCD(b,r).
Infatti per ogni numero c che divide sia a che b risulta a=mc e b=nc per cui r=a-bq=mc-ncq=c(m-nq) cioè r è divisibile per c. Allo stesso modo si dimostra anche che ogni numero che divide sia b che r divide anche a, quindi l'insieme dei divisori di a e b coincide con quello dei divisori di b e r e da ciò segue la tesi.
Per determinare il massimo comune divisore tra due numeri a e b, supponendo a>b si procede nel modo seguente:
- si sottrae da a un multiplo di b tale che la differenza
d1=a-q1b sia minore di b
- si sottrae da b un multiplo di d1 tale che la differenza
d2=b-q2d1 sia minore di d1
- si ripete il procedimento costruendo una successione decrescente di n numeri b>d1>d2>d3>……>dn>0 con dn=dn-2-qndn-1
- il procedimento termina quando la differenza ottenuta risulta uguale a zero e il massimo comune divisore tra a e b è uguale all'ultima differenza diversa da zero così ottenuta.

Dalle uguaglianze presenti nell'algoritmo euclideo è possibile dedurre che se d=MCD(a,b) allora esistono due numeri interi h e k, positivi o negativi, tali che d=ha+kb e da questa proposizione è possibile dedurre che se un numero p è divisore del prodotto ab allora p deve essere divisore di a o di b.

SE d=MCD(a,b)

ALLORA ESISTONO DUE NUMERI INTERI H E K, POSITIVI O NEGATIVI, TALI CHE

d=ha+kb

Per dimostrare questa proposizione consideriamo le successive differenze ottenute precedentemente. Poiché d1=a-q1b , per h1=1 e k1=-q1 , si può scrivere d1=h1a+k1b.

Dall'uguaglianza successiva d2=b-q2d1 si ottiene d2=b-q2(h1a+k1b)=(-q2h1)a+(1-q2k2)b=h2a+k2b

Continuando con lo stesso procedimento si ottiene dn=hna+knb e poiché d è l'ultimo elemento della successione diverso da zero, segue la tesi.

SE P È UN DIVISORE PRIMO DI AB ALLORA DIVIDE ALMENO UNO DEI DUE FATTORI DEL PRODOTTO

Infatti se il numero primo p non dividesse a sarebbe MCD(a,p)=1 e per quanto dimostrato in precedenza si potrebbero trovare due numeri h e k tali che 1=ha+kp.Moltiplicando per b entrambi i membri dell'uguaglianza si avrebbe b=hab+kpb. Poiché per ipotesi p è divisore di ab , possiamo scrivere ab=pm, quindi b=hpm+kpb=p(hm+kb) . Dall'ultima uguaglianza risulta che p è divisore di b. Se invece avessimo supposto la non divisibilità di b per p, avremmo dimostrato che p divide a, da ciò segue la tesi.


A questo punto è possibile dimostrare il

TEOREMA FONDAMENTALE DELL'ARITMETICA

La scomposizione in fattori primi di un numero N è unica

Si proceda per assurdo e si supponga che esistano due possibili scomposizioni di N cioè

p1·p2·p3·p4·....=q1·q2·q3·q4·....=N

(i pi , così come i qi, non necessariamente sono diversi tra loro).
Piché p1 è divisore del primo membro deve essere divisore anche del secondo membro, i qi però sono primi e dunque p1 coinciderà con uno di essi, ad esempio p1=qk. È possibile allora cancellare dall'uguaglianza p1 e qk e il ragionamento può essere ripetuto per p2, p3, ecc. Alla fine tutte le p saranno semplificate e al primo membro rimarrà 1. A destra dell'uguaglianza non può rimanere nessuna delle q, poiché esse sono tutte maggiori di 1, e dunque i numeri p e q risulteranno associati a coppie e le due scomposizioni, salvo l'ordine dei fattori, risulteranno essere uguali.

E' da notare che se si considerasse l'unità tra i numeri primi questo teorema dovrebbe essere formulato in maniera diversa e sicuramente più complessa.

È chiara quindi l'importanza che si attribuisce ai numeri primi che risultano essere alla base dell'aritmetica in quanto un numero naturale,diverso da zero e da uno,o è un numero primo o è il prodotto di numeri primi.
Ma quanti sono i numeri primi?
E come è possibile individuarli?
Alla prima domanda già rispose Euclide ma alla seconda sono state date, per il momento, solo risposte parziali.

ESISTONO INFINITI NUMERI PRIMI

Con la proposizione 20 del libro IX degli Elementi, Euclide dimostrò, con un semplice ed elegante ragionamento, che i numeri primi sono infiniti.

PROPOSIZIONE 20

"I numeri primi sono più di una qualsiasi assegnata moltitudine di numeri primi"

Ragionando per assurdo supponiamo che i numeri primi siano in numero finito e siano essi p1, p2, p3,…., pn. Consideriamo il numero

N=p1·p2·p3·...·pn+1

e cioè il successivo del prodotto di tutti i numeri primi.N è maggiore di tutti i pi ma diviso per ognuno di essi da come resto 1 e quindi non ammette alcuno dei pi come divisore.Ma allora N è un numero primo, oppure se non lo è, risulta divisibile per un numero primo maggiore di tutti i numeri primi della successione data. Ciò è in contraddizione con quanto supposto e dunque la proposizione risulta vera.


Riportiamo la bella dimostrazione di Godfrey H. Hardy, dalla sua Apologia di un matematico, Garzanti, 1989.

I numeri primi o, semplicemente, i primi, sono quei numeri
(A) 2,3,5,7,11,13,17,19,23,29,…
che non possono essere scomposti in prodotto di fattori minori. Per questo 37 e 317 sono numeri primi.
I numeri primi sono il materiale attraverso cui dalla moltiplicazione, si costruiscono tutti i numeri : per esempio si ha 666=2×3×3×37. Ogni numero che non è un numero primo è divisibile per almeno un numero primo in genere, naturalmente, per molti). Dobbiamo dimostrare che esistono infiniti numeri primi e cioè che la successione (A) non termina mai.
Supponiamo invece che abbia fine e che 2,3,5,…,P rappresenti la successione completa dei numeri primi (per cui P risulta il massimo numero primo). Con questa ipotesi, consideriamo il numero Q definito dalla formula
Q = (2×3×5×…×P)+1.
E’ evidente che Q non è divisibile per nessuno dei numeri 2, 3, 5,…,P, perché il resto della divisione per ognuno di questi numeri sarà sempre 1. Ma, se Q stesso non è un numero primo, esso è divisibile per qualche numero primo ( che può essere lo stesso numero Q) che supera tutti quelli della successione. Questo contraddice l’ipotesi che non esiste un numero primo maggiore di P, e perciò la nostra ipotesi è falsa.
Questa è una dimostrazione per reductio ad absurdum, e la reductio ad absurdum , tanto amata da Euclide, è una delle più belle armi del matematico. E’ un gambetto molto più raffinato di qualsiasi gambetto degli scacchi: un giocatore di scacchi può offrire in sacrificio un pedone o anche qualche altro pezzo, ma il matematico offre la partita.

 

 

Chiunque si interessi un po' di matematica non può non apprezzare l'eleganza di questo teorema, considerato da alcuni come uno dei più belli nella storia della matematica. La sua straordinarietà sta nel fatto che, con un ragionamento comprensibile anche da un non addetto ai lavori, Euclide ottiene un risultato di notevole importanza.

Il ragionamento di Euclide non solo permette di affermare che esistono infiniti primi, ma fornisce anche un metodo per determinarne, almeno in teoria, una successione infinita. Partendo dal 2 e costruendo il successivo del prodotto dei primi n primi si ottiene o un nuovo numero primo oppure un numero composto che ha come fattore un primo diverso dai precedenti.


2
2+1=3
2*3+1=7
2*3*5+1=31
2*3*5*7+1=211
2*3*5*7*11+1=2311
2*3*5*7*11*13+1=30031=59*509 con 59 e 509 numeri primi

Ecco che ritorna allora la seconda delle domande che ci siamo posti precedentemente : esiste un algoritmo che generi tutti i numeri primi?
Molti matematici, nel corso dei secoli, si sono cimentati nella ricerca di un tale algoritmo e in alcuni casi sono state trovate, a ragione o a torto, delle formule che generano particolari classi di numeri primi, ma questo è argomento del prossimo paragrafo.