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í

To znamená, že číslo je dělitelné prvočíslem p.

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

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 (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

Pro libovolná přirozená čísla   a   taková, že NSD(a,n) = 1, platí

 , kde   je Eulerova funkce.

PříkladEditovat

  • Buď p=5, a=2. Jelikož 5 je prvočíslo a 2 není násobek 5, má podle malé Fermatovy věty platit, že   je dělitelné 5. Vskutku,   je dělitelné 5.

DůkazyEditovat

Důkaz indukcíEditovat

Buď   a nechť   pro přirozená  . Pak   (ostatní členy v binomickém rozvoji   jsou dělitelné  ) a podle indukčního předpokladu  . Tedy  , neboli  . Tedy tvrzení platí pro  . Dále pro   platí  , což plyne opět z binomického vzorce. Zbývá si uvědomit, že libovolné číslo  , které není násobkem  , je možno napsat jako  , kde  . Tedy  .

Elementární důkazEditovat

Mějme   různých písmen   (nějaké) abecedy a uvažujme množinu všech slov o   písmenech z oné abecedy (nad onou abecedou), kde   je prvočíslo. Takových slov je zřejmě  . Buď  .

Rozdělme tuto množinu slov do menších podmnožin   takovým způsobem, že slovo   právě když  . Buď   nejmenší takové, že  . Zřejmě  , proto buď   anebo  . Tedy každá z těchto podmnožina   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  , neboť jsou to právě množiny  . Zbylá slova se tedy dají rozdělit do podmnožin velikosti  , tedy  .

Důkaz pomocí teorie grupEditovat

Buď   prvočíslo. Pak množina zbytkových tříd   je těleso, jehož nenulové prvky tvoří multiplikativní grupu   řádu  . Libovolný prvek   generuje její cyklickou podgrupu řádu  , t.j.   je nejmenší číslo, pro které  . Podle Lagrangeovy věty, počet prvků podgrupy dělí počet prvků grupy, tedy  . Tedy   v  . Tedy pro   máme   v  .

Důkaz pomocí součinu zbytkových třídEditovat

Buď opět   prvočíslo,   množina zbytkových tříd, jejíž nenulové prvky tvoří multiplikativní grupu   řádu  . Násobení prvkem   permutuje prvky  , proto součin všech prvků se nezmění:

 

Součin na obou stranách je nesoudělný s   (poněvadž každý prvek součinu je nesoudělný s  ). Můžeme tedy zkrátit součin a dostáváme   v  .

LiteraturaEditovat

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