Malá Fermatova věta

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 (16011665); přívlastek malá ji odlišuje od Velké Fermatovy věty. Využívá se například pro Fermatův test prvočíselnosti.

Zobecnění[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

Elementární důkaz[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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