Malá Fermatova věta

Z Multimediaexpo.cz

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 Pierre de Fermata (* 1607, † 12. ledna 1665).

Přívlastek malá ji odlišuje od slavnější 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

• AoPS – Fermat's Little Theorem (anglicky)
• Wolfram MathWorld – Fermat's Little Theorem (anglicky)

Commons nabízí fotografie, obrázky a videa k tématu Malá Fermatova věta

Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii