Scritto da Maria Rispoli Domenica 09 Gennaio 2011 12:58...

I numeri primi

Scritto da Maria RispoliDomenica 09 Gennaio 2011 12:58 - Ultimo aggiornamento Domenica 13 Marzo 2011 20:09

Un numero naturale n (eccetto lo 0 e l’1), che ha come divisori solo 1 e se stesso, è detto numero primo.

Più precisamente, un numero primo è un numero intero p, maggiore di 1, che non ammettedivisori diversi da se stesso e da 1.

Euclide nel suo Libro VII de Gli Elementi afferma:

“numero primo è quello che è misurato soltanto dall’unità”.

In altre parole, nella sua definizione di numero primo Euclide ammette come unico divisorel’unità, mentre non contempla la divisibilità del numero per se stesso.

I più piccoli numeri primi sono:

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

L’importanza della classe dei numeri primi è espressa dal seguente:

Teorema fondamentale dell’aritmetica

“Ogni numero intero maggiore di 1 è scomponibile in un unico modo (a meno dell’ordine in cuicompaiono i fattori) come un prodotto di numeri primi positivi”.

1 / 26

I numeri primi


Pertanto, se un numero non è primo, può essere scomposto in un prodotto di fattori primi. Unnumero intero (diverso da 0 o da 1) che non sia primo si dice numero composto [1] .

Euclide, nella proposizione 20 del Libro IX de Gli Elementi, opera composta intorno al 300 a.C.,afferma che la serie dei numeri interi primi è illimitata:

“I numeri primi sono più di qualsiasi assegnata moltitudine di numeri”.

La dimostrazione è indiretta; si mostra infatti che se si assume l’ipotesi dell’esistenza di unnumero finito di interi si perviene ad una contraddizione.

Dimostrazione:

Sia P il prodotto di tutti i numeri primi, che si assumono essere di numero finito, e si consideri ilnumero N=P+1.

Ora, N non può essere un numero primo, giacché ciò contraddirebbe l’ipotesi secondo cui Pera il prodotto di tutti i numeri primi.

Pertanto N è un numero composto e vi deve essere qualche numero primo p che lo misura.

Ma p non può essere nessuno dei fattori primi di P, perché altrimenti dovrebbe essere un

2 / 26

#_ftn1

I numeri primi


fattore di 1.

Se un numero p fosse fattore di N e di P sarebbe fattore anche della differenza N-P, infattibasta metterlo in evidenza e pertanto sarebbe fattore di:

N-P=1.

Pertanto p deve essere un numero primo diverso da tutti quelli che costituiscono il prodotto P;dunque, l’ipotesi che Pera il prodotto di tutti i numeri primi deve essere falsa[2].

C’è, inoltre, una dimostrazione di Euclide presente nell’opera Gli Elementi.

Dimostrazione:

“Siano A, B, C i numeri primi proposti; dico che esistono numeri primi in maggior numero che A,B, C (cioè che ne esiste almeno un altro, oltre ad A, B, C).

Infatti, si prenda il minimo comune multiplo di A, B, C (VII, 36), e sia esso K; si aggiunga a Kl’unità U. Ora, il numero K+U o è primo o non lo è.

Dapprima, sia un numero primo; si sono dunque trovati i numeri primi A, B, C, K+U che sono inmaggior numero che A, B, C.

Ma sia adesso il caso in cui, per ipotesi, K+U non è primo, per cui esso è diviso da un numero

3 / 26

#_ftn2

I numeri primi


primo (VII, 31).

Sia diviso dal numero primo D; dico che D non è uguale a nessuno dei numeri A, B, C.

Infatti, se possibile, sia uguale (a qualcuno di essi).Ma A, B, C dividono K; perciò anche Ddividerebbe K. Ma D divide pure K+U; ossia D dividerebbe, pur essendo un numero, anchel’unità U che rimane di K+U (ossia dividerebbe anche la differenza fra i due numeri consecutiviK+U e K, vale a dire, pur essendo un numero, dividerebbe l’unità U): il che è per assurdo.Quindi D non è uguale a nessuno dei numeri A, B, C. Ed è, per ipotesi, primo.

Dunque si sono trovati numeri primi, cioè A, B, C, D, più numerosi di quanti numeri primi sisiano proposti, cioè A, B, C”.

Vale a dire, siano dati i numeri primi a, b, c. Dico che esiste almeno un quarto numero primo.

Per raggiungere tale scopo si moltiplicano tra loro i tre numeri dati e si aggiunge una unità, siottiene così il numero:

d= abc+1.

