Fermatův test prvočíselnosti se používá k určení, zda je dané číslo prvočíslo nebo číslo složené. Patří mezi pravděpodobnostní testy prvočíselnosti a je založený na malé Fermatově větě.

Popis

Fermatův test nepatří mezi typické pravděpodobnostní testy. Jednoznačně nerozliší prvočísla od čísel složených (to jsou tzv. Carmichaelova čísla), proto je často označován jako test složenosti.^[1]

Na základě malé Fermatovy věty, je-li ${\displaystyle n}$ prvočíslo a ${\displaystyle a}$ není jeho násobek platí ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$, nebo lze také říci, že ${\displaystyle a^{n-1}-1}$ je dělitelné číslem ${\displaystyle n}$. Po použití obrácené implikace tohoto tvrzení je zřejmé, že existuje-li ${\displaystyle a\in \{1,2,...,n-1\}}$ takové, že ${\displaystyle n}$ nedělí ${\displaystyle a^{n-1}-1}$, pak musí být ${\displaystyle n}$ číslo složené.^[2]

Příklad: Při zvolení ${\displaystyle a=2;n=9}$; ${\displaystyle 2^{8}-1=255}$, číslo ${\displaystyle 9}$ není dělitelem čísla ${\displaystyle 255}$ nebo

${\displaystyle a=2;n=21}$; ${\displaystyle 2^{20}-1=1048575}$, také ${\displaystyle 21}$ nedělí číslo ${\displaystyle 1048575}$. Fermatův test potvrdil složenost čísla pro ${\displaystyle a=2}$.

n je složené číslo

Pro složené číslo ${\displaystyle n}$ a přirozené číslo ${\displaystyle a}$, platí:

• ${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$ – číslo ${\displaystyle a}$ se nazývá Fermatův svědek složenosti čísla ${\displaystyle n}$
• ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ – číslo ${\displaystyle n}$ se nazývá pseudoprvočíslo vzhledem k bázi ${\displaystyle a}$.^[2][1]

Zobecnění

Je-li ${\displaystyle n}$ prvočíslo ${\displaystyle \Rightarrow }$ ${\displaystyle {\bigl (}\forall a\in \{1,2,...,n-1\}:a^{n-1}\equiv 1{\pmod {n}})}$ nebo ${\displaystyle \exists a\in \{1,2,...,n-1\}:a^{n-1}\not \equiv 1{\pmod {n}}\Rightarrow n}$ není prvočíslo

Příklady

Zadání1: ${\displaystyle n=5}$ a platí pro ${\displaystyle a=1;1^{5-1}=1^{4}=1}$, ${\displaystyle a=2;2^{5-1}=2^{4}=16}$ atd.

${\displaystyle 1^{4}\equiv 1{\pmod {5}}}$

${\displaystyle 16=2^{4}\equiv 1{\pmod {5}}}$

${\displaystyle 81=3^{4}\equiv 1{\pmod {5}}}$

${\displaystyle 4^{4}\equiv 1{\pmod {5}}}$ ${\displaystyle \Rightarrow }$ ${\displaystyle n=5}$ je prvočíslo.

Zadání2: ${\displaystyle n=15}$; ${\displaystyle a=2;1^{2-1}=1}$

${\displaystyle 1^{14}\equiv 1{\pmod {15}}}$

${\displaystyle 2^{14}\equiv 4{\pmod {15}}}$ ${\displaystyle \Rightarrow }$ kongruence není rovna ${\displaystyle 1}$Zdroj:https://cs.wikipedia.org?pojem=Fermatův_test_prvočíselnosti
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.