Malá Fermatova věta je matematická věta, která tvrdí, že pro každé prvočíslo p a každé celé číslo a platí

${\displaystyle a^{p}\equiv a{\pmod {p}}}$

To znamená, že číslo ${\displaystyle (a^{p}-a)}$ je dělitelné prvočíslem p.

Pokud NSD(a,p) = 1, pak platí také tvar

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.

Symbol ≡ pochází z modulární aritmetiky a zápis se čte "je kongruentní s" (v modulo p).

Věta je nazvána podle francouzského matematika Pierra de Fermat (1601–1665); přívlastek malá ji odlišuje od Velké Fermatovy věty. Využívá se například pro Fermatův test prvočíselnosti.

Zobecnění

Pro libovolná přirozená čísla ${\displaystyle a}$ a ${\displaystyle n}$ taková, že NSD(a,n) = 1, platí

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$, kde ${\displaystyle \varphi }$ je Eulerova funkce.

Příklad

• Buď p=5, a=2. Jelikož 5 je prvočíslo a 2 není násobek 5, má podle malé Fermatovy věty platit, že ${\displaystyle 2^{5}-2}$ je dělitelné 5. Vskutku, ${\displaystyle 2^{5}-2=32-2=30}$ je dělitelné 5.

Důkazy

Důkaz indukcí

Buď ${\displaystyle k<p-1}$ a nechť ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$ pro přirozená ${\displaystyle 1\leq a\leq k}$. Pak ${\displaystyle (k+1)^{p}\equiv k^{p}+1^{p}{\pmod {p}}}$ (ostatní členy v binomickém rozvoji ${\displaystyle (k+1)^{p}}$ jsou dělitelné ${\displaystyle p}$) a podle indukčního předpokladu ${\displaystyle k^{p}\equiv k{\pmod {p}}}$. Tedy ${\displaystyle (k+1)^{p}\equiv k+1{\pmod {p}}}$, neboli ${\displaystyle (k+1)^{p-1}\equiv 1{\pmod {p}}}$. Tedy tvrzení platí pro ${\displaystyle a=1,\ldots ,p-1}$. Dále pro ${\displaystyle b\in \mathbb {Z} }$ platí ${\displaystyle (a+pb)^{p}\equiv a^{p}{\pmod {p}}}$, což plyne opět z binomického vzorce. Zbývá si uvědomit, že libovolné číslo ${\displaystyle x\in \mathbb {Z} }$, které není násobkem ${\displaystyle p}$, je možno napsat jako ${\displaystyle x=a+bp}$, kde ${\displaystyle a\in \{1,2,\ldots ,p-1\}}$. Tedy ${\displaystyle x^{p-1}\equiv a^{p-1}\equiv 1{\pmod {p}}}$.

Elementární důkaz

Mějme ${\displaystyle a}$ různých písmen ${\displaystyle A_{1},\ldots ,A_{a}}$ (nějaké) abecedy a uvažujme množinu všech slov o ${\displaystyle p}$ písmenech z oné abecedy (nad onou abecedou), kde ${\displaystyle p}$ je prvočíslo. Takových slov je zřejmě ${\displaystyle a^{p}}$. Buď ${\displaystyle \sigma (A_{i_{1}}A_{i_{2}}\ldots A_{i_{p}})=A_{i_{2}}A_{i_{3}}\ldots A_{i_{p}}A_{i_{1}}}$.

Rozdělme tuto množinu slov do menších podmnožin ${\displaystyle M}$ takovým způsobem, že slovo ${\displaystyle S\in M}$ právě když ${\displaystyle \sigma (S)\in M}$. Buď ${\displaystyle k}$ nejmenší takové, že ${\displaystyle \sigma ^{k}S=S}$. Zřejmě ${\displaystyle k\mid p}$, proto buď ${\displaystyle k=1}$ anebo ${\displaystyle k=p}$. Tedy každá z těchto podmnožina ${\displaystyle M}$ může mít buď jeden prvek (pokud se v slově opakuje p krát jedno písmeno), anebo p prvků (v ostatních případech). Jednoprvkových množin je však ${\displaystyle a}$, neboť jsou to právě množiny $$Zdroj:https://cs.wikipedia.org?pojem=Malá_Fermatova_věta
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.