Don't take life too seriously: it's just a temporary situation

Mersenne (numeri di)

Teoria dei numeri 

Indice

  1. 1. Pagina principale
  2. 2. Primi di Mersenne
  3. 3. Proprietà dei primi di Mersenne

Tra i numeri di Mersenne i numeri primi, detti “primi di Mersenne” rivestono particolare importanza, per le loro connessioni con i numeri perfetti. Infatti, tutti i numeri perfetti pari hanno la forma 2p – 1Mp (Eulero).

 

Nichomacus aveva indicato, circa nel 100 d.C., che per p = 2, 3, 5, e 7 si ottengono numeri primi, producendo il primo elenco noto di primi di Mersenne.

 

Il quinto, sesto e settimo numero primo di Mersenne furono scoperti da Ismail ibn Ibrahim ibn Fallus (1194 – 1239), che diede un elenco dei primi 10, solo 7 dei quali corretti, ma il suo lavoro fu ignorato e tali numeri furono riscoperti secoli dopo. Di conseguenza la scoperta del quinto primo di Mersenne è comunemente attribuita a un anonimo fiorentino (1456) e sesto e settimo sono attribuiti a Cataldi (1603), sebbene nel 1977 sia stato scoperto che il sesto è citato in un commentario di J. Scheybl (1555) a una traduzione del testo di Euclide.

C’è però un punto a favore dei nostri matematici: l’elenco di ibn Fallus conteneva anche 3 errori, ossia citava come primi 3 numeri di Mersenne che non lo sono, quindi potrebbe essere stato in parte stilato in base a congetture, mentre Cataldì dimostrò effettivamente che M17 e M19 sono primi, anche se non seppe resistere alla tentazione di allungare l’elenco con numeri errati, probabilmente trovati in base a qualche congettura (e ovviamente senza dare dimostrazioni).

 

Prima del ’500 molti ritenevano che tutti i numeri della forma 2p – 1 fossero primi, se p è primo. In effetti, Mp può essere primo solo se p è primo, ma il fatto che p lo sia non rende necessariamente primo Mp; la prima eccezione è 211 – 1 = 2047 = 23 • 89 e dai dati disponibili sembrerebbe che i primi per i quali Mp è primo siano solo una sparuta minoranza: solo 42 sui primi 1622440.

Il merito d’aver notato che per p = 11 si ottiene un numero composto è solitamente attribuito a Hudalricus Regius (1536), che pubblicò la scomposizione, ma un manoscritto del 1456 riporta correttamente i primi 5 primi di Mersenne, saltando 2047, quindi probabilmente l’eccezione era già stata notata. Del resto per trovare la scomposizione di 2047 bastano pochi minuti con carta e penna.

 

Il matematico bolognese Pietro Antonio Cataldi (1548 – 1626) dimostrò che Mp può essere primo solo se p è primo e allungò l’elenco dei primi di Mersenne conosciuti, aggiungendo M17 e M19; in seguito aggiunse M31, ma anche, erroneamente, M23, M29 e M37. I primi due errori furono trovati da Fermat nel 1640, mentre Eulero fu il primo a trovare un fattore di M37.

 

Mersenne nel 1644 affermò nella prefazione a Cogitata Physico Mathematica, (Riflessioni fisico-matematiche) del 1644 che i numeri ottenuti per p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, e per nessun altro valore minore di 257, sono primi (v. congettura di Mersenne). Mersenne però ammise onestamente di non poter dimostrare la sua affermazione e doveva nutrire qualche dubbio, perché scrisse: “Tutto il tempo del mondo non sarebbe sufficiente a determinare se sono primi”, firmando così una delle previsioni meno azzeccate della storia della matematica; la verifica arrivò, infatti, in poco meno di tre secoli, sempre a mano, e oggi un calcolatore può farcela in una frazione di secondo. L’affermazione, come tante altre, dimostra che “infinito” è un tempo troppo lungo per azzardare previsioni.

L’elenco dei primi, a lungo controverso, ma ritenuto probabilmente corretto, fece comunque scalpore: a quei tempi nessuno aveva dimostrato nulla per p > 19.

