Před tímto článekem doporučuji přečtení článku o grupách.
Podgrupa
Mějme grupu \(G\) s operací \(\circ\). Potom její podgrupou rozumíme podmnožinu \(H\) nosné množiny \(G\) s operací \(\circ\), která splňuje všechny axiomy grupy. Píšeme \(H \leq G\).
Mějme např. \(\mathbb{Z}\) se sčítáním. Vyberme si nějakou její podmnožinu, např. všechna sudá čísla, tedy \(H = \{2k, k \in \mathbb{Z}\}\). Aby tato podmnožina byla podgrupou, musí splňovat uzavřenost, asociativitu, inverzi a obsahovat neutrální prvek.
Uzavřená je, neboť součtem dvou sudých čísel je opět sudé číslo. Asociativita zde platí taky, neboť sčítání je obecně asociativní. Neutrální prvek obsahuje, tím je nula a nakonec každý prvek má i inverzi, k libovolnému prvku \(a\) je to \(-a\) (např. k \(3\) je to \(-3\), neboť \(3+(-3) = 0\) ).
Pokud bychom brali jako podmnožinu všechna lichá čísla, tak nebudeme mít neutrální prvek ani uzavřenost (součet dvou lichých čísel je číslo sudé).
Důležité je si uvědomit, že každá grupa je podgrupou i sobě samé.
Podgrupový test
Každá podgrupa musí splňovat všechny axiomy grupy. Nyní si ale ukážeme, že nám stačí zkontrolovat jen dva, abychom měli o podmnožině libovolné grupy jistotu, zda jde, či nejde o podgrupu.
Věta o podgrupách: Neprázdná podmnožina \(H\) grupy \(G\) je podgrupou \(G\) právě tehdy, když jsou splněny dvě následující podmínky:
\(1\) Uzavřenost neboli pro všechny \(a, b \in H\) platí \(ab \in H\).
\(2\) Existence inverzí neboli pro všechny \(a \in H\) platí \(a^{-1} \in H\).
Důkaz věty o podgrupách
První dokažme \(\Rightarrow\), tedy tvrzení, že pokud je \(H\) podgrupa grupy \(G\), potom platí tvrzení \(1\) a \(2\). Ty ale platí automaticky, protože každá podgrupa musí splňovat všechny axiomy grupy (tedy i tyto dva).
Nyní dokažme \(\Leftarrow\), tedy tvrzení, že pokud libovolná podmnožina \(H\) grupy \(G\) splňuje \(1\) a \(2\), potom je automaticky podgrupou.
Musíme tedy ukázat, že takováto množina splňuje ještě asociativitu a obsahuje neutrální prvek. Vzhledem k tomu, že si vybíráme prvky z grupy a používáme danou operaci, musí i pro tyto vybrané prvky platit asociativita.
Dále vzhledem k tomu, že dle \(2\) existuje inverze ke každému prvku, musí k libovolně vybranému prvku \(a \in H\) existovat i \(a^{-1} \in H\). Podle tvrzení \(1\) také platí, že \(aa^{-1} \in H\) neboli \(e \in H\), čímž je důkaz hotov.
Upozornění pro další text: \(a^k\) není nutně zkrácený zápis pro násobení tak, jak jej známe, ale je to \(\underbrace {a \circ a \circ … \circ a}_{k-krát}\), kde \(\circ\) je libovolná grupová operace. Při tomto typu zápisu, pokud je naší operací sčítání, tedy např. místo \(a+a+a \) píšeme \(a^3\).
Cyklická podgrupa
Mějme konečnou grupu \(G\) a nechť \(a \in G\). Potom \(\langle a \rangle = \{a^n, n \in \mathbb Z\}\).
Ukážeme, že takováto množina vždy tvoří podgrupu. Mějme např. \( (\{1,2\} ; \cdot)\), kde \(\cdot\) je definováno tak, že spolu vynásobíme dva libovolné prvky a pak uděláme zbytek po dělení třemi. Potom \(\langle 1 \rangle = {1}\) – máme zde uzavřenost, neboť \(1 \cdot 1 = 1\), neutrální prvek (tím je ona jednička), inverzní prvek (opět jednička) i asociativitu \(1 \cdot (1 \cdot 1) = (1 \cdot 1) \cdot 1\).
A teď formálněji:
Důkaz
Podle předešlé věty nám stačí ukázat, že takto vytvořená množina vždy splňuje uzavřenost a že existují inverze.
Vyberme si nějaké \(x, y \in \langle a \rangle\), tj. existují taková \(k, l\), že \(x = a^k, y = a^l\). Potom \(xy = a^ka^l = a^{k+l}\), kde \(k+l\) je určitě celé číslo, tedy \(xy \in \langle a \rangle\). Tím jsme dokázali uzavřenost.
Nyní dokažme existenci inverzí. Vyberme si libovolné \(x \in \langle a \rangle\), tedy existuje takové \(k\), že \(x = a^k\). Vynásobme tuto rovnici zleva \(x^{-1}\) (\(x\) je z grupy, tedy v ní musí mít i nějakou inverzi) a dostáváme \(e = x^{-1}a^k\). Tuto rovnici vynásobme zprava \( (a^k)^{-1}\) (opět musí existovat z analogických důvodů) a dostáváme \(a^{-k} = x^{-1}\), což ale znamená, že \(x^{-1}\) zvládneme napsat jako \(a\) umocněné na nějaké celé číslo, tedy dle konstrukce patří do \(\langle a \rangle\). Tím je důkaz hotov.
Levý koset grupy
Vezmeme si nějakou podgrupu \(H\). Levým kosetem této podgrupy a prvku \(g\) této grupy budeme rozumět \(gH = \{g \circ h; g \in G, h \in H\} \). (Pravý koset definujeme analogicky).
Mějme např. grupu \( (\mathbb{Z}; +)\) a její podgrupu \(\{2k, k \in \mathbb{Z}\}\), tedy tato podgrupa obsahuje všechna sudá čísla. Potom levým kosetem prvku \(g = 3 \) a této podgrupy rozumíme množinu \(gH = \{3 + h; h \in H\}\), což je množina všech lichých čísel.
V tomto článku nás ale více budou zajímat konečné množiny, ukažme si tedy nějakou. Mějme grupu (že jde o grupu zde nebudeme dokazovat) zadanou tabulkou:
\[ \begin{array}{c|cccccc} \cdot & I & a & a^2 & b & ab & a^2b \\ \hline I & I & a & a^2 & b & ab & a^2b \\ a & a & a^2 & I & ab & a^2b & b \\ a^2 & a^2 & I & a & a^2b & b & ab \\ b & b & a^2b & ab & I & a^2 & a \\ ab & ab & b & a^2b & a & I & a^2 \\ a^2b & a^2b & ab & b & a^2 & a & I \\ \end{array} \]Vezměme si její podgrupu \(H = \{I, b\}\). Zkusme najít všechny levé kosety s touto podgrupou, tedy najdeme koset této podgrupy s prvkem \(I\), pak postupně s prvky \(a, a^2, b, ab, a^2b\).
První koset tedy je \(IH = \{I \cdot h; h \in H\} = \{I \cdot I, I \cdot b\} = \{I, b\}\).
Druhý \(aH = \{a, ab\}\).
Třetí \(a^2H = \{a^2, a^2b\}\).
Čtvrtý \(bH = \{b, I\}\).
Pátý \(abH = \{ab, a\}\).
Šestý \(a^2bH = \{ a^2b, a^2 \}\).
Zapišme si to do tabulky:
\[ \begin {array} {c|cc} \cdot & I & b \\ I & I & b \\ a & a & ab \\ a^2 & a^2 & a^b \\ b & b & I \\ ab & ab & a \\ a^2b & a^2b & a^2 \\ \end {array} \]Každý řádek je jeden koset. Všimněme si několika věcí – každý koset má stejný počet prvků – což není zvláštní, neboť jsme postupně násobili prvky v dvouprvkové množině. To ještě ale nezaručuje, že např. \(a \cdot I \neq a \cdot b\), čili (alespoň zatím, tuto jistotu hned získáme) nemáme obecně jistotu, že nám nikde nevznikne koset, jehož nějaké dva prvky jsou stejné.
Že nám vždy vzniknou kosety, jejichž všechny prvky jsou od sebe různé, nám zaručuje následující lemmátko.
Věta 1: Mějme grupu \(G\) s operací \(\cdot\). Potom \( a = b \Leftrightarrow ga = gb \) pro všechna \(a,b,g \in G\).
Důkaz: Implikace doprava je zřejmá, mám-li dva stejné prvky a vynásobím je stejným prvkem, na rovnosti se nic nezmění.
Implikace doleva není o moc složitější, mějme \(ga = gb\) a obě dvě strany vynásobme zleva prvkem \(g^{-1}\), dostáváme \(g^{-1}ga = g^{-1}gb\), odkud \(ea = eb\), tedy \(a = b\). (Samozřejmě \(g^{-1}\) musí existovat, neboť jsme v grupě, tedy máme zde inverzní prvky).
Také platí, že každý prvek \(g\) se nám objeví alespoň v jednom kosetu, neboť vytváříme koset prvku \(g\) s nějakou podgrupou – a aby to byla podgrupa, musí obsahovat neutrální prvek \(e\), čili nám v kosetu vzniká prvek \(g \circ e = g\).
V našem příkladu jednoduše ověříme, že identitou je prvek \(I\) a pak postupně vidíme, že prvek \(I\) je v kosetu \(IH\), \(a\) v kosetu \(aH\) atd.
Potom si všimněme, že velikost nosné množiny naší grupy byla rovna šestce. Tomuto budeme říkat řád grupy a budeme jej značit \(|G|\). Naše podgrupa měla řád dva. A dvojka dělí šestku – ač to zní jako náhodné výlevy a hledání souvislostí, kde nejsou, není tomu tak. Podívejme se na následující větu.
V. Lagrangeova věta – máme-li konečnou grupu \(G\), tak její řád je dělitelný řádem její libovolné podgrupy \(H\), tj. existuje kladné přirozené \(k\) tž. \(k|H| = |G|\).
Důkaz Lagrangeovy věty
V tomto důkazu využijeme kosetů. Většina důkazu bude zdánlivě o něčem nesouvisejícím – totiž o tom, že pokud mají dva kosety alespoň jeden prvek stejný, potom jsou celé stejné (jinými slovy se nám prvky grupy rozdělí do několika kosetů a nikde nebudou víckrát).
Uvažujme grupu \(G\) a její podgrupu \(H\). Mějme nějaké dva kosety, které mají alespoň jeden prvek stejný, tj. pro nějaká \(g_1, g_2 \in G\) platí \(g_1H \bigcap g_2H \neq \emptyset\), tj. průnik těchto dvou kosetů je neprázdný. Jinými slovy pro nějaká \(g_1, g_2, h_1, h_2\) platí, že \(g_1h_1 = g_2h_2\).
Vyberme si libovolné \(x \in g_1H\), tj. toto \(x\) se dá zapsat jako \(g_1h\) pro nějaké \(h \in H\).
Dostáváme
$$ x = g_1h = g_1eh = g_1(h_1h^{-1}_1)h = (g_1h_1)h^{-1}_1h = (g_2h_2)h^{-1}_1h = g_2(h_2h^{-1}_1h), $$
kde \(h_2h^{-1}_1h\) je určitě prvek z \(H\), neboť jde o (pod)grupu, tedy \(x = g_2(h_2h^{-1}_1h) \in g_2H\), což je přesně definice druhého kosetu, se kterým pracujeme.
Naprosto analogickým způsobem bychom dostali, že pro libovolné \(x\), které leží v \(g_2H\), platí, že leží také v \(g_1H\). Tedy dostáváme- pokud dva kosety obsahují dva stejné prvky, potom jsou všechny jejich prvky stejné.
Všechny kosety s danou podgrupou obsahují stejný počet prvků. Zároveň se nám do kosetů rozdělí všechny prvky grupy, jak jsme již ukázali. To ale znamená, že existuje takové celé kladné \(k\), že \(k|H| = |G|\) neboli že \(|G| = \frac{|H|}{k}\). Tím je důkaz hotov.
Tato věta nám tedy říká, že mám-li grupu s řádem \(6\), její libovolné podgrupy mohou mít buď \(1, 2\), nebo \(3\) prvky. (A grupa je podgrupou sobě samé, tedy může mít i \(6\) prvků).
Tuto větu zužitkujeme později.
Ještě si uvědomme, že tato věta neříká, že musí existovat podgrupa dané grupy o \(x\) prvcích, kde počet prvků grupy je dělitelný číslem \(x\). Ale říká, že pokud budou nějaké podgrupy dané grupy existovat, potom mohou mít právě tolik prvků.
Řád prvku
Řádem prvku \(a\) grupy \(G\) je řád cyklické podgrupy \(\langle a \rangle\).
Mějme příklad ze začátku tohoto článku, tedy \(\mathbb{Z_3}\) s násobením. Tam jsme měli, že \(|\langle 1 \rangle| = {1}\), řád prvku jedna je tedy roven jedné.
Je zřejmé, že když máme konečnou grupu, tak řád každého prvku je konečný.
Pro řád prvku dané grupy také platí, že je to takové nejmenší \(k\), pro které platí, že \(a^k = e\) (v modulárních grupách s násobením bude vždy \(e = 1\)). Např. v naší grupě bychom hledali takové \(k\), že \(1^k = 1\). Pro \(k = 1\) dostáváme, že \(1^1 = 1\).
Dokažme, že toto platí obecně. Tedy to, že
Věta 2.: Pokud je řád prvku \(a\) konečný, tak je roven takovému nejmenšímu přirozenému \(k\), že \(a^k = e\).
Důkaz: Předpokládejme, že \(k\) je doopravdy nejmenší přirozené číslo takové, že \(a^k = e\), ale řád prvku \(a\) je jiný než \(k\). Pokud by počet prvků grupy \(\langle a \rangle\) byl menší než \(k\) (tj. řád této grupy by byl méně než \(k\)), tak by mezi prvky \(a^0, a^1,…,a^{k-1}\) musely být dva stejné, tedy pro nějaká \(i,j\) menší než \(k\) by platilo, že \(a^i = a^j\). Bez újmy na obecnosti předpokládejme, že \(i < j\), tedy \(0 < j-i < k\).
Rovnici \(a^i = a^j\) můžeme vynásobit zprava prvkem \(a^{-i}\) a dostáváme, že \(e = a^{j-i}\), což je ale spor s tím, že \(k\) je nejmenší číslo takové, že \(a^k = e\).
Kdyby počet prvků grupy \(\langle a \rangle\) byl větší než \(k\), tak existuje nějaký prvek \(a^x\), kde \(x = l \cdot k+r\), kde \(0 \leq r < k-1\) (např. pokud by řád této podgrupy byl o jedna větší než \(k\), tak bychom psali, že \(x = 1 \cdot k+1\) a existovaly by zde vzájemně různé prvky \(a^0, a^1,…,a^k, a^x\)) . Vidíme, že ale pro tento prvek dostáváme \(a^x = a^{lk+r} = a^{lk}a^r = (a^k)^la^r = e^la^r = a^r\), což je ale jeden z prvků \(a^0\) až \(a^{k-1}\), což je spor s tím, že máme vzájemně různé prvky. Tím je důkaz hotov.
Eulerova funkce
Eulerova funkce \(\phi(n)\) je taková funkce, která spočítá, kolik menších nesoudělných přirozených čísel než \(n\) (tj. kolikrát vyjde, že \(\gcd(n,x) = 1\), kde \(x < n\)) existuje. Např. nesoudělná čísla s \(n = 10\) jsou \(\{1, 3, 7, 9\}\), tj. \(\phi(10) = 4\).
Eulerova věta
Chceme ukázat, že pokud je \(n \in \mathbb{N}, n \geq 2\) a libovolné přirozené \(a\) s ním nesoudělné, tak
$$ a^{ \phi (n)} \equiv 1 \pmod{n} $$
Mějme pro lepší představu nějaké konkrétní \(n\), např. \(10\), kde již víme, že nesoudělná čísla jsou \(\{1, 3, 7, 9\}\) a že \(\phi(10) = 4\).
Tato čísla tvoří grupu v modulo \(n\) (v našem případě v \(\bmod 10\)) s násobením a řád grupy \(|G| = \phi(10) = 4\). To znamená, že zde máme uzavřenost na operaci, neutrální prvek, asociativitu a inverzní prvek.
Než ukážeme asociativitu, zadefinujme si tu násobení v \(\bmod n\).
Mějme \(\mathbb{Z_n}\), potom součinem dvou prvků z \(\mathbb{Z_n}\) rozumíme \([a]_n \times [b]_n\) a definujeme jej následovně: \([a]_n \times [b]_n =[a \cdot b]_n\).
Pokud tento zápis není jasný, tak si vyberme nějaké konkrétní \(n\), třeba \(5\). Potom \(\mathbb{Z_n} = \{0,1,2,3,4\}\). Hranatá závorka nám značí, že s prvkem v ní máme provést \(\bmod n\) (tj. zbytek po dělení), v našem případě \(\bmod 5\). Takže např. \([23]_5 = 23 \bmod 5 = 3\).
Uzavřenost ukažme jen namátkou:
$$ [3]_{10} \times [7]_{10} = [3 \cdot 7]_{10}= [21]_{10} = 1, \\ [9]_{10} \times [9]_{10} =[9 \cdot 9]_{10}= [81]_{10}=1, \\ [7]_{10} \times [9]_{10}= [7 \cdot 9]_{10} = [63]_{10} = 3, \\ … $$
Stejně tak asociativitu v \(\bmod 10\) ukažme jen namátkou:
$$ [3]_{10} \times ([12]_{10} \times [84]_{10}) = [3]_{10} \times [12 \cdot 84]_{10} = [3 \cdot 12 \cdot 84]_{10} = [3024]_{10} = 4 \\ ([3]_{10} \times [12]_{10}) \times [84]_{10} = ([3]_{10} \times [12]_{10}) \times [84]_{10} = [3 \cdot 12]_{10} \times [84]_{10} = [3 \cdot 12 \cdot 84]_{10} = [3024]_{10} = 4 \\ … $$
Neutrálním prvkem je jednička. Ještě zbývá nalézt inverzní prvek – tj. takový prvek, který při složení s vybraným prvkem, vrátí jedničku. K \(1\) je inverzní \(1\), neboť \(1 \cdot 1 \bmod 10 = 1\). Ke trojce je inverzní sedmička, neboť \(3 \cdot 7 \bmod 10 = 1\). K sedmičce je inverzní trojka, protože násobení je komutativní. K devítce je inverzní devítka, neboť \(9 \cdot 9 \bmod \ 10 = 1\). Nyní jsme tedy ukázali, že v tomto konkrétním příkladě, tj. v množině všech nesoudělných čísel s naším \(n = 10\) s násobením, jde o grupu.
Vyberme si libovolné \(a\) z naší grupy, třeba číslo \(9\). Tento prvek generuje podgrupu \(\langle 9 \rangle = \{9,1\}\). Toto je v souladu s tím, že jsme měli najít nejmenší \(k\) takové, že \(9^k \bmod 10 = 1\), což řeší právě \(2\) a vygenerovaná množina má doopravdy \(2\) prvky.
Podle Lagrangeovy věty řád této podgrupy musí dělit řád dané grupy – což tu přesně máme, protože řád grupy je roven čtyřce a řád této podgrupy dvojce (a \(4/2 = 2\) beze zbytku). Můžeme tedy psát, že \(\phi(10) = 4 = 2 \cdot k = 2 \cdot 2\). Máme tedy, že \(a^{\phi(10)} = 9^{\phi(10)} = 9^{2 \cdot 2} = (9^2)^2 = 1^2 = 1\), kde máme pořád „rovná se“ z modulární grupy. Dostáváme tedy, že \(9^4 \mod \ 10 = 1\), což je v souladu s tím, co jsme měli dokázat.
Ukažme si to nyní abstraktně pro všechny možné modulární grupy!
První musíme ukázat, že máme-li nějaké \(n\) a s ním všechna jeho menší nesoudělná čísla (jinými slovy – máme množinu všech \(x<n\) takových, že \(gcd (n,x) = 1\)), tak tato čísla tvoří grupu \(G\) s násobením v \(\mod \ n \).
Jako první ukažme uzavřenost – vyberme si nějaké dva prvky \(a, b \in G\), na kterých chceme ukázat, že \(\gcd(a,n) = 1 \land \gcd (b,n) = 1 \Rightarrow \gcd (ab, n) = 1\).
Uvědomme si, že pokud \( \gcd (ab, n) = 1\), potom i \(\gcd([a]_n \times [b]_n, n) = 1\).
Předpokládejme pro spor, že \(gcd(a,n) = 1 \land gcd (b,n) = 1 \land gcd (ab, n) \neq 1\).
To, že \(gcd (ab, n) \neq 1\) ale znamená, že zlomek \(\frac{ab}{n}\) se dá zkrátit. Proč? Představme si, že máme zlomek \(\frac{27 \cdot 26}{6}\). Tam můžeme zkrátit \(27\) s \(6\), neboť obě čísla jsou dělitelná právě trojkou.
To ale znamená, že se buď to dá nějakým číslem krátit buď \(a\) s \(n\), tj. \(gcd(a,n) \neq 1\), anebo, že se dá nějakým číslem krátit \(b\) s \(n\), tj. \(gcd(b,n) \neq 1\), což je ale spor. Tím je důkaz uzavřenosti hotov.
Ukažme nyní, že v naší grupě zbytků máme asociativitu, tj. chceme ukázat, že \([a]_n \times ([b]_n \times [c]_n) = ([a]_n \times [b]_n) \times [c]_n\).
Pišme tedy \([a]_n \times ([b]_n \times [c]_n) = [a]_n \times [b \cdot c]_n = [abc]_n\).
Potom taky \( ([a]_n \times [b]_n) \times [c]_n = [a \cdot b]_n \times [c]_n = [abc]_n\), čili vidíme, že dokazovaná rovnost opravdu platí, a dokázali jsme asociativitu.
Neutrálním prvkem je nám zde \(1\), která v grupách nesoudělných čísel vždy bude, neboť pro všechna \(n\) platí, že \(gcd(n,1) = 1. \)
Nakonec musíme ukázat, že vždy máme inverzní prvek, tedy že každému \(x \in G\) existuje nějaký prvek (který značme \(x^{-1}\)), že \(xx^{-1} \ mod \ n = 1\) neboli že \(xx^{-1} \equiv 1 \pmod n\). Takový prvek vždy najdeme tzv. rozšířeným Eukleidovým algoritmem, jehož popis najdete v tomto článku v odstavci jménem Rozšiřený Eukleidův algoritmus. \(x\) již podle konstrukce není soudělné s \(n\). Ukažme, že i \(x^{-1}\) je nesoudělné s \(n\).
Předpokládejme pro spor, že \(\gcd(x^{-1}, n) > 1\). Z toho ale nutně plyne, že \(\gcd(xx^{-1}, n) >1 \). My ale víme z \(xx^{-1} \equiv 1 \pmod n\), že \(xx^{-1} = 1+kn\) a musí platit, že \( \gcd(xx^{-1}, n) = \gcd( 1+kn, n) = 1\), což je spor.
Co kdyby naše \(x^{-1} > n\), neměli bychom problém s tím, že by nepatřilo do naší grupy? Neměli.
Hledat \(x^{-1}\) takové, že \(xx^-1 \equiv 1 \pmod n\) je ekvivalentní s tím, že \(xx^{-1}-1 = kn\) neboli \(xx^{-1}-kn = 1\). Pokud \(x^{-1} > n\), tak pišme \(x^{-1}x-kn-nx+nx = 1\), kde jsem jen přičetl nulu. To ale můžeme přepsat na \( (x^{-1}-n)x+(x-k)n = 1\), odkud \( (x^{-1}-n)x-1 = (k-x)n\), což je ekvivalentní s \( (x^{-1}-n)x \equiv 1 \pmod n\), takže máme inverzi k \(x\), konkrétně \(x^{-1}-n\). Pokud by ani tento prvek nebyl menší než \(n\), potom provedeme úplně stejný postup a nalezneme \(x^{-1}-2n\) atd. až dojdeme k číslu menšímu než \(n\)
Zjistili jsme tedy, že nesoudělná čísla s \(n\) a menší než \(n\) tvoří grupu s operací násobení v \(\mod \ n\). Řád této grupy je \(\phi(n)\).
Nyní si vyberu libovolné \(a\) z mé grupy. Tento prvek generuje nějakou podgrupu \(\langle a \rangle\), která je určitě konečná a existuje (podle Věty 2) takové nejmenší \(k\), že \(a^k = 1\).
Víme, že toto \(k\) je právě počet prvků dané podmnožiny a podle Lagrangeovy věty musí toto číslo dělit číslo \(\phi(n)\), tj. existuje takové \(m\), že \(mk = \phi(n)\). Máme tedy, že \(a^{\phi(n)} = a^{mk} = (a^k)^m= 1^m = 1\). Všechny tyto úpravy jsme ale udělali v modulární grupě, dohromady tedy máme, že \(a^{\phi(n)} \bmod n = 1\), což jsme chtěli dokázat.
Přehled toho, co se stalo
Máme \(n \geq 2\) a s ním nesoudělné \(a\). Ukážeme, že nesoudělná čísla s \(n\) a zároveň menší než \(n\) tvoří grupu s násobením v \(\bmod n\). Pak si vyberu libovolné \(a\) nesoudělné s \(n\), čili z naší grupy.
Tento prvek generuje nějakou podgrupu a podle Lagrangeovy věty řád této podgrupy dělí řád této grupy (který je \(\phi(n)\)), tedy pro řád \(r\) nějaké podgrupy platí, že \(r*k = \phi(n)\) pro nějaké přirozené \(k\).
Tedy \(a^{\phi(n)} = a^{r*k} = (a^r)^k\), ale prvek generující podgrupu na řád této podgrupy je roven neutrálnímu prvku \(e\) (v našem případě \(e=1\)), odtud tedy \(a^{\phi(n)} = (a^r)^k = 1^k = 1\), neboli \(a^{\phi(n)} = 1 \pmod n\).
Eulerova funkce pro prvočísla
Mějme nějaké prvočíslo \(p\) (pokud je třeba, tak pro krátké povídání o prvočíslech opět odkazuji na stejný článek jako výše v tomto článku, konkrétně odstavec „Jak ověřit, že je číslo prvočíslem“). Potom \(\phi(p) = p-1\). Toto není těžké náhlednout – vyberme si pro příklad nějaké prvočíslo, třeba \(7\). Číslo \(1\) je nesoudělná s každým číslem, tedy i se sedmičkou. Číslo \(2\) je nesoudělné se \(7\), neboť kdyby bylo soudělné, musela by čísla \(7\) a \(2\) obsahovat ve svém rozkladu nějaké číslo větší než jedna a menší nebo rovno dvěma. To by ale znamenalo, že číslo \(7\) není prvočíslem. Obdobně pro čísla \(3, 4, 5, 6\), dostáváme tedy, že \(\phi(7) = 7-1 = 6\).
Stejné argumenty můžeme provést pro všechna prvočísla. Již víme, že platí
$$ a^{ \phi (n)} \equiv 1 \pmod{n}. $$
Vyberme si za naše \(n\) libovolné prvočíslo. Potom platí, že
$$ a^{ \phi (p)} \equiv 1 \pmod{p}, $$
odkud, podle právě řečených argumentů máme
$$ a^{p-1} \equiv 1 \pmod{p}, $$
což není nic jiného než Malá Fermatova věta! Po tomto důkazu jsme tedy dostali důkaz Malé Fermatovy věty krásně skrz to, že víme, co jsou grupy.