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í

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

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

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

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

$a^{\varphi (n)}\equiv 1{\pmod {n}}$, 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

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}}$.

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$, tj. $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}$.

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

Autoritní data	NKC: ph158529

Portály: Matematika