Se d è primo , esso è un altro numero primo esistente oltre ad a, b, c. Quindi è stata dimostratal’esistenza di un quarto numero primo.

Se d non è primo, esso ammette almeno un divisore primo (diverso da 1) e questo divisore lochiamo h.

Dico che h è diverso da a, b, c, e quindi che esso costituisce un quarto numero primo del qualesi voleva appunto dimostrare l’esistenza.

4 / 26

I numeri primi


Se, infatti, il numero h fosse uguale ad uno dei tre numeri a, b, c, esso dividerebbe il prodotto abc. Ma avendo supposto che il numero hdivida anche:

d= abc+1,

allora h dividerebbe pure la differenza tra (abc+1) e abc, ossia l’unità:

abc + 1 – abc = 1

Abbiamo potuto affermare questo perché: se un numero x divide il numero y e divide pure ilnumero z alloradivide la differenza y-z.

Infatti:

se x divide y, sarà:

y=x*p

se x divide z, sarà:

5 / 26

I numeri primi


z=x*q

allora:

y-z=xp-xq=x(p-q)

per cui si divide la differenza y e z che è (p-q).

Ma h, numero intero diverso da 1, non può essere un divisore di 1. L’assurdo a cui si èpervenuto deriva dal fatto che si è supposto che h possa essere uguale ad a o a b o a c.

Pertanto:

h diverso da a, h diverso da b, h diverso da c,

cioè h è un quarto numero primo

E così via. Cioè si può dimostrare l’esistenza di un quinto numero primo, ecc.

Uno dei più grandi numeri primi è un numero di 909.526 cifre formato da 23.021.377.

La scoperta è opera del GIMPS, un progetto che ha collegato 4.000 computer di appassionati ditutto il mondo ognuno dei quali aveva il compito di esaminare un intervallo di numeri. Il fortunatoscopritore fu il diciannovenne Roland Clarksen, studente universitario della California cheannunciò la sua scoperta il 27 gennaio del 1998.

6 / 26

I numeri primi


Nayan Hajratwala, un giovane informatico del Michigan, ha trovato il più grande numero primooggi conosciuto 26.972.593-1. Il numero è stato ottenuto dalla formula di Mersenne 2n-1, la qualeperò non assicura che il numero generato sia primo: per provarlo occorre verificare che non èdivisibile per nessuno dei numeri precedenti, ad eccezione di 1.

Hajratwala ha fatto lavorare il suo computer per 111 giorni. Il numero record si compone di2.098.960 cifre, per scriverlo occorrono circa 1.000 pagine di un normale libro.

RICERCA DEI NUMERI PRIMI

Possiamo costruire una tavola dei numeri primi minori di un certo valore n operando nel modoseguente: dapprima scriviamo in ordine tutti i numeri interi minori di n; poi da questa tabella cancelliamo tutti i multipli di 2; successivamente eliminiamo tutti i multiplidi 3, quindi i multipli di 5 e così via fino ad aver eliminato tutti i numeri composti.

Questo procedimento, noto come il Crivello di Eratostene, tratterrà nelle sue maglie tutti inumeri primi minori di n.

Il testo più antico che dà una descrizione del crivello è quello dei neopitagorico Nicomaco diGerasa (II sec. d. C.).

Perfezionando questo metodo sono state gradualmente calcolate tavole complete di numeriprimi fino a 10.000.000, che ci forniscono una enorme quantità di dati empirici circa ladistribuzione e le proprietà dei numeri primi [3] .

Generalmente disponibile e soprattutto priva di errori è la tavola dei primi fino a 107 elaboratada D. N. Lehmer.

7 / 26

#_ftn3

I numeri primi


Non siamo ancora riusciti, invece, a determinare un criterio, ammesso che esista, e, quindi, unalgoritmo, che ci consenta di determinare a priori la distribuzione dei numeri primi all’internodell’insieme dei numeri naturali.

Infatti, uno dei più antichi problemi riguardanti i numeri primi consiste nel fatto che nessuno maiè riuscito a trovare una formula o un sistema che permettano di determinare se un numero èprimo o no.

Sono stati fatti dei tentativi per trovare delle semplici formule aritmetiche che diano soltantonumeri primi, anche se magari non tutti.

Eulero nel 1751 afferma:

“I matematici hanno provato invano finora a scoprire qualche ordine nella successione deinumeri primi e si ha diritto a credere che è un mistero che lo spirito umano non saprà penetrare.Per convincersene, basta gettare gli occhi sulle tavole dei numeri primi, che alcuni si sono datila pena di costruire fino a centomila, e ci si accorgerà subito che non vi regna alcun ordine oregola. Questa circostanza appare tanto più sorprendente quando si rifletta sul fatto chel’Aritmetica ci fornisce regole sicure con le quali si è in grado di prolungare la successione di talinumeri fin dove si vuole, senza però lasciare la minima traccia di qualche ordine [4] ”.

