Úvod
Toto číslo patrí do kategórie špeciálnych prvočísiel (viď. článok špeciálne prvočísla). Toto číslo je jedno z najväčších známych prvočísiel. V tomto diely Vám ukážem užitočnosť redukovanej, malej Fermatovej vety a k nemu prislúchajúceho algoritmu (aj pre výpočet najväčších prvočísiel). Ide o Mersennove prvočíslo a z hľaddiska dielov o prvočíslach ide o špeciálne prvočíslo (viď. predošlý diel).Výsledný vzťah je :
Vzťahy platia pre ľubovolne špeciálne prvočíslo - Mersenovo prvočíslo.
Výpočet vo Wolfram:
Príklady pre overenie Wolfram:
(1)
https://www.wolframalpha.com/input/?i=2%5E31+mod+%282%5E31-1%29
preverenie periody:
https://www.wolframalpha.com/input/?i=%282147483647-1%29%2F2+mod+31
TRUE
(2)
https://www.wolframalpha.com/input/?i=2%5E82589933+mod+%282%5E82589933-1%29
preverenie periódy:
https://www.wolframalpha.com/input/?i=%282%5E82589933-1-1%29%2F2+mod+82589933
TRUE
Poznámka:
Pre špeciálne prvočísla postačuje preveriť periódu.Nie je nutné počítať Fermatovú vetu. Pre prvočísla v tvare:
- p=2
^k-1, perioda T=k, podmienka: (p-1)/2 mod T=0
- p= 2 ^k+1, perioda T=2k, podmienka: (p-1) mod T=0
- Ak platí podmienka ide pravdepodobne o prvočíslo, resp pseudoprvočíslo.