msleziak.com

Definícia $a^n$

Majme grupu $(G,\cdot)$ a nejaký prvok $a\in G$.

Pre $n=1,2,\dots$ vieme definovať
$$a^n=\underset{\text{$n$-krát}}{\underbrace{a\cdot a \cdots a}}.$$
Bude sa nám hodiť používať aj $a^0=1_G$. (Toto je asi prirodzená voľba.)

Formálnejšie by sme to mohli definovať indukciou:
$1^\circ$ $a^0=1$

$2^\circ$ $a^{n+1}=a^n\cdot a$

Všimnime si, že v definícii nenápadne používame asociatívnosť (nepíšeme zátvorky).
Napríklad $a^3=(a\cdot a)\cdot a=a\cdot(a\cdot a)$

Asi by nemalo byť ťažké si rozmyslieť, že pre $n,k\in\mathbb N_0$ platí:
\begin{align*}
a^{n+k}&=a^n\cdot a^k\\
a^{nk}&=(a^n)^k
\end{align*}
(Opäť upozorním, že v dôkazoch využívame asociatívnosť.)

(Vedeli by sme nejako zmysluplne definovať aj $a^{-1}, a^{-2}, a^{-3}, \dots$. Tu to však nebudeme potrebovať, takže na tomto mieste sa im nejdem venovať.)

Komutatívny prípad

Na jednom z cvičení sme si rozmysleli takúto vec, ktorá je v sade úloh o binárnych operáciách a grupách:

Nech $G$ je konečná komutatívna grupa, $|G|=n$. Neutrálny prvok tejto grupy označme $e$ a jej prvky označme ako $a_1,\dots,a_n$ (t.j. ).
a) Ukážte, že pre ľubovoľné $a\in G$ platí $G=\{aa_1,\dots,aa_n\}$.
b) Ukážte, že pre ľubovoľné $a\in G$ platí $a^n=1_G$.
(Poznámka: Takéto tvrdenie platí aj pre nekomutatívnej grupy -- v tom prípade ale treba použiť iný argument. Dá sa to odvodiť napríklad ako dôsledok Lagrangeovej vety, ktorú stručne spomenieme aj na tomto predmete.)

Jedna z možností ako povedať základnú ideu je to, že $x\mapsto a*x$ je bijekcia $G\to G$. (V riadku $a$ tabuľky grupovej operácie sa vyskytne každý prvok grupy práve raz.)

Ak niekto chce vyskúšať, či sa mu už po prezradení základnej myšlienky podarí urobiť dôkaz, tak ten som skryl ako spoiler.
Ak sa detailnejšie pozrieme na to, ako fungoval dôkaz, tak presne rovnako by sme vedeli dokázať:
Ak $G$ je konečná množina, $\cdot$ je binárna operácia na $G$, ktorá je komutatívna, asociatívna a platia pre ňu zákony o krátení, tak:
a) Pre ľubovoľné $a\in G$ platí $G=\{aa_1,\dots,aa_n\}$.
b) Pre ľubovoľné $a\in G$ platí $a^n=1_G$.

Lagrangeova veta

Medzičasom ste už stretli Lagrangeovu vetu.
Teda viete, že ak mám konečnú grupu $G$ a nejakú jej podgrupu $H$, tak počet prvkov podgrupy je deliteľ počtu prvkov celej grupy.
$$|H| \mid |G|$$
Často ju nájdete zapísanú aj v tvare $|G|=[G:H]\cdot|H|$, kde symbol $[G:H]$ označuje počet tried. Keď si človek pozorne pozrie dôkaz, tak zistí, že sme nikde nepotrebovali komutatívnosť. (Aj keď na tomto predmete nás zaujímajú faktorové grupy najmä pre komutatívne grupy; takže sme sa venovali primárne tým.)

Ako to súvisí s tým, o čom sme hovorili doteraz?

Povedzme, že máme grupu $(G,\cdot)$ a nejaký prvok $a\in G$.
Ak sa pozeráme na prvky $a^0=1_G,a^1,\dots,a^s,\dots$, tak sa v tejto postupnosti určite nejaké prvky zopakujú (pretože máme iba konečne veľa prvkov).
A nie je veľmi ťažké si uvedomiť, že prvý prvok, ktorý sa vyskytne dvakrát, bude $1_G$. Označme si $k$ najmenší exponent, kedy sme znovu dostali $a^k=1_G$.
Máme teda $k$ rôznych prvkov $a^0,a^1,\dots,a^{k-1}$ a všetky ďalšie mocniny prvku a sa už opakujú. (Platí $a^{s+k}=a^s$.)
Takéto $k$ sa zvykne volať aj rád prvku $a$.