Un modo molto semplice per ottenere dei numeri primi sempre più grandi è descritto inseguito.

Tali numeri si ottengono aumentando di 1 successivamente i prodotti di numeri primiconsecutivi a partire da 2.

Si ha così:

2+1=3

8 / 26

#_ftn4

I numeri primi


2*3+1=7

2*3*5+1=31

2*3*5*7+1=211

…………………….

I numeri 3, 7, 31, 211, … sono numeri primi.

E’ chiaro però che, con il procedimento indicato, non si ottengono tutti i numeri primi compresifra 2 ed un numero assegnato; per esempio, non si ottengono i numeri 5, 11, ecc.

Fermat formulò la famosa ipotesi che tutti i numeri della forma:

con n numero naturale (o intero positivo), siano primi.

Questo tipo di numeri primi vengono chiamati primi di Fermat perché nel 1640 Fermat scrisse aun corrispondente scientifico, il padre (dell’ordine dei minimi) Marin Mersenne, di avere

9 / 26

I numeri primi


scoperto una formula che è quella riportata sopra, mediante la quale si ottenevano solo numeriprimi, benché egli dichiarasse di non averne alcuna dimostrazione [5] .

In effetti per n = 1, 2, 3, 4 si ottengono i numeri:

tutti primi.

Nel 1732 Eulero dimostrò che la congettura di Fermat era falsa, infatti scoprì che:

non è primo.

Nel 1880 F. Landry riuscì a dimostrare che anche F(6) è composto; e nel 1975 Brillhart eMorrison dimostrarono che anche F(7) è composto.

10 / 26

#_ftn5

I numeri primi


Nel 1981 Richard P. Brent e John Pollard sono riusciti a scomporre l’enorme numero F(8)dimostrando che non è primo.

Attualmente si sono fattorizzati tutti i numeri primi di Fermat fino a F(23), ma non si sa ancorase il numero di Fermat F(24) con le sue 5.050.446 cifre sia o no primo [6] .

Più tardi, ricorrendo, date le insormontabili difficoltà del calcolo diretto, a metodi della teoria deinumeri ogni volta più complicati, si trovò che tranne i primi quattro gli altri numeri di Fermatsono composti.

Un’altra notevole espressione che dà luogo a molti numeri primi è:

f(n) = n2 – n + 41

Per n = 1, 2, 3, …, 40, è primo; ma, per n = 41, si ha un numero non primo: infatti 1.681 = 412

= 41 * 41.

Anche l’espressione

n2 – 79n +1601

dà luogo a numeri primi per ogni n fino a 79, ma per n = 80 non si ottiene un numero primo [7] .

Eulero propose anche alcuni algoritmi che davano come risultato dei numeri primi. Due di questisono:

11 / 26

#_ftn6

#_ftn7

I numeri primi


n2 + n + 41

n2 + n + 17

ma questi algoritmi come quelli mostrati in precedenza non forniscono tutti i numeri primi.

Altri numeri primi sono i numeri di Mersenne:

Mp = 2p – 1

con p primo, che intervengono nella teoria dei numeri perfetti.

I numeri primi di questa forma si dicono primi di Mersenne per il fatto che vennero discussisistematicamente nei Cogitata physica mathematica (Paris 1644) del padre Marin Mersenne [8].

Uno dei più grandi interi riconosciuti come primo è (2127 – 1) la cui rappresentazione decimaleha 39 cifre.

DISTRIBUZIONE MEDIA DEI NUMERI PRIMI

Il passo decisivo, nella ricerca di una legge da cui dipenda la distribuzione dei numeri primi, fucompiuto quando i matematici rinunciarono ai tentativi di trovare una formula matematicasemplice che rappresentasse tutti i numeri primi o desse il numero esatto dei numeri primicontenuti nei primi n numeri interi, e cercarono di chiarire invece la distribuzione media deinumeri primi tra i numeri interi.

12 / 26

#_ftn8

I numeri primi


Per ogni numero intero n indichiamo con An il numero di numeri primi contenuto tra gli interi 1,2, 3, …, n.

Sottolineiamo i numeri primi nella successione formata dai primi numeri interi:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 …

possiamo calcolare alcuni dei valori di An:

A1 = 0,

A2 = 1,

A3 = A4 = 2,

A5 = A6 = 3,

A7 = A8 = A9 = A10 = 4,

A11 = A12 = A13 = A14 = A15 = A16 = 6,

