Prvočíslo

Prvočíslo je přirozené číslo určitého druhu. Každé přirozené číslo je rovno 1 krát samo sebe. Pokud je číslo rovno násobku jakéhokoli jiného čísla, pak se číslo nazývá "složené číslo". Nejmenší složené číslo je 4, protože 2 x 2 = 4. Jednička není složené číslo. Každé jiné číslo je prvočíslo. Prvočísla jsou čísla jiná než 1, která se nerovnají m x n (kromě 1 x samo sebe). Nejmenší prvočíslo je 2. Dalšími prvočísly jsou 3, 5, 7, 11 a 13. Nejmenší prvočíslo je 2. Největší prvočíslo neexistuje.

Způsob vzniku prvočísel je pro matematiky obtížným problémem. Když je číslo větší, je obtížnější zjistit, zda se jedná o prvočíslo. Jednou z odpovědí je věta o prvočíslech. Jedním z nevyřešených problémů je Goldbachova domněnka.

Zde je další způsob, jak přemýšlet o prvočíslech. Číslo 12 není prvočíslo, protože z něj lze vytvořit obdélník se stranami o délkách 4 a 3. Tento obdélník má plochu 12, protože je použito všech 12 kvádrů. To nelze provést s číslem 11. Ať je obdélník uspořádán jakkoli, vždy v něm zůstanou kvádry, kromě obdélníku se stranami o délkách 11 a 1. 11 tedy musí být prvočíslo.

Jak najít malá prvočísla

Existuje jednoduchá metoda, jak najít seznam prvočísel. Vytvořil ji Eratosthenes. Má název Eratosthenovo síto. Zachycuje čísla, která nejsou prvočísla (jako síto), a prvočísla nechává projít.

Metoda pracuje se seznamem čísel a speciálním číslem b, které se v průběhu metody mění. Při postupu metodou některá čísla v seznamu zakroužkujete a jiná vyškrtnete. Každé zakroužkované číslo je prvočíslo a každé přeškrtnuté číslo je složené. Na začátku jsou všechna čísla prostá: nejsou zakroužkována ani přeškrtnuta.

Metoda je vždy stejná:

Na list papíru napište všechna celá čísla od 2 až po testované číslo. Číslo 1 nezapisujte. Přejděte k dalšímu kroku.
Začněte s hodnotou b rovnou 2. Přejděte k dalšímu kroku.
V seznamu zakroužkujte písmeno b. Přejděte na další krok.
Počínaje číslem b spočítejte v seznamu další b a toto číslo vyškrtněte. Opakujte počítání dalších b čísel a škrtání čísel až do konce seznamu. Přejděte k dalšímu kroku.

(Například: Když je b 2, zakroužkujete 2 a přeškrtnete 4, 6, 8 atd. Když je b 3, zakroužkujete 3 a přeškrtnete 6, 9, 12 atd. Hodnoty 6 a 12 již byly přeškrtnuty. Přeškrtněte je znovu.)

Zvětšete b o 1. Přejděte k dalšímu kroku.
Pokud bylo b přeškrtnuto, vraťte se k předchozímu kroku. Pokud je b číslo v seznamu, které nebylo přeškrtnuto, přejděte ke 3. kroku. Pokud b není v seznamu, přejděte k poslednímu kroku.
(Toto je poslední krok.) Hotovo. Všechna prvočísla jsou zakroužkována a všechna složená čísla jsou přeškrtnuta.

Tuto metodu můžete například použít na seznamu čísel od 2 do 10. Na konci budou zakroužkována čísla 2, 3, 5 a 7. Jsou to prvočísla. Čísla 4, 6, 8, 9 a 10 budou přeškrtnuta. Jsou to složená čísla.

Tato metoda nebo algoritmus trvá příliš dlouho, než se najdou velmi velká prvočísla. Je však méně komplikovaný než metody používané pro velmi velká prvočísla, jako je Fermatův test prvočíselnosti (test, který zjišťuje, zda je číslo prvočíslo či nikoli) nebo Millerův-Rabinův test prvočíselnosti.

K čemu se používají prvočísla

Prvočísla jsou velmi důležitá v matematice a informatice. Níže jsou uvedena některá reálná použití. Velmi dlouhá čísla se obtížně řeší. Je obtížné najít jejich prvočinitele, proto se většinou čísla, která jsou pravděpodobně prvočísla, používají k šifrování a tajným kódům.

Většina lidí má bankovní kartu, kterou si může vybrat peníze ze svého účtu pomocí bankomatu. Tato karta je chráněna tajným přístupovým kódem. Protože kód musí být utajen, nemůže být na kartě uložen v otevřeném textu. K tajnému uložení kódu se používá šifrování. Toto šifrování využívá násobení, dělení a hledání zbytků velkých prvočísel. V praxi se často používá algoritmus zvaný RSA. Využívá čínskou větu o zbytcích.

Pokud má někdo u svého e-mailu digitální podpis, používá se šifrování. Tím je zajištěno, že nikdo nemůže e-mail od něj zfalšovat. Před podpisem se vytvoří hashová hodnota zprávy. Ta se pak zkombinuje s digitálním podpisem a vznikne podepsaná zpráva. Používané metody jsou víceméně stejné jako v prvním výše uvedeném případě.

Hledání největšího dosud známého prvočísla se stalo svého druhu sportem. Testování, zda je číslo prvočíslo, může být obtížné, pokud je číslo velké. Největšími známými prvočísly jsou obvykle Mersennova prvočísla, protože nejrychlejším známým testem prvočíselnosti je Lucasův-Lehmerův test, který se opírá o speciální tvar Mersennových čísel. Skupina, která hledá Mersennova prvočísla, je zde[1].

Otázky a odpovědi

Otázka: Co je to prvočíslo?

Odpověď: Prvočíslo je přirozené číslo, které nelze dělit žádným jiným přirozeným číslem kromě 1 a sebe sama.

Otázka: Jaké je nejmenší složené číslo?

Odpověď: Nejmenší složené číslo je 4, protože 2 x 2 = 4.

Otázka: Jaká jsou další prvočísla po 2?

Odpověď: Další prvočísla po 2 jsou 3, 5, 7, 11 a 13.

Otázka: Existuje největší prvočíslo?

Odpověď: Ne, žádné největší prvočíslo neexistuje. Množina prvočísel je nekonečná.

Otázka: Co říká základní věta aritmetiky?

Odpověď: Základní věta aritmetiky říká, že každé kladné celé číslo lze zapsat jako součin prvočísel jedinečným způsobem.

Otázka: Co je Goldbachova domněnka?

Odpověď: Goldbachova domněnka je nevyřešený problém v matematice, který tvrdí, že každé sudé celé číslo větší než dvě lze vyjádřit jako součet dvou prvočísel.

Otázka: Kdo zaznamenal důkaz, že neexistuje největší prvočíslo?

Odpověď: Euklides zaznamenal důkaz, že neexistuje největší prvočíslo.