Ešte si treba rozmyslieť, že
$$H=\{1_G,a,a^2,\dots,a^{k-1}\}=\{a^j; j\in\mathbb Z, 0\le j<k\}$$
je podgrupa grupy $G$.
Máme neprázdnu konečnú podmnožinu, teda stačí kontrolovať uzavretosť na operáciu. Teda overiť, či pre $x,y\in H$ aj $x\cdot y\in H$. Z Lagrangeovej vety potom dostaneme, že $k$ musí byť deliteľ čísla $|G|=n$. (Teda rád ľubovoľného prvku delí počet prvkov grupy.)

Teda $n=k\cdot l$ pre nejaké prirodzené číslo $l$. To znamená, že
$$a^n = a^{kl} = (a^k)^l = 1_G^l=1_G.$$
Pomocou Lagrangovej vety sme teda vedeli zdôvodniť, že aj pre nekomutatívne grupy platí $a^n=1_G$.

Pole $\mathbb Z_p$

V čase, keď už vieme niečo o poliach, tak sa nezaškodí vrátiť ešte raz k tejto istej úlohe.

Ak vieme, že pre každé prvočíslo je $\mathbb Z_p$ poľom, tak môžeme výsledok spomenutý vyššie aplikovať na grupu $(\mathbb Z_p\setminus\{0\},\cdot)$. Táto grupa má $(p-1)$ prvkov, a teda máme $$a^{p-1}=1$$ pre každé $a\in\mathbb Z_p\setminus\{0\}$. (Pričom mocninu tu chápeme tak, že počítame modulo $p$.)

Môžete si ľahko vyskúšať, že takéto niečo naozaj funguje pre malé prvočísla. Týmto sme vlastne dokázali malú Fermatovu vetu, ktorú zvyčajne nájdete sformulovanú pomocou kongruencií.

Malá Fermatova veta. Nech $p$ je prvočíslo a $a$ je celé číslo také, že $p\nmid a$. Potom platí $$a^{p-1}\equiv 1 \pmod p.$$

Ekvivalentne môžeme malú Fermatovu vetu sformulovať aj tak, že pre každé $a\in\mathbb Z$ platí $a^p \equiv a \pmod p$. (Pri počítaní v $\mathbb Z_p$ by sme to isté namiesto kongruencií priamo mohli sformulovať ako rovnosť $a^p=a$ pre každé $a\in\mathbb Z_p$.)

Výpočet inverzného prvku. Už sme videli, že inverzný prvok v $\mathbb Z_p$ môžeme hľadať pomocou rozšíreného euklidovho algoritmu: viewtopic.php?t=1346
Nie je na škodu si uvedomiť, že vlastne sme dostali v $\mathbb Z_p$ rovnosť
$$a^{-1}=a^{p-2},$$
čo nám dáva inú možnosť ako získať inverzný prvok k danému číslu $a\in\mathbb Z_p$.

Opäť si to môžete vyskúšať pre nejaké malé prvočíslo $p$. Oplatí sa zamyslieť aj nad tým, že mocninu $a^k$ vieme vypočítať aj rýchlejšie než postupným počítaním všetkých mocnín $a, a^2, a^3, \dots, a^k$. Wikipédia: Exponentiation by squaring

V inom topicu sme vypočítali $31^{-1}$ v $\mathbb Z_{101}$ pomocou euklidovho algoritmu: viewtopic.php?t=1346
Ak by sme ho chceli vypočítať takto, tak potrebujeme v $\mathbb Z_{101}$ vypočítať $31^{99}$. Môžete si vyskúšať, že by sme sa dostali k tomu istému výsledku. Dôkaz, že $\mathbb Z_p$ je pole

Ak si všimneme, čo sme používali v zdôvodnení že $a^n=1$, tak sme nepotrebovali všetky vlastnosti grupy; to sme spomenuli už skôr:

Martin Sleziak wrote: ↑Tue Nov 07, 2023 6:33 pm Ak sa detailnejšie pozrieme na to, ako fungoval dôkaz, tak presne rovnako by sme vedeli dokázať:
Ak $G$ je konečná množina, $\cdot$ je binárna operácia na $G$, ktorá je komutatívna, asociatívna a platia pre ňu zákony o krátení, tak:
a) Pre ľubovoľné $a\in G$ platí $G=\{aa_1,\dots,aa_n\}$.
b) Pre ľubovoľné $a\in G$ platí $a^n=1_G$.

Toto by sa dalo použiť v dôkaze, že pre prvočíslo $p$ je okruh $(\mathbb Z_p,+,\cdot)$ poľom. (Nejaký dôkaz tohto faktu sme už videli na prednáške.)
Ak by sme nejako vedeli zdôvodniť, že v $\mathbb Z_p\setminus\{0\}$ platia zákony o krátení, tak pri dôkaze existencie inverzného prvku môžeme použiť toto tvrdenie a dostať tak, že inverzný prvok je $a^{p-2}$.