I numeri primi non saranno mai gli ultimi – Parte #1

C’è un progetto, che è in piedi circa dal ’96, per cercare i numeri di Mersenne primi sfruttando la capacità di calcolo di tutti i computer della gente che desidera partecipare.

Il principio è, direi ovviamente, quello di dividere i dati da elaborare in tanti pacchetti e di distribuirli ai volontari per mezzo di Internet. Ogni volontario si scarica il programmino che – diciamo così – fa i conti, poi quando ha finito di lavorare sul pacchetto ne spedisce i risultati e magari ne chiede un altro. Il progetto si chiama Great Internet Mersenne Prime Search (GIMPS).

Il programmino, che invece si chiama Prime95 (per Windows, MPrime per Linux, ma è senza interfaccia grafica), e timb d’aqquan iev nu uagningid, detto in altre parole, quando ero un giovane adolescente (vedere l’About), era quello d’ordinanza per fare lo stress test alla CPU overclockata.

Si facevano (e si fanno) cose strane con i sistemi di raffreddamento dei componenti del computer, cose tipo questa con l’azoto liquido (dal forum di tomshardware.co.uk),

e allora c’era bisogno di vedere un attimino se il computer era partito per Graziadiddio e poi crashava, oppure se poteva funzionare – si fa per dire – normalmente, almeno per un po’.

Per esempio qui, sempre su tomshardware.co.uk, c’è un tipico caso di modo insano di usare Prime95. In realtà credo proprio (sì, è acqua calda) che a GIMPS abbiano cavalcato alla grande questo fenomeno per diffonderlo anche tra coloro non proprio interessatissimi ai numeri primi.

In ogni caso, all’inizo del post ho menzionato i numeri di Mersenne primi. Vediamo cosa sono in modo molto amichevole, senza andare a scorrere la pagina di Wikipedia santissima; che linko quasi sempre in inglese, perché devo far vedere che sono internazionale e che sac l’ingles (cioè: che so l’inglese), anche se sono Terrone DOC (ma insomma, la Provincia di Bari si chiama o non si chiama proprio Terra di Bari?).

 

 

Partiamo dalle cose essenziali. Stiamo parlando di numeri. In particolare di numeri naturali.

I numeri naturali sono 1,\ 2,\ 3,\ 4,\ \dots,\ 34,\ 35,\ \dots, ecc. Certi cominciano con zero invece che con uno, ma io comincerò da 1, perché tanto lo zero non lo useremo. Indicheremo l’insieme dei numeri naturali con \mathbb N.

Non sono numeri naturali 2.3\ 56.0239\ 3124.4\ 0.24 ecc, non sono numeri naturali \frac{3}{4} \ \frac{37}{28}\ \frac{1}{2456} ecc, non sono numeri naturali 3+i5\ 25 -8i\ e\ \pi ecc, questo

non è un numero naturale (ah, che bello il Natale, tra un po’ arriva).

 

 

Se a e b sono numeri naturali, diremo che a divide b se e solo se esiste un numero naturale c tale che b=a*c. Per indicare questo fatto scriveremo a\mid b. Diremo in più che a è un divisore di b. Si vede facilmente che 1 divide tutti i numer naturali (prendendo c=b) e che ogni numero naturale divide se stesso (prendendo c=1). Queste sono cose credo pacifiche, senza bisogno di ulteriori spiegazioni.

 

 

Se a e b sono numeri naturali e a\mid b, ossia a divide b, ossia esiste un numero naturale c tale che b=a*c, se in più a e b sono distinti, ossia sono diversi, ossia è a\neq b, allora è a<b, cioè a è strettamente minore di b, cioè esiste un numero naturale d tale che b=a+d.

Pure questo è un fatto assai pacifico e naturale. Epperò lo possiamo pure ricavare perbene.

Infatti per ipotesi abbiamo detto che a divide b, quindi esiste un numero naturale c tale che b=a*c. Questo c non può essere 1, sennò sarebbe a=b, da b=a*1. Quindi c è strettamente maggiore di 1, è 2 oppure un numero più grande.

E’ tutto vero se scriviamo b=a*c e a=a*1; se sottraiamo a a entrambi i membri di b=a*c, otteniamo b-a=a*c-a*1, quindi, usando la gloriosa proprietà distributiva, abbiamo b-a=a*(c-1). Abbiamo visto che c è almeno 2, quindi c-1 è un numero naturale e pure a è un numero naturale, quindi b-a è un numero naturale ed è almeno 1. In conclusione abbiamo dimostrato che b-a è uguale a qualche numero naturale d, ossia risulta b-a=d, cioè, rullo di tamburi, b=d+a: b è uguale ad un numero che è a più qualcos’altro che è almeno uno ed è un numero naturale, cioè abbiamo fatto vedere che è a<b, a è strettamente minore di b.

 

 

Cosa è un numero primo? Un numero primo è un numero naturale p, diverso da 1 (è una stradiffusa convenzione), tale che per nessun numero naturale a, eccetto che per 1 e per p, risulta che a\mid p. In altre parole p ha come unici divisori 1 e p stesso.

 

 

Il bello è che se n è un numero naturale qualsiasi diverso da 1, allora n è primo oppure è prodotto di primi.

Dimostriamolo usando il principio di induzione nella forma forte, che è anche assai intuitivo.

Per n=2 la proposizione “2 è primo oppure è prodotto di primi” è vera, perché 2 è un numero primo. Per n=3 la proposizione corrispondente è vera, perché 3 è primo; per n=4 è vera, perché 4=2*2, cioè 4 è prodotto di primi. Immaginiamo o supponiamo di aver controllato per tutti i numeri naturali (diversi da 1) fino a n e che sia vera, e vediamo cosa succede a n+1. Se n+1 è primo stiamo apposto, se invece n+1 non è primo, significa che esiste un numero naturale a, diverso da 1 e da n+1, tale che a\mid n+1, ossia esiste un numero naturale c tale che n+1=a*c.

Anche c è diverso da 1 e da n+1, altrimenti avremmo n+1=a*1=a oppure avremmo n+1=a*(n+1) con a più grande di uno, cioè diremmo cose da scimuniti. Quindi sia a che c sono diversi da 1 e da n+1, in più, per la proposizione che abbiamo dimostrato poco sopra, vale a<n+1 e c<n+1. Cioè sia a che c sono numeri che abbiamo controllato, quindi per ciascuno vale la proposizione: è primo oppure è prodotto di primi. Quindi n+1, se non è primo, è prodotto di primi e in conclusione la proposizione vale pure per n+1.

Abbiamo così dimostrato che se n è un numero naturale qualsiasi diverso da 1, allora n è primo oppure è prodotto di primi.

 

 

Tornando all’inizio del discorso, un numero di Mersenne, che indichiamo con M_p, è un numero naturale del tipo M_p=2^p-1, con p numero primo qualsiasi.

Tra i numeri di Mersenne ce ne sono alcuni che sono primi. Non si sa se sono infiniti o a un certo punto non ce ne sono più (di Mersenne primi). Ciò che posso dire con certezza è che al 23 agosto 2008 il numero primo più grande conosciuto era un numero di Mersenne: M_{43112609}=2^{43112609}-1.

I numeri di Mersenne primi non si sa se sono infiniti, ma i numeri primi sì. Si può dimostrare facilmente che i numeri primi sono infiniti.

Di conseguenza anche i numeri di Mersenne sono infiniti (tutti insieme, primi e non primi).

Ma questo lo vedremo un’altra volta, se capiterà.


Annunci


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...