Come si vede dalla tabella seguente, omise tre valori (p = 61, 89, 107) e incluse erroneamente nell’elenco due primi (67 e 257), tuttavia la sua affermazione, con 5 soli errori nei primi 55 numeri primi, è sorprendentemente vicina al vero, in un’epoca nella quale non era conosciuto alcun metodo efficiente per determinare se numeri così grandi fossero primi o meno.

Solo 128 anni dopo Eulero dimostrò che effettivamente 231 – 1 è primo e 2127 – 1 (che è un numero di 39 cifre) dovette attendere un altro secolo (Lucas, 1876).

Probabilmente questo resterà per sempre il più grande numero dimostrato primo a mano. Osservate che mi cautelo, smussando con l’avverbio “probabilmente” gli spigoli di questo rischioso “per sempre”.

Nel 1876 Lucas evidenziò il primo errore di Mersenne dimostrando che M67 non è primo.

E’ probabile che Mersenne ritenesse che Mp e primo se e solo se p è un primo della forma 22n + 1, 22n + 1 – 1, o 22n ± 3, o almeno così asseriva Lucas, mentre Tannery attribuiva questa affermazione a Frenicle o Fermat; in ogni caso le eccezioni come 67 e 89 non mancano e la congettura era motivata solo dagli scarsi dati certi disponibili nel XVII secolo.

 

La ricerca dei primi di Mersenne ha stimolato lo sviluppo di metodi per stabilire se un numero di questa forma è primo o meno.

All’inizio si provavano semplicemente tutti i primi sino alla sua radice quadrata, ma questo metodo diventa rapidamente poco pratico (soprattutto lavorando a mano). Per dimostrare che M19 è primo, Cataldi provò a dividerlo per tutti i 127 primi dispari minori della sua radice quadrata.

 

Il primo progresso si deve a Fermat, che affermò che se Mp non è primo, i suoi fattori primi hanno la forma 2kp + 1 e dimostrò che M23 e M37 sono primi, correggendo due errori di Cataldi. L’affermazione di Fermat deriva in modo abbastanza semplice dal suo “piccolo” teorema, ma il matematico francese, per la disperazione dei suoi colleghi, era avaro di dettagli, quindi la scoperta viene comunemente attribuita a Eulero, che pubblicò una dimostrazione precisa e poté provare che M29 è composto (1738) e M31 è primo (1732) esaminando poco più che 150 fattori primi di quella forma (la tabella pubblicata da Brancker nel 1738 conteneva tutti i primi sino a 100000).

Eulero fece anche due affermazioni errate, dichiarando primi M41 e M47, ma corresse l’errore nel 1753.

 

Sfruttando il fatto che gli eventuali divisori primi devono anche essere della forma 8k ± 1, si possono dimezzare i primi candidati da provare, ma è chiaro che il metodo di esaminare i possibili divisori primi richiedeva uno sforzo enorme per verificare se numeri come M61 siano primi, anche per la mancanza di adeguate tabelle di primi.

 

L’ultimo numero di Mersenne scomposto a mano con questa tecnica fu M67: Lucas aveva già dimostrato nel 1886 che è composto, ma trovarne i fattori era, all’epoca, un lavoro estenuante.

Nell’ottobre del 1903 Frank N. Cole (1861 – 1926) tenne a un incontro dell’American Mathematical Society la prima, e sinora unica, conferenza di matematica senza parole: quando arrivò il suo turno si alzò, andò alla lavagna e calcolò 267 – 1, poi calcolò 193707721 • 761838257287, ottenendo lo stesso numero, quindi tornò a sedersi, mentre la sala applaudiva a lungo. Cole impiegò le domeniche di 20 anni per arrivare a questo risultato.

 

Per trovare altri primi di Mersenne si dovette aspettare oltre un secolo, sino a quando cioè Lucas dimostrò che esiste un test di primalità relativamente semplice, valido solo per essi. Si inizia con S0 = 4 e si calcola Formula per il calcolo della ricorrenza, quindi S1 = 14, S2 = 194 ecc.: Mp è primo se e solo se divide Sp – 2.

I valori della sequenza sono dati da Formula per il calcolo di S(n), ma il metodo più semplice di applicare il test è il calcolo ripetuto di quadrati modulo Mp.

Lucas si servì della sua tecnica per dimostrare che M67 non è primo, contrariamente a quando affermato da Mersenne, e che M127 lo è.

