Mersenneovi prosti brojevi

Mersenovi prosti brojevi su prosti brojevi oblika $2^n-1$

Nije poznato da li ovih brojeva ima konačno ili beskonačno mnogo.

U januaru 2013. pronađen je, za sada najveći 48. po redu Mersenov prost broj koji za n=57885161, ima 17 425 170 cifara.

Naziv su dobili po matematičaru Marinu Mersennu (8. septembar 1588 - 1. septembar 1648) koji je bio francuski teolog, filozof, matematičar i teoretičar muzike, koga često nazivaju ocem akustike. Mersenn je bio centar naučnog svijeta i svijeta matematike u prvoj polovini XVII vijeka. U svojoj knjizi "Cogita Physico– Mathematica" iznio je tvrdnju da je broj $2^n-1$ za n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 prost, a za sve druge prirodne brojeve manje od 257 da je složen broj. Kasnije su provjere pokazale kako je Mersenne pogriješio, i da brojevi $m_{67}$ i $m_{257}$ nisu prosti, a da su prosti brojevi $m_{61}$, $m_{89}$ i $m_{107}$.

Do danas je poznato 38 Mersenneovih brojeva, a u donjoj tablici se navodi nekoliko posljednjih:

n	broj cifri	godina	otkrio
1 257 787	378632	1996	Slowinski i Gage
1 398 269	420 921	1996	Armengaud i Woltman
2 976 221	895 932	1997	Spence i Woltman
3 021 377	909 526	1998	Clarkson
6 972 593	2 098 960	1999	Hajratwala

Godine 1963. u Sjedinjenim Americkim Državama kreiran je poštanski pečat na kojem stoji zapis da je broj $2^{11213}-1$ prost. A na memorandumu velikog proizvodača računala IBM–a neko je vrijeme stajalo zapisano da je broj $2^{19937}-1$ prost.

Mersseneova tvrdnja probudila je veliko zanimanje zato što su brojevi toliko veliki da nekoliko stotina godina niko nije mogao potvrditi ni opovrgnuti njegovu tvrdnju. Tadašnjim matematičarima bilo je jasno da Mersenne nije mogao provjeriti tvrdnju za sve navedene brojeve, ali isto tako nisu mogli ni oni. Leonhard Euler pokazao je 1772. godine da je $m_{31}$ prost tako što je provjerio sve proste brojeve do 46339 kao moguće djelitelje, ali tu metodu nije mogao upotrijebiti na brojevima $m_{67}$, $m_{127}$ i $m_{257}$. Na sličan način je Pietro Cataldi 1588. godine pokazao da su $m_{17}$i $m_{19}$ prosti brojevi.

Provjera da li je neki broj oblika $2^n-1$ Mersenneov ili nije je komplikovana. Broj $2^n$ vrlo brzo raste pa je neophodno u provjerama koristiti računare. No neki stariji rezultati su uistinu impresivni. Francuski matematičar Edouard Lucas (1842. - 1891.) dokazao je 1876. da je broj

$m_{127}=170141183460469231731687$$303715884105727$ prost broj.

Lucas je pritom razvijao metode kojima bi se postupak provjere što vise pojednostavio, pa ga danas smatraju pionirom modernog numeričkog računa. Važan je rezultat kako broj $2^n-1$ uopšte može biti prost samo ako je $n$ prost. Uz traganje za Mersenneovim brojevima vezan je niz detalja. Tako su, primjerice Laura Nickel i Curt Noll, dvoje osamnaestogodišnjih studenata Kalifornijskog sveučilista u Haywardu, otkrili uz pomoć računara da je $2^{21701}-1$ prost broj. Taj broj sastoji se od $6533$ cifri. Također, devetnaestogodišnji Amerikanac Ronald Clarkson je 1998. na svom kućnom računaru otkrio Mersenneov broj $m_{3021377}$ u čijem je zapisu $909526$ cifri.