Čtení: 40 minHodnotí se: písemka, ústní (minikvízy 1 a 2 máš splněné)

1 Grupy, podgrupy a generátory

Po přečtení umíš

poznat grupoid, pologrupu, monoid a grupu
najít podgrupy a použít Lagrangeovu větu
spočítat řád prvku a najít generátory
rychle mocnit díky řádu prvku

Tato látka je základ pro konečná tělesa a kryptografii. Minikvízy 1 a 2 máš hotové, kapitola tedy slouží hlavně k písemce a ústní zkoušce.

1.1 Ukázka: hodiny

Na hodinách s 12 pozicemi počítáme modulo 12. Začneme v 0 a skáčeme po 4: 0, 4, 8, 0. Dostaneme jen tři čísla a pak se zacyklíme. Se skokem 5 projdeme všech 12 pozic, protože 5 a 12 jsou nesoudělné.

Vlevo skok 4 navštíví jen 3 pozice, vpravo skok 5 všech 12.

Tomu odpovídají pojmy: skok 4 má řád 3, skok 5 je generátor a množina $\{0, 4, 8\}$ je podgrupa.

1.2 Struktury

Definice 1.2 (Grupoid až grupa)

Grupoid: množina s binární operací, výsledek zůstává v množině.
Pologrupa: navíc asociativita.
Monoid: navíc neutrální prvek.
Grupa: navíc inverze ke každému prvku.
Abelovská grupa: navíc komutativita.

Příklady: $(\mathbb{N}, +)$ s nulou je monoid, ale ne grupa, protože chybí opačná čísla. $(\mathbb{Z}, +)$ je abelovská grupa. $\mathbb{Z}_n^+$ je sčítání modulo $n$ . $\mathbb{Z}_n^\times$ je násobení modulo $n$ na číslech nesoudělných s $n$ .

Příklad 1.3 (Prvky

\mathbb{Z}_{12}^\times

)

Bereme čísla nesoudělná s 12: $\{1, 5, 7, 11\}$ . Grupa má řád 4.

1.3 Podgrupy a Lagrange

Definice 1.4 (Podgrupa)

Podmnožina, která je sama grupou se stejnou operací. U konečné grupy stačí uzavřenost.

Věta 1.5 (Lagrangeova věta)

Řád podgrupy dělí řád grupy.

Grupa řádu 12 tedy může mít podgrupy jen řádu 1, 2, 3, 4, 6, 12. Podgrupa řádu 5 v ní neexistuje. Grupa prvočíselného řádu má jen triviální podgrupy.

1.4 Řád prvku

Definice 1.6 (Řád prvku)

Nejmenší kladné $k$ , pro které $a^k = e$ . U sčítání $k \cdot a = 0$ .

Věta 1.7 (Důsledky)

Řád prvku dělí řád grupy. Proto $a^{|G|} = e$ a $a^m = a^{m \bmod \operatorname{ord} a}$ .

V $\mathbb{Z}_n^+$ platí jednoduchý vzorec: $\operatorname{ord} a = n / \gcd(a, n)$ .

Příklad 1.8 (Řády v

\mathbb{Z}_7^\times

)

Grupa má řád 6, řády tedy dělí 6. Spočítejme mocniny:

$a$	1	2	3	4	5	6
$\operatorname{ord} a$	1	3	6	3	6	2

Prvky 3 a 5 mají řád 6, jsou to generátory. Prvek 2 generuje jen podgrupu $\{1, 2, 4\}$ .

Příklad 1.9 (Rychlé mocnění)

Spočítej $3^{100} \bmod 7$ . Řád 3 je 6 a $100 \bmod 6 = 4$ , takže stačí $3^4 = 81 \equiv 4$ .

1.5 Cyklické grupy a generátory

Definice 1.10 (Cyklická grupa)

Grupa je cyklická, pokud ji celou vygeneruje jeden prvek.

Věta 1.11 (Generátory)

Cyklická grupa řádu $n$ má $\varphi(n)$ generátorů. Je-li $g$ generátor, pak $g^k$ je generátor právě tehdy, když $\gcd(k, n) = 1$ . Pro každý dělitel $d$ řádu existuje právě jedna podgrupa řádu $d$ .

Příklad 1.12 (Podgrupy

\mathbb{Z}_{12}^+

)