13 / 26

I numeri primi


A17 = A18 = 7,

A19 = 8,

ecc.

Ora prendiamo una successione di valori di n che cresca indefinitamente, per esempio

n = 10, 102, 103, 104, …,

vediamo che i corrispondenti An:

A10, A102, A103, A104, …,

crescono oltre ogni limite (anche se più lentamente).

Poiché esistono infiniti numeri primi, presto o tardi i valori di An supereranno qualunque numerofinito.

La densità dei numeri primi compresi tra i primi n numeri interi è data dal rapporto An/n, e

14 / 26

I numeri primi


questi valori possono essere calcolati utilizzando una tavola di numeri primi per valori di nopportunamente grandi.

n

A n / n

10 3

10 6

10 9

...

0,168

0,078498

0,050847478

15 / 26

I numeri primi


.............

La distribuzione dei singoli numeri primi tra gli interi è molto irregolare.

Ma quest’irregolarità individuale o, come si usa dire, in piccolo, sparisce se si concentral’attenzione sulla distribuzione media dei numeri primi data dal rapporto An/n. La semplicelegge che governa il comportamento di questo rapporto è una delle scoperte più notevoli di tuttala matematica.

Dopo uno studio empirico delle tavole dei numeri primi, Gauss osservò che il rapporto An/n èapprossimativamente uguale a 1/logn, e che quest’approssimazione migliora con il crescere di n.

Allora per stabilire il teorema dei numeri primi dobbiamo definire il logaritmo naturale di unnumero intero n.

A questo scopo consideriamo due assi perpendicolari nel piano e l’insieme di tutti i punti delpiano per i quali il prodotto delle distanze x e y da questi assi è uguale ad 1.

Questo luogo geometrico, in coordinate x e y, è un’iperbole equilatera, ed è definitodall’equazione xy = 1.

Definiamo il logn come l’area della figura seguente, limitata dall’iperbole, dall’asse x e dalle duerette x = 1

16 / 26

I numeri primi


e x =n

(che sono parallele all’asse y).

Il rapporto An/n è approssimativamente uguale a 1/logn e il grado d’approssimazione è dato dalrapporto

i cui valori, per n = 1.000, 1.000.000, 1.000.000.000, sono dati nella seguente tavola:

n

A n /n

1/logn

17 / 26

I numeri primi


10 3

10 6

10 9

…

0,168

0,078498

0,050847478

.....................

18 / 26

I numeri primi


0,145

0,072382

0,048254942

.....................

1,159

1,084

1,053

............

Sulla base di questa verifica empirica Gauss formulò l’ipotesi che il rapporto An/n è

19 / 26

I numeri primi


asintoticamente uguale a 1/logn.

Con questo intendeva che se si considera una successione di valori di n sempre crescente, peresempio n uguale a10, 10 2, 103,104

, …, allora il rapporto:

calcolato per questi successivi valori di n, si andrà via via avvicinando a 1, e che la differenzatra 1 e questo rapporto può divenire piccola a piacere per valori di nsufficientemente grandi[9].

Dunque se s’indica con il numero dei numeri primi fino a n vale che:

E’ una scoperta molto notevole che il comportamento medio della distribuzione dei numeriprimi possa essere descritto dalla funzione logaritmica, poiché è sorprendente che due concettimatematici apparentemente così lontani siano in realtà connessi tra loro.

Quest’ipotesi di Gauss fu dimostrata da Hadamard a Parigi e de La Vallée Poussin a Lovanio,indipendentemente nel 1896.

20 / 26

#_ftn9

I numeri primi


Se rappresentiamo la distribuzione dei numeri primi su un grafico, disponendo in ascissa lasequenza dei numeri ordinali ed in ordinata il rispettivo numero primo, otteniamo la seguentecurva:

Nel grafico, non considerando la parte iniziale fino a n = 20, la linea di tendenza sembra essereuna retta o un’iperbole con una curvatura molto ampia.

Sembrerebbe quindi facile determinare un algoritmo che permetta di calcolare un numeroprimo, in funzione di n.

In realtà qualsiasi formula che noi possiamo definire, non darà mai un risultato esatto per tutti inumeri primi, come se la regola che li unisce tendesse a sfuggire ad ogni logica matematica.

CONGETTURE SUI NUMERI PRIMI

Mentre il problema della distribuzione media dei numeri primi è stato soddisfacentementerisolto, vi sono molte altre ipotesi confermate da tutte le verifiche empiriche, ma di cui non si èancora dimostrata la validità.

Una di queste è la congettura di Goldbach (1690-1764) proposta in una lettera ad Eulero nel1742:

