Mersennovo prvočíslo

Z Wikipedie, otevřené encyklopedie

Mersennovo prvočíslo je takové prvočíslo (číslo dělitelné jen jedničkou a sebou samým), které je o jedna menší než celočíselná mocnina dvojky, tzn. je tvaru

M_p = 2^p − 1,

pokud číslo v takovém tvaru není prvočíslo, označuje se jako Mersennovo číslo.

Příkladem Mersennova prvočísla je 7 = 2³ − 1. Naproti tomu například Mersennovo číslo 2⁴ − 1 = 15 není prvočíslem (je to složené číslo, 15 = 3 · 5).

[editovat] Vlastnosti

Lze snadno ukázat, že pokud má být číslo 2ⁿ − 1 prvočíslem, musí být prvočíslem i exponent n:

$2^{ab}-1 = (2^a-1) \cdot (1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a})$ ,

opak ovšem neplatí: číslo 2^p − 1 může být složené i pro prvočíselný exponent p (např. 2¹¹ − 1 = 23 · 89).

Mersennova prvočísla mají těsný vztah s dokonalými čísly (čísla, která jsou rovná součtu svých vlastních dělitelů), tento fakt byl také prvotním důvodem pro studium tohoto druhu prvočísel. Už ve 4. století př. n. l. Eukleidés dokázal, že pokud M je Mersennovo prvočíslo, pak M(M+1)/2 je dokonalé číslo. V 18. století pak dokázal Euler, že takovou formu mají všechna sudá dokonalá čísla. (Nejsou známa žádná lichá dokonalá čísla a předpokládá se, že žádná neexistují.)

V současné době není známo, zda je Mersennových prvočísel nekonečně mnoho.

M_n je sumou kombinačních čísel: $M_n = \sum_{i=0}^{n}{n \choose i} - 1$ .

[editovat] Historie

Tato čísla jsou pojmenována podle francouzském matematikovi Marinu Mersennovi (1588–1648), který sestavil seznam takových prvočísel s exponenty do 257; jeho seznam však obsahoval chyby: nesprávně zahrnoval M₆₇ a M₂₅₇ a naopak v něm chyběly M₆₁, M₈₉, M₁₀₇. Mnoho prvočísel v tomto tvaru je však známo už výrazně déle (viz níže).

[editovat] Způsoby hledání

Pro hledání Mersennových prvočísel existují specializované velice rychlé metody (oproti obecným metodám pro hledání či testování libovolných prvočísel), což je důvod, proč největší známá prvočísla jsou právě Mersennovými prvočísly.

V současné době nejrychlejší metoda testování prvočíselnosti Mersennových čísel spočívá ve výpočtu rekurentní posloupnosti, vyvinutá v roce 1878 Edouardem Lucasem a vylepšená Lehmerem ve 30. letech 20. století, známá jako Lucasův-Lehmerův test. Tento test je založen na faktu, že Mersennovo číslo je prvočíslem tehdy a jen tehdy, pokud dělí číslo $s n - 2$ , kde $s_k = s_{k-1}^2 - 2$ (a $s 0 = 4$ ).

Převratem ve vyhledávání Mersennových prvočísel byl příchod počítačů. První počítačem nalezené Mersennovo prvočíslo, M₅₂₁, bylo nalezeno v 22:00 30. ledna 1952 na počítači na UCLA, pod Lehmerovým vedením, pomocí programu sestaveného profesorem Robinsonem. Od nalezení předchozího Mersennova prvočísla tehdy uběhlo už 38 let, následující prvočíslo (M₆₀₇) pak bylo nalezeno za necelé dvě hodiny, v dalších měsících pak stejný program nalezl tři další.

V roce 1997 vzniknul na Internetu projekt GIMPS pro distribuované vyhledávání Mersennových prvočísel. Tento projekt dosud objevil devět největších známých Mersennových prvočísel (tzn. i největší dnes známé prvočíslo).