Da allora i numeri di Mersenne rappresentano candidati ideali per la caccia primi enormi, e in effetti, il record per il maggior primo noto nella storia è stato detenuto da un numero di Mersenne, con pochissime eccezioni (v. numeri primi).

 

Quando Ivan Mikheevich Pervushin (Perm, Russia, 21/1/1827 – Mehonskoe, Russia, 29/6/1900) dimostrò che M61 è primo (1883) non pochi (soprattutto in Francia) sostennero che l’elenco di Mersenne era corretto, ma che c’era stato un errore di trascrizione, che aveva fatto confondere M67 con M61. I sostenitori di Mersenne si dovettero però arrendere all’evidenza quando furono scoperti gli altri errori, in particolare quando R.E. Powers dimostro che M89 è primo (1911).

L’ultimo errore fu trovato da Kraitchik che dimostrò che M257 è composto (1922).

 

Nel 1932 Derrick H. Lehmer e sua moglie, Emma Trotskaia Lehmer, raffinarono il metodo di Lucas, rendendo l’esame più veloce.

 

Nel 1951 Max Mewmann e Alan Turing intrapresero la prima ricerca sistematica di nuovi primi di Mersenne col test di Lucas – Lehmer, utilizzando un calcolatore elettronico. Esaminarono tutti i primi fino a 509, senza trovare nuovi primi di Mersenne. Sfortuna, perché avrebbero avuto successo col primo immediatamente seguente: 521.

 

Sono stati verificati due volte, con calcolatori differenti, tutti i primi sino a 37000000; quelli sino a 68000000 sono stati verificati almeno una volta. Esiste quindi la remotissima possibilità che vi siano altri primi di Mersenne tra il 45° e il 49°. E una più concreta possibilità che ve ne siano altri minori dell’ultimo.

 

La tabella seguente riporta i valori noti di p tali che Mp sia primo.

n

p

Scopritore

1

2

 

2

3

 

3

5

 

4

7

 

5

13

Ismail ibn Ibrahim ibn Fallus (circa 1230)

6

17

Ismail ibn Ibrahim ibn Fallus (circa 1230), Pietro Cataldi (1588)

7

19

Ismail ibn Ibrahim ibn Fallus (circa 1230), Pietro Cataldi (1588)

8

31

Eulero (1750)

9

61

Ivan Mikheevich Pervushin (11/1883)

10

89

Ralph Ernest Powers (6/1911)

11

107

Ralph Ernest Powers (1/6/1914)

12

127

Édouard Lucas (10/1/1876)

13

521

Raphael Mitchell Robinson (30/1/1952)

14

607

Raphael Mitchell Robinson (30/1/1952)

15

1279

Raphael Mitchell Robinson (25/6/1952)

16

2203

Raphael Mitchell Robinson (7/10/1952)

17

2281

Raphael Mitchell Robinson (9/10/1952)

18

3217

Hans Riesel (8/9/1957)

19

4253

Alexander Hurwitz (3/11/1961)

20

4423

Alexander Hurwitz (3/11/1961)

21

9689

Donald Bruce Gillies (11/5/1963)

22

9941

Donald Bruce Gillies (16/5/1963)

23

11213

Donald Bruce Gillies (2/6/1963)

24

19937

Bryant Tuckerman (4/3/1971)

25

21701

Laura Nickel e Landon Curt Noll (30/10/1978)

26

23209

Landon Curt Noll (9/2/1979)

27

44497

Harry Lewis Nelson e David Slowinski (8/4/1979)

28

86243

David Slowinski (25/9/1982)

29

110503

Water Colquitt e Luther Welsh (28/1/1988)

30

132049

David Slowinski (20/9/1983)

31

216091

David Slowinski (1/9/1985)

32

756839

David Slowinski e Paul Gage (17/2/1992)

33

859433

David Slowinski e Paul Gage (4/1/1994)

34

1257787

David Slowinski e Paul Gage (1/9/1996)

35

1398269

Joel Armengaud (13/11/1996)

36

2976221

Gordon Spence (24/8/1997)

37

3021377

Roland Clarkson (27/1/1998)

38

6972593

Nayan Hajratwala (1/6/1999)

39

13466917

Michael Cameron (14/11/2001)

40

20996011

Michael Shafer (17/11/2003)

41

24036583