Generátory jsou $1, 5, 7, 11$ . Podgrupy odpovídají dělitelům 12: $\langle 1 \rangle$ řádu 12, $\langle 2 \rangle$ řádu 6, $\langle 3 \rangle$ řádu 4, $\langle 4 \rangle$ řádu 3, $\langle 6 \rangle$ řádu 2, $\langle 0 \rangle$ řádu 1.

Test generátoru: prvek $g$ v grupě řádu $n$ je generátor, když $g^{n/q} \ne e$ pro každé prvočíslo $q$ dělící $n$ .

Příklad 1.13 (Je 3 generátor

\mathbb{Z}_7^\times

$n = 6 = 2 \cdot 3$ . Ověř $3^{3} = 27 \equiv 6 \ne 1$ a $3^{2} = 9 \equiv 2 \ne 1$ . Ano.

Varování 1.14 (Ne každá

\mathbb{Z}_n^\times

je cyklická)

$\mathbb{Z}_8^\times = \{1, 3, 5, 7\}$ má řád 4, ale každý prvek kromě 1 má řád 2. Pro prvočíslo $p$ je $\mathbb{Z}_p^\times$ cyklická vždy.

1.6 Typické chyby

Záměna řádu grupy a řádu prvku.
$\mathbb{Z}_n^\times$ bez vyřazení soudělných čísel.
Zkoušení všech mocnin místo dělitelů řádu.
Závěr, že $\mathbb{Z}_n^\times$ je vždy cyklická.

1.7 Kvíz

Kvíz

1. Co chybí

(\mathbb{N}_0, +)

k tomu, aby byla grupa? Asociativita Neutrální prvek Inverzní prvky

2. Jaký je řád prvku 8 v

\mathbb{Z}_{12}^+

? Odpověď:

3. Může mít grupa řádu 15 podgrupu řádu 4? Ano Ne

4. Kolik generátorů má

\mathbb{Z}_7^\times

? Odpověď:

5. Kolik je

3^{100} \bmod 7

? Odpověď:

6. Co platí pro cyklickou grupu řádu 12? Může být správně více možností, ale také žádná. Je abelovská Má

\varphi(12) = 4

generátory Má podgrupu řádu 5 Má právě jednu podgrupu řádu 6

7. Proč v grupě platí

a^{|G|} = e

Ukázat řešení

Řád prvku je řád cyklické podgrupy, kterou generuje. Podle Lagrange dělí

|G|

, takže

|G| = k \cdot \operatorname{ord} a

a^{|G|} = (a^{\operatorname{ord} a})^k = e

1.8 Příklady na procvičení

Cvičení 1.15

Najdi všechny generátory $\mathbb{Z}_{10}^+$ .

Řešení

Čísla nesoudělná s 10: $1, 3, 7, 9$ . Je jich $\varphi(10) = 4$ .

Cvičení 1.16

Je 2 generátor $\mathbb{Z}_{11}^\times$ ?

Řešení

Řád grupy je $10 = 2 \cdot 5$ . Ověř $2^5 = 32 \equiv 10 \ne 1$ a $2^2 = 4 \ne 1$ . Ano, je.

Cvičení 1.17

Najdi všechny podgrupy $\mathbb{Z}_7^\times$ .

Řešení

Grupa je cyklická řádu 6, takže na každý dělitel 1, 2, 3, 6 připadá jedna podgrupa: $\{1\}$ , $\{1, 6\}$ , $\{1, 2, 4\}$ a celá grupa.

1.9 Tahák

Tahák

Grupoid → asociativita → neutrál → inverze → komutativita.
Lagrange: řád podgrupy dělí řád grupy.
$\operatorname{ord} a \mid |G|$ , a tedy $a^m = a^{m \bmod \operatorname{ord} a}$ .
$\mathbb{Z}_n^+$ : $\operatorname{ord} a = n / \gcd(a, n)$ .
Generátorů je $\varphi(n)$ , $g^k$ je generátor, když $\gcd(k, n) = 1$ .
Test: $g^{n/q} \ne e$ pro prvočísla $q \mid n$ .
$\mathbb{Z}_p^\times$ cyklická, $\mathbb{Z}_8^\times$ ne.

Kapitolu mám prostudovanou