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 takové, že NSD(a,p) = 1, platí

$a^{p-1}\equiv 1 \pmod p$, anebo ekvivalentně,

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

To znamená, že číslo $(a^p-a)$ je dělitelné prvočíslem 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 $p$ a $a$ taková, že NSD(a,p) = 1, platí

$a^{\varphi(p)}\equiv 1 \pmod p$, kde $\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 $2^5-2$ je dělitelné 5. Vskutku, $2^5-2=32-2=30$ je dělitelné 5.

Důkazy

Elementární důkaz

Mějme $a$ různých písmen $A_1,\ldots,A_a$ (nějaké) abecedy a uvažujme množinu všech slov o $p$ písmenech z oné abecedy (nad onou abecedou), kde $p$ je prvočíslo. Takových slov je zřejmě $a^p$. Buď $\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 $M$ takovým způsobem, že slovo $S\in M$ právě když $\sigma(S)\in M$. Buď $k$ nejmenší takové, že $\sigma^k S=S$. Zřejmě $k\mid p$, proto buď $k=1$ anebo $k=p$. Tedy každá z těchto podmnožina $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 $a$, neboť jsou to právě množiny $\{A_1 A_1\ldots A_1\}, \ldots, \{A_a,\ldots,A_a\}$. Zbylá slova se tedy dají rozdělit do podmnožin velikosti $p$, tedy $p\mid a^p-a$.

Důkaz pomocí teorie grup

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

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

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

$\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 $p$ (poněvadž každý prvek součinu je nesoudělný s $p$). Můžeme tedy zkrátit součin a dostáváme $a^{p-1}=1$ v $\mathbb{Z}_p$.

Důkaz indukcí

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

Literatura

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