Grupy a teorie čísel

Úkol:

a)
Dokažte, že pro každou konečnou grupu $ {\mbox{{\bb G}}}$ je její řád $ \vert{\mbox{{\bb G}}}\vert$ dělitelný řádem libovolné její podgrupy $ {\mbox{{\bb P}}}$ (Lagrangeova věta).
b)
Použijte předchozího výsledku k důkazu malé Fermatovy věty: je-li $ p$ prvočíslo a $ n\in${\bb N}, potom $ n^p$ a $ n$ dávají stejný zbytek při dělení $ p$, neboli

$\displaystyle n^p\equiv n(\mathop{\rm mod}\nolimits p)\,.$

c)
Pro dané $ n\in${\bb N} označme $ \varphi (n)$ počet přirozených čísel menších než $ n$ a nesoudělných s $ n$ (včetně jedničky, tzv. Eulerova funkce). Dokažte, že když $ (k,n)=1$ (kulatá závorka znamená zde největšího společného dělitele), potom

$\displaystyle k^{\varphi (n)}\equiv 1(\mathop{\rm mod}\nolimits n)\,.$


Řešení: Na úvod připomeňme dvě známé skutečnosti. Množina $ M_p=\{0,1,\ldots, p-1\}$ s operací násobení modulo $ p$ tvoří pro prvočíselné $ p$ grupu: inverzní prvek k $ n$ musí existovat, neboť čísla $ 0,n,2n,\ldots, (p-1)n$ dávají různé zbytky po dělení $ p$ (pokud $ jn\equiv j'n(\mathop{\rm mod}\nolimits p)$, pak $ p$ dělí $ (j-j')n$, což nelze pro $ \vert j-j'\vert<p$). Jelikož je jich $ p-1$, musí mezi těmito zbytky být i jednička. Toto je v kostce obsah příkladu 3.1.

Druhá skutečnost je, že pro $ p$ neprvočíselné tvoří multiplikativní grupu čísla z $ M_p$, která jsou nesoudělná s $ p$. Důkaz se provede podobně.


a) $ {\mbox{{\bb P}}}$ budiž podgrupa $ {\mbox{{\bb G}}}=\{g_1,\ldots, g_n\}$. Pro libovolné $ g\in${\bb G} definujeme levou třídu $ g{\mbox{{\bb P}}}:=\{gp\,\vert\,p\in{\mbox{{\bb P}}}\}$. Dokažte si, že relace $ \diamond$ na {\bb G}$ \times${\bb G}, definovaná $ g_1\diamond g_2\Leftrightarrow \exists p\in{\mbox{{\bb P}}},\ g_1=g_2p$, je ekvivalence (viz úlohu 2.6). Je-li $ g\in{\mbox{{\bb G}}}$ pevný prvek, pak $ g{\mbox{{\bb P}}}$ je množina všech prvků $ {\mbox{{\bb G}}}$ ekvivalentních (podle $ \diamond$) s $ g$. Všechny třídy $ g{\mbox{{\bb P}}}$ tvoří rozklad množiny {\bb G}, tzn. každé dvě takovéto třídy jsou buď totožné, nebo disjunktní a sjednocení $ g_1{\mbox{{\bb P}}}\cup \ldots\cup g_n{\mbox{{\bb P}}}={\mbox{{\bb G}}}$. Zřejmě ale všechny třídy mají stejný počet prvků jako $ {\mbox{{\bb P}}}$ (při důkazu předpokládejte, že dva prvky $ g${\bb P} jsou stejné), odkud už plyne dokazované tvrzení.


b) Uvažujme multiplikativní grupu $ {\mbox{{\bb G}}}=\{1,2,\dots,p-1\}$ s násobením modulo $ p$. Každý její prvek $ n$ prostřednictvím násobení se sebou samým generuje cyklickou podgrupu $ \{1,n,n^2,\ldots,\allowbreak n^{r-1}\}$, jejíž řád $ r$ je nejmenší přirozené číslo takové, že $ n^r\equiv 1(\mathop{\rm mod}\nolimits p)$. Dle bodu a) ale $ r$ dělí řád {\bb G}, tj. $ p-1$. Platí tedy také

$\displaystyle n^{p-1}\equiv 1(\mathop{\rm mod}\nolimits p)$

a po přenásobení celé kongruence $ n$

$\displaystyle n^p\equiv n(\mathop{\rm mod}\nolimits p)\,,$

což bylo dokázat. Předchozí úvaha samozřejmě platí jen pro $ n$, které není dělitelné $ p$. V opačném případě je ale tvrzení triviální.

Skutečnost, že $ p$ je prvočíslo, je potřeba k tomu, aby $ {\mbox{{\bb G}}}$ byla grupa, pro $ p$ neprvočíselné nenajdeme vždy inverzní prvek. Právě pro prvočíselné $ p$ je $ {\mbox{{\bb G}}}\cup\{0\}$ také těleso (s operacemi násobení a sčítání) -- viz příklad 3.1. Závěrem dodejme, že obrácená implikace k malé Fermatově větě neplatí.


c) Vzpomeňme si na okruh {\bb Z}$ _n=\{0,1,\dots,n-1\}$ se sčítáním a násobením modulo $ n$. Tento okruh obecně není tělesem, neboť pro ty prvky $ k\in${\bb Z}$ _n$, pro které $ (k,n)>1$, neexistuje inverzní multiplikativní prvek. Uvažujme nyní množinu $ {\mbox{{\bb P}}}=\{k\in\mbox{{\bb Z}}_n\,,\ (k,n)=1\}$, která tvoří s násobením modulo $ n$ grupu, jejíž řád je právě $ \varphi (n)$. Stejně jako v b) pak pro $ k\in${\bb P} využijeme jím generované cyklické podgrupy grupy $ {\mbox{{\bb P}}}$ k tomu, abychom dokázali

$\displaystyle k^{\varphi (n)}\equiv 1(\mathop{\rm mod}\nolimits n)\,.$

$ \ast$TB$ \ast$