21 / 26

I numeri primi


“tutti i numeri pari ad eccezione di 2 sono la somma di due numeri primi”.

Fino a poco tempo fa una dimostrazione della congettura di Goldbach sembravairraggiungibile; oggi non appare più tale.

Un risultato importante e inatteso, fu raggiunto nel 1931 da un giovane matematico russo allorasconosciuto, Schnirelmann (1905-1938), il quale dimostrò che:

“ogni numero intero positivo può essere rappresentato come somma di non più di 300.000primi”.

Questo è un primo passo verso la dimostrazione della congettura di Goldbach.

Più recentemente nel 1937 il matematico russo I. M. Vinogradov, usando metodi dovuti aHardy, Littlewood, e al loro grande collaboratore indiano Ramanujan, è riuscito a ridurre ilnumero da 300.000 a 4.

Ci si è molto avvicinati ad una soluzione del problema di Goldbach.

Tutt’altro che vicino ad una soluzione è quest’altro problema.

Congettura dei primi gemelli.

“I numeri primi si presentano frequentemente in coppie della forma p e p+2, come 3 e 5, 11 e

22 / 26

I numeri primi


13, 29 e 31 ecc”.

Si ritiene corretta l’ipotesi che esistano infinite coppie fatte così, ma finora non si è compiuto ilminimo passo verso una dimostrazione [10] .

Osserviamo anche che:

“Un numero dispari maggiore di 5 è sempre somma di tre numeri primi”.

“Se consideriamo un numero e il suo doppio fra questi due numeri c’è sicuramente un numeroprimo”.

“I numeri primi sono tutti dispari tranne il 2”.

C’è anche la congettura di Opperman.

“Fra il quadrato di un numero qualsiasi e la differenza tra il quadrato dello stesso numero più (omeno) il numero stesso, c’è sempre un numero primo”.

Ad esempio:

25 - (25-5) = 5

49 - ( 49 + 7) = 7

23 / 26

#_ftn10

I numeri primi


121 - (121-11) = 11

400 - (400-20) = 20

E la congettura di Brocard:

“Fra i quadrati di due numeri primi consecutivi maggiori di 2, ci sono sempre almeno 4 numeriprimi”.

Ad esempio tra (13)2 e (11)2 ci sono 127, 131, 137, 139, 149, 151, 157, 163, 167.

Una procedura che consente di stabilire se un numero n dato in input è primo, considera unavariabile c che è inizializzata al valore2, questa variabile è incrementata all’interno di un ciclo in cui si verifica se il valore di cè un divisore n,se lo è e il suo valore è minore di nallora il numero nnon è un numero primo.

Osserviamo che nella ricerca dei numeri primi non è necessario effettuare la verifica fino alvalore n , ma basterà per ogni numero n verificare se tutti gli interi da 2 alla radice quadrata di nsono divisori del numero stesso.

24 / 26

I numeri primi


Infatti prima di 2 non troviamo numeri che dividono n, e i numeri maggiori di sono necessariamente associati ad un fattore che si sarebbe già dovuto trovare come divisoredi n, perché:

* = n

e, se prendiamo un numero x > l’altro fattore y deve essere minore di . Quindi possiamo fermarci a verificare fino al valore .

[1] R. Courant, H. Robbins, Che cos’è la Matematica?, p.59, Bollati Boringhieri.

[2] C. B. Boyer, Storia della Matematica, Milano, Mondadori.

[3] R. Courant, H. Robbins, cit., pag.63.

[4] P. Nastasi, A. Scimone, Da Euclide a Goldbach Storie di Uomini e Numeri, Sigma.

[5] P. Nastasi, A. Scimone, Da Euclide a Goldbach Storie di Uomini e Numeri, Signa.

[6] P. Nastasi, A. Scimone, Da Euclide a Goldbach Storie di Uomini e Numeri, Sigma.

[7] R. Courant, H. Robbins, cit., p.63,64.

25 / 26

#_ftnref1

#_ftnref2

#_ftnref3

#_ftnref4

#_ftnref5

#_ftnref6

#_ftnref7

I numeri primi


[8] P. Nastasi, A. Scimone, Da Euclide a Goldbach Storie di uomini e numeri, Sigma.

[9] R. Courant, H. Robbins, cit., p.65-68.

[10] R. Courant, H. Robbins, cit., pag. 68-70.

26 / 26

#_ftnref8

#_ftnref9

#_ftnref10

Scritto da Maria Rispoli Domenica 09 Gennaio 2011 12:58...

Documents

Transcript of Scritto da Maria Rispoli Domenica 09 Gennaio 2011 12:58...