I numeri primi
Si consideri l’insieme dei numeri naturali\mathbb{N}.
[/math]
\mathbb{N}
[/math]
\mathbb{N_d}.
[/math]
il numero uno ed il numero stesso considerato.
Quindi, mentre un numero naturale ha infiniti multipli, sappiamo bene che l’insieme costituito da i suoi divisori è sempre finito. Se l’insieme dei divisori di un numero è un insieme paio, ossia un insieme che contiene due soli elementi, diremo che tale numero è un numero primo.
Si noti che in base a tale definizione (ed al Teorema Fondamentale dell’Aritmetica) il numero 1 non può essere considerato un numero primo.
Alcune proprietà dei numeri primi
I numeri primi sono molto importanti poiché sono alla base della struttura moltiplicativa dei numeri naturali, si pensi al Teorema Fondamentale dell’Aritmetica il quale afferma che ogni numero diverso da uno si può esprimere in un unico modo come prodotto di fattori primi.Nonostante ci siano molte teorie non è stata ancora trovata una formula generale per la determinazione dei numeri primi. Sappiamo, tramite la dimostrazione di Euclide, che l’insieme che li contiene è infinito e che non hanno un ordine preciso: esistono solo due numeri primi consecutivi, il 2 ed il 3, tutti gli altri non sono consecutivi.
Generare numeri primi
Per trovare numeri primi, esistono formule, o meglio successioni matematiche: particolari funzioni di numeri naturali, rappresentate da sequenze ordinate di numeri.Tuttavia, queste successioni, frutto di studi complessi, riescono a produrre una quantità di numeri primi limitata. Questo accade perché i numeri che vengono generati sono grandissimi (si parla di numeri con migliaia e migliaia di cifre) e superano i limiti e la potenza di calcolo dei più moderni calcolatori.
In generale, queste formule si basano sulla capacità di scegliere opportunamente l’operazione e il numero iniziale da inserire nella successione, il quale ci consente di ottenere il maggior numero di numeri primi. Questo tipo di scelta è tutt’altro che facile. Di seguito riportiamo alcune formule per ricavare numeri primi.
La formula per i numeri primi di Wright fu proposta nel 1951 dal matematico inglese Edward M. Wright. In questa formula si deve elevare
2
[/math]
1,92878:
[/math]
2^{1,92878}.
[/math]
1,92878
[/math]
Da questa prima operazione si ottiene il numero
3,807.
[/math]
2^{1,92878} = 3,807
[/math]
Del numero
3,807
[/math]
Pertanto si ottiene il numero 3, il primo numero primo dopo il 2.
Dopo questo primo passo, il procedimento va avanti, stavolta elevando il numero
2
[/math]
3,807:
[/math]
2^{3,807} = 13,999.
[/math]
In questo modo, escludendo di nuovo le cifre dopo la virgola, si ottiene il numero 13, che di nuovo è un numero primo.
Il procedimento si ripete ulteriormente, elevando il
2
[/math]
13,999:
[/math]
2^{13, 999} = 16.381
[/math]
e si ottiene 16.381, che è ancora un numero primo.
Questa formula permette di generare alcuni numeri primi, ma i numeri di trovati sono sparsi e crescono troppo rapidamente (basti pensare che il numero successivo a 16.381 è un numero con 4.932 cifre).
Una alternativa è la formula di Plouffe.
Plouffe è partito da queste formule, cercando di elaborarne una nuova, una successione che potesse produrre una maggiore quantità di numeri primi e in cui i valori non fossero così lontani uno dall’altro come nell’espressione di Wright.
Il suo obiettivo, in pratica, era quello di far sì che la successione di numeri non crescesse troppo rapidamente e che i numeri siano più piccoli (con meno cifre). Questo risultato può consentire di produrre una maggiore quantità di numeri di primi, dato che il minor numero di cifre permette all’elaboratore elettronico di generarne di più.
Il metodo, però, è simile a quello usato da Wright, dato che è una successione in cui i numeri sono elevati a potenza.
La formula di Plouffe è la seguente:
A_{n + 1} = (a_n)^ {\frac{5}{4}}.
[/math]
Il numero iniziale è numero
a_0 = 43,8046877158
[/math]
\frac{5}{4}:
[/math]
(43,8046877158)^ {\frac{5}{4}} = 112,69.
[/math]
Il numero ottenuto deve essere approssimato così da ottenere il numero primo 113.
Si ripete il procedimento tornando ad elevare il numero ottenuto non approssimato a
\frac{5}{4}:
[/math]
a_n = 112,69
[/math]
(112,69)^ {\frac{5}{4}} = 367,161
[/math]
che approssimato fornisce 367, che è un altro numero primo.
Procedendo in questo modo si producono numeri primi che non sono molto distanti uno dall’altro, per grandezza, come accade nella precedente formula di Wright.
Traducendo quanto spiegato in simboli, la Formula di Plouffe è la seguente:
A_{n + 1} = (a_n)^ {\frac{5}{4}}
[/math]
dove il numero iniziale è
a_0 = 43,804677158.
[/math]
Con questa formula si riescono a generare ben 50 numeri primi, dove il cinquantesimo numero primo ha solo 807 cifre. La quantità prodotta supera quella di ogni altro algoritmo esistente e dei soli 39 dell’attuale polinomio in uso:
n^2 + n + 41
[/math]
che si ferma a 39 perché quelli successivi sono troppo lunghi per essere calcolati. Si ottiene così la sequenza più lunga di sempre.
Un ulteriore metodo di calcolo per numeri primi è dato dalla Formula di Dirichlet.
Dirichlet in un suo studio mostrò che:
se a e b sono due numeri naturali, primi fra loro, allora la funzione lineare
f(x) = ax + b
[/math]
con massimo comun divisore MCD(a, b) = 1,
contiene infiniti numeri primi, quando l’intero x che descrive l’insieme dei numeri naturali (ossia appartiene all’insieme
\mathbb{N}
[/math]
Durante lo studio della Teoria dei Numeri, si matura subito l’idea che oltre alla forma base generatrice
2k + 1
[/math]
x = m \cdot k + c
[/math]
dove:
k, c \in \mathbb{N}
[/math]
MCD(c,m) = 1
(la costante c è coprima con m)
m è un numero primo o un prodotto di numeri primi
Esempio:
2 \cdot 3 = 6
[/math]
oppure
2 \cdot 3 \cdot 5 = 30
[/math]
oppure
2 \cdot 3 \cdot 5 \cdot 7 = 210
[/math]
oppure
2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310
[/math]
ecc.
ed x deve risultare numero primo.
Qui la costante c può essere anche negativa (esempio -1).
L’espressione
x = 2k +1,
[/math]
ad esempio, è un caso particolare di forma generatrice lineare di numeri primi generalizzata (FGLPG) con m = 2, c = 1 ed è coprimo con m.
La formula
x = 2k +1
[/math]
Particolari forme generatrici lineari di numeri primi generalizzata sono, ad esempio, le seguenti:
x = 6 \cdot k + 1
[/math]
se
c = -1
[/math]
x = 6 \cdot k - 1)
[/math]
x = 6 \cdot k + 5.
[/math]
Questo metodo permette non tanto di creare numeri primi, quanto di trovare i numeri primi di un dato insieme ordinato.
Questo metodo si attribuisce ad Eratostene di Cirene (273- 194 a.C.), matematico, astronomo e geografo greco che fu direttore della biblioteca di Alessandria. Questo metodo è conosciuto come crivello di Eratostene e permette di ricercare i numeri primi minori di un numero naturale assegnato.Tale metodo consiste nello scrivere tutti i numeri naturale maggiori di 1 e minori del numero fissato e nel cancellare, successivamente:
- i multipli di 2, escluso il 2;
- i multipli di 3 escluso il 3;
- i multipli di 5, escluso il 5;
- i multipli di 7, escluso il 7;
- e così via considerando, in ordine, la successione dei numeri primi.
\mathbb{N}
[/math]
In generale, per trovare tutti i numeri primi minori di un numero N assegnato, è sufficiente realizzare un crivello per i numeri primi minori o uguali a
\sqrt{N}.
[/math]
Questo ci fornisce un metodo per trovare i numeri primi minori di un numero dato. Questo metodo si continua ad usare ancora oggi per trovare numeri primi piccoli, minori di diecimilamilioni.
Per la spiegazione e l'illustrazione dell'algoritmo utilizzato per la generazione di numeri primi e la conseguente realizzazione del relativo programma si rimanda alla consultazione del seguente articolo: Creazione e Verifica di numeri primi relativamente grandi
Scarica il programma per generare numeri primi
per ulteriori approfondimenti sui numeri primi vedi anche qua
