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 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. +more 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. +more 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. +more 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. +more 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). +more 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

Kategorie:Teorie čísel Kategorie:Matematické věty a důkazy