Jak identifikovat prvočíslo bez počítače

Je 170,141,183,460,469,231,731,687,303,715,884,105,727 prvočíslo? Než požádáte internet o odpověď, můžete zvážit, jak byste na tuto otázku mohli odpovědět bez počítač nebo dokonce digitální kalkulačku?

V roce 1800 francouzský matematik Édouard Lucas strávil roky dokazováním, že toto 39místné číslo bylo skutečně prvočíslo. jak to udělal? Lucas, který mimochodem také navrhl zábavnou hru Hanojská věžvyvinul metodu, která je užitečná i dnes, o více než století později.

Lidé byli po tisíciletí fascinováni prvočísly. Tato čísla jsou dělitelná pouze 1 a sami sebou, zatímco každé jiné celé číslo lze jednoznačně vyjádřit jako součin několika prvočísel; například 15 = 3 × 5. Prvočísla v podstatě tvoří periodickou tabulku matematiky. Mají také mnohá tajemství. Na číselné ose se objevují s určitou pravidelností, ale jejich výskyt je charakterizován kolísáním, které zatím nelze kvantifikovat. Tato nepředvídatelnost byla pro odborníky zdrojem zděšení.

O podpoře vědecké žurnalistiky

Pokud se vám tento článek líbí, zvažte podporu naší oceňované žurnalistiky předplatné. Zakoupením předplatného pomáháte zajistit budoucnost působivých příběhů o objevech a nápadech, které formují náš dnešní svět.

A matematickí nadšenci neustále hledají nová prvočísla. Aktuální rekord (od října 2025) pro největší prvočíslo je 2^136,279,841 − 1, číslo s 41 024 320 číslicemi. Pouhé přečtení tohoto čísla nahlas by trvalo přibližně 240 dní.

Prvočísla se speciální strukturou

Každý, kdo pozoroval rekordní prvočísla posledních let, si mohl všimnout, že mají většinou podobnou strukturu: 2^p – 1 (kde p je prvočíslo). Prvočísla tohoto tvaru se nazývají Mersennova prvočísla. A číslo, kterému Lucas zasvětil téměř dvě dekády svého života, je také mersennovským primátem, konkrétně 2¹²⁷ – 1. Ale tato Mersennova prvočísla mají nějakou záludnost: ne každé 2^p– 1 je prvočíslo pro každou prvočíslo p. Například 2¹¹ – 1 dává 2 047 a lze ji zapsat jako součin 23 a 89.

Takže v polovině 19. století Lucas přemýšlel, zda 2¹²⁷ – 1 bylo prvočíslo nebo ne. Čelil hrozivé výzvě. Číslo je obrovské, skládá se z 39 číslic a Lucas v té době evidentně neměl přístup k počítači. Musel ručně zajistit, aby 2¹²⁷ – 1 neměl žádné dělitele (kromě 1 a sebe).

Jedním ze způsobů, jak toho dosáhnout, je projít všechna prvočísla až do 2¹²⁷ – 1 a ujistěte se, že se nedělí žádným z nich. Ale to je extrémně časově náročné a jednoduše neproveditelné, pokud neznáte všechna menší prvočísla.

Lucas-Lehmerův test prvočísel

Lucas se nevzdal. Na základě zjištění svého kolegy Évarista Galoise vyvinul novou metodu, která vyžadovala výrazně méně výpočtů.

Než se ponoříme do krásné – ale nepochybně abstraktní – matematiky Galoise a Lucase, představím Lucasův výsledek, nyní známý jako Lucas-Lehmerův test primálnosti.

Chcete-li zkontrolovat, zda 2^p – 1 je prvočíslo, Lucas vyvinul následující algoritmus:

1. Vytvořte posloupnost čísel, jejichž první člen je s₀ = 4 a kde každý následující s_n se počítá jako s²_{n – 1} – 2. Posloupnost je tedy: 4, 14, 194, 37 634 a tak dále.

2. Potom 2^p – 1 je prvočíslo právě tehdy, když p – 2. člen sekvence (tj. s_{p – 2}) je dělitelný 2^p – 1 beze zbytku. To znamená, že každé Mersennovo prvočíslo má tuto vlastnost a naopak každé s_{p – 2} definuje Mersennovo prvočíslo 2^p – 1.