[editovat] Známá Mersennova prvočísla

Následující tabulka obsahuje všechna známá Mersennova prvočísla (sekvence A000668 v OEIS):

#	n	M_n	Cifer v M_n	Datum objevu	Objevitel
1.	2	3	1	dávno	neznámý
2.	3	7	1	dávno	neznámý
3.	5	31	2	dávno	neznámý
4.	7	127	3	dávno	neznámý
5.	13	8191	4	1456	neznámý
6.	17	131071	6	1588	Cataldi
7.	19	524287	6	1588	Cataldi
8.	31	2147483647	10	1772	Euler
9.	61	2305843009213693951	19	1883	Pervušin
10.	89	618970019…449562111	27	1911	Powers
11.	107	162259276…010288127	33	1914	Powers
12.	127	170141183…884105727	39	1876	Lucas
13.	521	686479766…115057151	157	30. ledna 1952	Robinson
14.	607	531137992…031728127	183	30. ledna 1952	Robinson
15.	1 279	104079321…168729087	386	25. června 1952	Robinson
16.	2 203	147597991…697771007	664	7. října 1952	Robinson
17.	2 281	446087557…132836351	687	9. října 1952	Robinson
18.	3 217	259117086…909315071	969	8. září 1957	Riesel
19.	4 253	190797007…350484991	1 281	3. listopadu 1961	Hurwitz
20.	4 423	285542542…608580607	1 332	3. listopadu 1961	Hurwitz
21.	9 689	478220278…225754111	2 917	11. května 1963	Gillies
22.	9 941	346088282…789463551	2 993	16. května 1963	Gillies
23.	11 213	281411201…696392191	3 376	2. června 1963	Gillies
24.	19 937	431542479…968041471	6 002	4. března 1971	Tuckerman
25.	21 701	448679166…511882751	6 533	30. října 1978	Noll a Nickel
26.	23 209	402874115…779264511	6 987	9. února 1979	Noll
27.	44 497	854509824…011228671	13 395	8. dubna 1979	Nelson a Slowinski
28.	86 243	536927995…433438207	25 962	25. září 1982	Slowinski
29.	110 503	521928313…465515007	33 265	28. ledna 1988	Colquitt a Welsh
30.	132 049	512740276…730061311	39 751	20. září 1983	Slowinski
31.	216 091	746093103…815528447	65 050	6. září 1985	Slowinski
32.	756 839	174135906…544677887	227 832	19. února 1992	Slowinski a Gage
33.	859 433	129498125…500142591	258 716	10. ledna 1994	Slowinski a Gage
34.	1 257 787	412245773…089366527	378 632	3. září 1996	Slowinski a Gage
35.	1 398 269	814717564…451315711	420 921	13. listopadu 1996	GIMPS / Joel Armengaud
36.	2 976 221	623340076…729201151	895 932	24. srpna 1997	GIMPS / Gordon Spence
37.	3 021 377	127411683…024694271	909 526	27. ledna 1998	GIMPS / Roland Clarkson
38.	6 972 593	437075744…924193791	2 098 960	1. června 1999	GIMPS / Nayan Hajratwala
39.^*	13 466 917	924947738…256259071	4 053 946	14. listopadu 2001	GIMPS / Michael Cameron
40.^*	20 996 011	125976895…855682047	6 320 430	17. listopadu 2003	GIMPS / Michael Shafer
41.^*	24 036 583	299410429…733969407	7 235 733	15. května 2004	GIMPS / Josh Findley
42.^*	25 964 951	122164630…577077247	7 816 230	18. února 2005	GIMPS / Martin Nowak
43.^*	30 402 457	315416475…652943871	9 152 052	16. prosince 2005	GIMPS / Curtis Cooper a Steven Boone
44.^*	32 582 657	124575026…053967871	9 808 358	4. září 2006	GIMPS / Curtis Cooper a Steven Boone