Ak $|G|=n$, tak $a^n=1_G$

[Martin Sleziak]

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.

Spoiler:

Riešenie.
Vieme, že v grupe platia zákony o krátení, t.j. ak $a_i\ne a_j$, tak $a\cdot a_i\ne a\cdot a_j$.
To znamená, že $aa_1,\dots,aa_n$ je $n$ navzájom rôznych prvkov. Keďže $|G|=n$, znamená to, že sú to všetky prvky z grupy $G$, a teda
$$G=\{aa_1,\dots,aa_n\}.$$

Ak teraz zapíšeme dvoma spôsobmi súčin všetkých prvkov z $G$, tak máme
$$a_1\cdots a_n=(aa_1)\cdots(aa_n).$$
(Všimnime si, že aj tu sme už využili komutatívnosť - nezáleží na tom, v akom poradí napíšem v tomto súčine prvky z grupy $G$.)

Vďaka komutatívnosti môžeme túto rovnosť ešte prepísať ako
$$a_1\cdots a_n=a^na_1 \cdots a_n.$$
A ak opäť využijeme zákony o krátení, tak máme
$$1_G=a^n.$$
Tým sme dokázali časti a) aj b). $\square$

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$.

[Martin Sleziak]

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.

Spoiler:

Aby som bol úplne presný, tak ste mali prednáškovú úlohu o tom, že medzi ľubovoľnými dvoma triedami rozkladu $G$ podľa $H$ existuje bijekcia.
Teda počet prvkov každej triedy je $|H|$.
To znamená, že $|G|$ je rozdelená na konečný počet disjunktných častí, z ktorých každá má počet prvkov $|H|$.
Z toho už je jasné, že počet prvkov grupy $G$ sa rovná počtu tried vynásobenému číslom $|H|$.

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$.

Spoiler:

Predpokladajme, že máme nejaké $s,t\in\mathbb N_0$ také, že $s<t$ a súčasne
$$a^s=a^t.$$
Navyše predpokladajme, že $s$ aj $t$ sme zobrali najmenšie možné.

Ak by platilo $s>0$, tak máme $a^{s-1}=a^{t-1}$ a dostaneme spor s minimalitou čísel $s$, $t$.

Teda musí platiť $s=0$ a
$$a^t=a^s=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$.

Spoiler:

Pre ľubovoľné dva prvky $x,y\in H$ máme ich vyjadrenie ako $x=a^i$ a $y=a^j$. Potom platí
\begin{align*}
x\cdot y&=a^i\cdot a^j=a^{i+j},\\
x\cdot y&=a^r,
\end{align*}
kde ako $r$ sme označili zvyšok čísla $(i+j)$ po delení číslom $k$.

Spoiler:

Pretože $i+j=qk+r$, tak máme
$$a^{i+j}=a^{qk+r}=(a^k)^q\cdot a^r=(1_G)^q\cdot a^r=1_G\cdot a^r=a^r.$$

Stručne: Ak sme exponent zmenili o násobok čísla $k$, tak sme neovplyvnili hodnotu mocniny.

Teda aj súčin vieme vyjadriť v tvare $x\cdot y=a^r$ pre nejaké číslo $r\in\mathbb Z$ také, že $0\le r<k$. Tým sme skontrolovali, že 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$.

[Martin Sleziak]

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.

Spoiler:

Napríklad ak $p=7$, tak máme
\begin{align*}
1^6&=1\\
2^6&=(2^3)^2=1^2=1\\
3^6&=(3^2)^3=2^3=1\\
4^6&=(-3)^6=1\\
5^6&=(-2)^6=1\\
6^6&=(-1)^6=1
\end{align*}

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$.

Spoiler:

V $\mathbb Z_7$ dostaneme
\begin{align*}
1^5&=1\\
2^5&=2^3\cdot2^2=4\\
3^5&=(3^2)^2\cdot3=2^2\cdot3=4\cdot3=5\\
4^5&=(4^2)^2\cdot4=2^2\cdot4=4\cdot4=2\\
5^5&=(5^2)^2\cdot5=4^2\cdot5=2\cdot5=3\\
6^5&=(-1)^5=-1=6
\end{align*}
Skutočne sme ku každému prvku dostali jeho multiplikatívny inverz:
\begin{align*}
1^{-1}&=1\\
2^{-1}&=4\\
3^{-1}&=5\\
4^{-1}&=2\\
5^{-1}&=3\\
6^{-1}&=6
\end{align*}

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$.

Spoiler:

Ak sme už vypočítali $a^s$, tak vieme vypočítať pomerne rýchlo $a^{2s}=(a^s)^2$. A vcelku rýchlo sa vieme dostať aj k $a^{2s+1}=a^{2s}\cdot a$.

Napríklad ak by sme počítali $a^{39}$, tak sa k nemu vieme dostať pomocou $a^{19}$. Takisto $a^{19}=a^{2\cdot9+1}$ vieme dostať z $a^9$.
T.j. postupne by sme počítali:
\begin{align*}
a^1&=a\\
a^2&=a^2\\
a^4&=(a^2)^2\\
a^8&=(a^4)^2\\
a^9&=a^8\cdot a\\
a^{18}&=(a^9)^2\\
a^{19}&=a^{18}\cdot a\\
a^{38}&=(a^{19})^2\\
a^{39}&=a^{38}\cdot a
\end{align*}

Na výpočet $a^k$ potrebujeme rádovo toľko krokov, koľko cifier má číslo $k$ zapísané v dvojkovej sústave.

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.

Spoiler:

\begin{align*}
31^2&\equiv 52 \pmod{101}\\
31^3&\equiv 52\cdot31 \equiv 97 \equiv -4 \pmod{101}\\
31^6&\equiv (-4)^2\equiv 16 \pmod{101}\\
31^{12}&\equiv 54 \pmod{101}\\
31^{24}&\equiv 54^2 \equiv -13 \pmod{101}\\
31^{48}&\equiv (-13)^2 \equiv 68 \equiv -33 \pmod{101}\\
31^{49}&\equiv -33\cdot31 \equiv -(32^2-1) \equiv -1023 \equiv -13 \pmod{101}\\
31^{98}&\equiv (-13)^2 \equiv -33 \pmod{101}\\
31^{99}&\equiv -33\cdot31 \equiv -13 \equiv 88 \pmod{101}
\end{align*}

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:

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}$.

Spoiler:

V $\mathbb Z_p$ pre $a\ne 0$ skutočne platí $$a\cdot x=a\cdot y \Rightarrow x=y.\tag{*}$$
Môžeme to zdôvodniť napríklad tak, že ak $ax$ aj $ay$ dávajú rovnaký zvyšok po delení číslom $p$, znamená to, že
$$p\mid ax-ay = a(x-y).$$
Keďže $p$ je prvočíslo a delí súčin $a(x-y)$, tak musí deliť niektorý z týchto dvoch činiteľov. Pretože $p\nmid a$, tak máme $p\mid x-y$.
Číslo $x-y$ je celé číslo také, že $-(p-1)\le x-y \le p-1$. Jediný násobok $p$ v tomto rozsahu je nula. Teda máme $x-y=0$ a $$x=y.$$

Všimnime si, že z $(*)$ vieme dostať aj to, že v $\mathbb Z_p$ platí:
$$ax=0 \Rightarrow a=0 \lor x=0.$$
Túto podmienku môžeme ekvivalentne prepísať ako
$$a\ne 0\land x\ne 0 \Rightarrow ax\ne0.$$
To vlastne hovorí to, že násobenie modulo $p$ je binárna operácia na množine $\mathbb Z_p\setminus\{0\}$.