Takže místo dělení Mersennova čísla všemi prvočísly menšími než 2¹²⁷ – 1, k určení stačí provést výpočty s₁₂₅ a pak vydělit 2¹²⁷ – 1. To je mnohem jednodušší, že?

V praxi existuje jen jeden malý – nebo spíše velmi velký – problém. Sekvenční termíny s_n rostou extrémně rychle – ve skutečnosti tak rychle, že není příliš praktické s nimi pracovat. Odborníci se proto uchýlí k triku: rozdělují členy sekvence s_n podle Mersennova čísla a pokračujte se zbytkem, pokud dělení nevede k celému číslu. To nemění druhou část algoritmu, takže podmínka pro Mersennova prvočísla zůstává stejná: musí být schopna rovnoměrně dělit s_{p – 2}. Tento trik dělá s_{p – 2} ovšem výrazně menší.

Abychom lépe porozuměli testu primality, můžeme jej propracovat na jednoduchém příkladu: Mersennovo číslo 2⁵ – 1, což je 31. Pomocí algoritmu vyvinutého Lucasem musíme vypočítats₃což je 37 634. Vydělením tohoto čísla 31 dostaneme přesný výsledek 1 214. To znamená, že s₃ je dělitelný 2⁵ – 1, a proto je to druhé prvočíslo.

Po letech usilovné práce vyvinul Lucas tento test primality a aplikoval jej na 2¹²⁷ – 1. Dokázal tak prokázat, že šlo skutečně o prvočíslo. Dodnes zůstává největším prvočíslem nalezeným bez pomoci počítače.

Lucas však přesvědčivě neprokázal, že jeho metoda spolehlivě identifikovala Mersennova prvočísla. Toho dosáhl až matematik Derrick Henry Lehmer v roce 1930, a proto je tato metoda známá jako Lucas-Lehmerův test primality.

Sady konečných čísel

Proč ale tato strategie vůbec funguje? Ve skutečnosti je důkaz docela technický – a proto vás ušetřím podrobností (k dispozici na Wikipedii). Ale mohu zhruba nastínit myšlenku metody.

Lucas-Lehmerův test primality je založen na výzkumu Galoise, který na počátku 19. století zkoumal symetrie v různých matematických objektech. Na rozdíl od svých předchůdců se však neomezoval pouze na geometrické útvary, ale uvažoval i o symetriích rovnic nebo číselných polí. Druhý termín popisuje množinu čísel, ve které lze všechny čtyři základní aritmetické operace (tj. sčítání, odčítání, násobení a dělení) použít bez opuštění množiny. Jinými slovy, když sečtu nebo vydělím dvě čísla z množiny, dostanu číslo, které je také součástí množiny. Příklady číselných sad jsou racionální čísla (která zahrnují celá čísla a zlomky) nebo reálná čísla.

Ukazuje se ale, že existují menší číselné množiny obsahující pouze konečný počet celých čísel od 0 do p – 1. Aby se zachovaly vlastnosti množiny, musí se čísla periodicky opakovat; po p – 1, 0 opět následuje: (0, 1, 2, 3, …, p – 1, 0, 1, 2, …). Takzvaná konečná pole se mohou zdát zvláštní, ale ve skutečnosti se s nimi setkáváme v každodenním životě: na analogových hodinách je naprosto přirozené, že 1 následuje 12.

Jak se ukazuje, konečné číselné soustavy jsou polem tehdy a jen tehdy p je prvočíslo. A Galois objevil, že tato pole konečných čísel mají speciální symetrické vlastnosti. Lucas využil tento princip při vývoji svého testu primality: Jestliže 2¹²⁷ – 1 je prvočíslo, pak odpovídající číselné pole 0, 1, 2,…, 2¹²⁷ – 2 musí mít určité symetrické vlastnosti. Chcete-li vygenerovat tento konečný číselný systém, musíte vydělit všechny hodnoty větší než 2¹²⁷ – 1 na 2¹²⁷ – 1 a vypočítejte zbytek. Toto je poslední krok v Lucasově algoritmu.

Tento článek se původně objevil v spektrum vědy a byl reprodukován se svolením.