Mersennovo prvočíslo

Mersennovo prvočíslo je takové prvočíslo, které je o jedna menší než celočíselná mocnina dvojky, tzn. je tvaru

${\displaystyle M_{p}=2^{p}-1}$.

Obecněji všechna čísla v takovém tvaru, bez ohledu na jejich prvočíselnost, se označují jako Mersennova čísla.

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).

Vlastnosti

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

${\displaystyle 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.

${\displaystyle M_{n}}$ je sumou kombinačních čísel: ${\displaystyle M_{n}=\sum _{i=0}^{n}{n \choose i}-1}$.

Historie

Tato čísla jsou pojmenována po 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).

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 ${\displaystyle s_{n-2}}$, kde ${\displaystyle s_{k}=s_{k-1}^{2}-2}$ (a ${\displaystyle 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 1996 vznikl na Internetu projekt GIMPS pro distribuované vyhledávání Mersennových prvočísel. Tento projekt dosud (prosinec 2018) objevil sedmnáct největších známých Mersennových prvočísel (tzn. i největší dnes známé prvočíslo).

Známá Mersennova prvočísla

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

^* Říjen 2021: Dosud není známo, zda mezi 48. a 51. čísly existují některá dosud neobjevená Mersennova prvočísla, číslování je zde proto pouze dočasné.

Odkazy

Reference

Související články

• Dokonalé číslo
• Abundantní číslo
• Deficientní číslo

Externí odkazy

• Obrázky, zvuky či videa k tématu Mersennovo prvočíslo na Wikimedia Commons
• www.mersenne.org – Great Internet Mersenne Prime Search (GIMPS)
• Mersennovo prvočíslo v encyklopedii MathWorld
• Mersennovo číslo v encyklopedii MathWorld
• Historie, věty, seznam Mersennových prvočísel
• mersennewiki.org – wiki o Mersennových prvočíslech