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(\mathrm{mod}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(\mathrm{mod}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^{\phi (n)}\equiv 1(\mathrm{mod}n)$, kde $\phi$ 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(\mathrm{mod}p)$ pro přirozená $1\le a\le k$. Pak $(k+1{)}^p\equiv k^p+1^p(\mathrm{mod}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(\mathrm{mod}p)$. Tedy $(k+1{)}^p\equiv k+1(\mathrm{mod}p)$, neboli $(k+1{)}^{p-1}\equiv 1(\mathrm{mod}p)$. Tedy tvrzení platí pro $a=1,\dots ,p-1$. Dále pro $b\in \mathbb{Z}$ platí $(a+pb{)}^p\equiv a^p(\mathrm{mod}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,\dots ,p-1\}$. Tedy $x^{p-1}\equiv a^{p-1}\equiv 1(\mathrm{mod}p)$.

Elementární důkaz

Mějme $a$ různých písmen $A_1,\dots ,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}\dots A_{i_p})=A_{i_2}{A}_{i_3}\dots 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\dots A_1\},\dots ,\{A_a,\dots ,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\ne 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\ne 0$ permutuje prvky ${\mathbb{Z}}_p^{*}$, proto součin všech prvků se nezmění:

${\mathrm{\Pi }}_{x\in {\mathbb{Z}}_p^{*}}x={\mathrm{\Pi }}_{x\in {\mathbb{Z}}_p^{*}}ax=a^{p-1}{\mathrm{\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

• Šablona:Commonscat