Malá Fermatova věta

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 ${\displaystyle \{A_{1}A_{1}\ldots A_{1}\},\ldots ,\{A_{a},\ldots ,A_{a}\}}$. Zbylá slova se tedy dají rozdělit do podmnožin velikosti ${\displaystyle p}$, tedy ${\displaystyle p\mid a^{p}-a}$.

Důkaz pomocí teorie grup

Buď ${\displaystyle p}$ prvočíslo. Pak množina zbytkových tříd ${\displaystyle \mathbb {Z} _{p}}$ je těleso, jehož nenulové prvky tvoří multiplikativní grupu ${\displaystyle \mathbb {Z} _{p}^{*}}$ řádu ${\displaystyle p-1}$. Libovolný prvek ${\displaystyle a\in \mathbb {Z} _{p}^{*}}$ generuje její cyklickou podgrupu řádu ${\displaystyle k}$, tj. ${\displaystyle k}$ je nejmenší číslo, pro které ${\displaystyle a^{k}=1}$. Podle Lagrangeovy věty, počet prvků podgrupy dělí počet prvků grupy, tedy ${\displaystyle p-1=km}$. Tedy ${\displaystyle a^{p-1}=a^{km}=(a^{k})^{m}=1^{m}=1}$ v ${\displaystyle \mathbb {Z} _{p}^{*}}$. Tedy pro ${\displaystyle 0\neq a\in \mathbb {Z} _{p}}$ máme ${\displaystyle a^{p-1}=1}$ v ${\displaystyle \mathbb {Z} _{p}}$.

Důkaz pomocí součinu zbytkových tříd

Buď opět ${\displaystyle p}$ prvočíslo, ${\displaystyle \mathbb {Z} _{p}}$ množina zbytkových tříd, jejíž nenulové prvky tvoří multiplikativní grupu ${\displaystyle \mathbb {Z} _{p}^{*}}$ řádu ${\displaystyle p-1}$. Násobení prvkem ${\displaystyle a\neq 0}$ permutuje prvky ${\displaystyle \mathbb {Z} _{p}^{*}}$, proto součin všech prvků se nezmění:

${\displaystyle \Pi _{x\in \mathbb {Z} _{p}^{*}}x=\Pi _{x\in \mathbb {Z} _{p}^{*}}ax=a^{p-1}\Pi _{x\in \mathbb {Z} _{p}^{*}}x}$

Součin na obou stranách je nesoudělný s ${\displaystyle p}$ (poněvadž každý prvek součinu je nesoudělný s ${\displaystyle p}$). Můžeme tedy zkrátit součin a dostáváme ${\displaystyle a^{p-1}=1}$ v ${\displaystyle \mathbb {Z} _{p}}$.

Literatura

• Jaroslav Blažek, Emil Calda, Blanka Kussová: Algebra a teoretická aritmetika I., SPN Praha 1979

Externí odkazy

• Obrázky, zvuky či videa k tématu Malá Fermatova věta na Wikimedia Commons