Josh Findley (15/5/2004)

42

25964951

Marin Novak (18/2/2005)

43

30402457

Curtis Cooper e Steven Boone (15/12/2005)

44

32582657

Curtis Cooper e Steven Boone (11/9/2006)

45

37156667

Hans-Michael Elvenich (6/9/2008)

46?

42643801

Odd Magnar Strindmo (12/4/2009)

47?

43112609

Edson Smith (23/8/2008)

48?

57885161

Curtis Cooper (25/1/2013)

49?

74207281

Curtis Cooper (7/1/2016)

 

Per dare un’idea delle dimensioni dell’ultimo primo della tabella, basti dire che stampato con 75 cifre per riga e 50 righe per pagina, occuperebbe un volume di 5957 pagine.

 

La tabella seguente riporta i primi 10 primi di Mersenne.

n

p

Mp

1

2

3

2

3

7

3

5

31

4

7

127

5

13

8191

6

17

131071

7

19

524287

8

31

2147483647

9

61

2305843009213693951

10

89

618970019642690137449562111

 

I primi di Mersenne sono stati scoperti in ordine crescente, tranne M127, dimostrato primo prima di M61, M89 e M107, e M43112609, scoperto prima di M42643801. Si discute, a livello puramente filosofico, se vi sia stata un’altra eccezione: quando il calcolatore SWAC scoprì che M521 e M607 sono primi, la macchina li scoprì e li scrisse in ordine, ma quando i programmatori andarono a leggere il tabulato videro per primo M607, e solo dopo attimi di esultanza e felicitazioni reciproche, controllando il resto della stampa, videro l’altro, quindi gli esseri umani, scoprirono i due primi in ordine inverso.

 

G. Woltman lanciò anni fa un’iniziativa sulla rete per la caccia ai primi di Mersenne, chiamata GIMPS (per Great Internet Mersenne Primes Search: ricerca di grandi primi di Mersenne via Internet).

Chiunque voglia mettere a disposizione alcune ore altrimenti inutilizzate del proprio calcolatore, può collegarsi e scaricare gratuitamente il programma. Il programma può girare sfruttando i tempi morti, di notte o quando il proprietario non lo usa; occasionalmente comunica via Internet i risultati e chiede un altro primo da verificare alla sede centrale, che tiene conto delle ricerche in corso e riassegna nuovi compiti ai volontari.

Quando viene scoperto un nuovo primo, una verifica finale eseguita dagli organizzatori su una macchina differente controlla che non si tratti di un falso allarme.

La disponibilità di migliaia di macchine, anche se non di enorme potenza, ha già dato i suoi frutti, sotto forma della scoperta dei primi di Mersenne dal trentacinquesimo in poi. Gli interessati possono trovare tutti i dettagli sul sito http://www.mersenne.org/prime.htm.

 

Trovo molto appropriato che all’asteroide con numero di catalogo 8191 (scoperto da Eric Walter Elst all’osservatorio La Silla il 20/8/1993) sia stato dato il nome “Mersenne”: dopotutto 8191 è un primo di Mersenne.

Bibliografia

  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
  • Bach, Eric;  Shallit, Jeffrey;  Algorithmic Number Theory, MIT Press, 1997.
  • Bressanini, Dario;  "In 200000 per scoprire un numero primo" in Le Scienze, Milano, n. 425, gennaio 2004, pag. 22 – 23.
  • Eves, Howard W.;  Mathematical Circles, Mathematical Association of America, vol. III, 2003 -

    Una stupenda raccolta di aneddoti a sfondo matematico, pubblicati inizialmente con i titoli Mathematical Circles Adieu (Prindle, Weber and Schmidt Inc., 1977) e Return to Mathematical Circles (Prindle, Weber and Schmidt Inc., 1988).

  • Giblin, Peter;  Primes and Programming, Cambridge University Press, 1993.
  • Shanks, Daniel;  Solved and Unsolved Problems in Number Theory, New York, Chelsea Publishing Co, V ediz., 2002 -

    La prima edizione risale al 2002; il grande successo del libro ha motivato le successive edizioni, ampliate e rivedute alla luce di progressi fatti negli anni.

  • Stewart, Ian;  Professor Stewart’s Cabinet of Mathematical Curiosities, Basic Books, 2009.
  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.