Grupy a kongruencie modulo \( m \)

1. Pojem grupy

Jedným zo základných pojmov algebry je grupa. Ide o matematickú štruktúru, v ktorej vieme medzi prvkami vykonávať určitú operáciu a táto operácia sa správa usporiadane.

Definícia

Grupa sa zapisuje ako usporiadaná dvojica \( (G, \circ) \).

• \( G \) je množina prvkov.
• \( \circ \) je binárna operácia na množine \( G \).

Najprv treba rozumieť tomu, čo znamená binárna operácia. Je to pravidlo, ktoré vezme dva prvky z množiny \( G \) a priradí im jeden výsledok. Zápis

\[ a \circ b \]

znamená, že na prvky \( a \) a \( b \) bola použitá daná operácia.

Aby mala dvojica \( (G, \circ) \) zmysel ako grupa, musia byť splnené tieto podmienky.

Uzavretosť operácie

Definícia

Pre každé dva prvky \( a, b \) z množiny \( G \) musí byť aj výsledok \( a \circ b \) opäť prvkom množiny \( G \).

Inými slovami: keď vezmeme dva prvky z množiny a vykonáme medzi nimi danú operáciu, nesmieme „vypadnúť“ mimo množiny.

Táto vlastnosť sa často zapisuje aj takto:

\[ G \times G \to G \]

Tento zápis znamená, že operácia berie dvojicu prvkov z \( G \) a vracia opäť prvok z \( G \).

Asociativita

Definícia

Pre všetky prvky \( q_1, q_2, q_3 \) z \( G \) musí platiť

\[ q_1 \circ (q_2 \circ q_3) = (q_1 \circ q_2) \circ q_3. \]

Táto vlastnosť hovorí, že pri zreťazení troch prvkov nezáleží na tom, ako ich uzátvorkujeme, pokiaľ nemeníme ich poradie.

Poznámka

Je dôležité všimnúť si, že asociativita neznamená, že môžeme meniť poradie prvkov. Hovorí iba o tom, že môžeme meniť umiestnenie zátvoriek.

Neutrálny prvok

Definícia

Musí existovať prvok \( e \) z \( G \) taký, že pre každý prvok \( q \) z \( G \) platí

\[ q \circ e = e \circ q = q. \]

Prvok \( e \) sa nazýva neutrálny prvok. Je to taký prvok, ktorý po použití operácie nič nemení.

• Pri sčítaní je neutrálnym prvkom \( 0 \).
• Pri násobení je neutrálnym prvkom \( 1 \).

Inverzný prvok

Definícia

Ku každému prvku \( q \) z \( G \) musí existovať prvok \( q^{-1} \) z \( G \) taký, že

\[ q \circ q^{-1} = q^{-1} \circ q = e. \]

Prvok \( q^{-1} \) sa nazýva inverzný prvok k prvku \( q \).

Jeho význam je takýto: keď prvok spojíme s jeho inverzným prvkom, dostaneme neutrálny prvok.

• Pri sčítaní je inverzným prvkom k číslu \( a \) číslo \( -a \).
• Pri násobení je inverzným prvkom k číslu \( q \) číslo \( \frac{1}{q} \), ak je definované a patrí do danej množiny.

Ak sú splnené všetky uvedené podmienky, dvojica \( (G, \circ) \) je grupa.

2. Základné príklady grúp

Samotná definícia grupy je abstraktná. Preto je dôležité vidieť konkrétne situácie, v ktorých sa s grupami stretávame.

Kladné racionálne čísla pri násobení

Príklad

Uvažujme množinu kladných racionálnych čísel \( \mathbb{Q}^{+} \) a operáciu násobenia.

Dostávame dvojicu

\[ (\mathbb{Q}^{+}, \cdot). \]

Treba overiť štyri podmienky grupy.

1. Uzavretosť

Súčin dvoch kladných racionálnych čísel je opäť kladné racionálne číslo.

1. Asociativita

Násobenie racionálnych čísel je asociatívne.

1. Neutrálny prvok

Neutrálnym prvkom je číslo \( 1 \), pretože pre každé \( q \) z \( \mathbb{Q}^{+} \) platí

$$ q \cdot 1 = 1 \cdot q = q. $$

1. Inverzný prvok

Ku každému \( q \) z \( \mathbb{Q}^{+} \) existuje inverzný prvok \( \frac{1}{q} \), pričom aj číslo \( \frac{1}{q} \) je opäť kladné racionálne číslo. Platí

$$ q \cdot \frac{1}{q} = \frac{1}{q} \cdot q = 1. $$

Preto kladné racionálne čísla s násobením tvoria grupu.

Celé čísla pri sčítaní

Príklad

Teraz uvažujme množinu celých čísel \( \mathbb{Z} \) a operáciu sčítania.

Dostávame dvojicu

\[ (\mathbb{Z}, +). \]

1. Uzavretosť

Súčet dvoch celých čísel je opäť celé číslo.

1. Asociativita

Sčítanie celých čísel je asociatívne.

1. Neutrálny prvok

Neutrálnym prvkom je \( 0 \), lebo pre každé \( q \) z \( \mathbb{Z} \) platí

$$ q + 0 = 0 + q = q. $$

1. Inverzný prvok

Ku každému \( q \) z \( \mathbb{Z} \) existuje inverzný prvok \( -q \), pretože

$$ q + (-q) = (-q) + q = 0. $$

Preto celé čísla so sčítaním tvoria grupu.

3. Zvyškové triedy a sčítanie modulo \( m \)

Pri práci s deliteľnosťou a kongruenciami sa často nepozeráme na celé číslo ako celok, ale iba na jeho zvyšok po delení číslom \( m \).

Pre pevne zvolené prirodzené číslo \( m \) uvažujeme množinu

\[ Z_m = \{0, 1, 2, \ldots, m - 1\}. \]

Táto množina obsahuje všetky možné zvyšky po delení číslom \( m \).

Sčítanie modulo \( m \)

Na množine \( Z_m \) zavedieme operáciu sčítania modulo \( m \). Zmysel tejto operácie je jednoduchý:

• najprv čísla sčítame bežným spôsobom,
• potom výsledok nahradíme jeho zvyškom po delení \( m \).

Túto operáciu môžeme označiť ako \( +_m \).

Ak teda \( a, b \) patria do \( Z_m \), potom

\[ a +_m b \]

je zvyšok čísla \( a + b \) po delení číslom \( m \).

Príklad

Pri modulo \( 5 \) platí

\[ 2 +_5 3 = 0, \]

pretože \( 2 + 3 = 5 \) a zvyšok po delení \( 5 \) je \( 0 \).

Rovnako

\[ 3 +_5 3 = 1, \]

pretože \( 3 + 3 = 6 \) a zvyšok po delení \( 5 \) je \( 1 \).

Prečo ide o grupu

Dvojica

\[ (Z_m, +_m) \]

je grupa.

• Uzavretosť: súčet dvoch zvyškov, po opätovnom znížení modulo \( m \), dá opäť prvok z množiny \( Z_m \).
• Asociativita: sčítanie modulo \( m \) dedí asociativitu od obyčajného sčítania celých čísel.
• Neutrálny prvok: neutrálnym prvkom je \( 0 \), lebo pripočítanie \( 0 \) nemení zvyšok.
• Inverzný prvok: ku každému zvyšku existuje opačný zvyšok, ktorý dá po sčítaní výsledok \( 0 \) modulo \( m \).

Príklad

Napríklad v \( Z_6 \):

• inverzný prvok k \( 1 \) je \( 5 \), lebo \( 1 + 5 = 6 \equiv 0 \pmod{6} \),
• inverzný prvok k \( 2 \) je \( 4 \), lebo \( 2 + 4 = 6 \equiv 0 \pmod{6} \),
• inverzný prvok k \( 3 \) je \( 3 \), lebo \( 3 + 3 = 6 \equiv 0 \pmod{6} \).

Poznámka

Cayleyho tabuľka

Operáciu v konečnej grupe možno prehľadne zapísať do Cayleyho tabuľky. Do riadkov a stĺpcov sa zapíšu prvky množiny a do políčok výsledky operácie.

Takáto tabuľka pomáha vidieť:

• že operácia je uzavretá,
• kde sa nachádza neutrálny prvok,
• ktoré prvky sú navzájom inverzné.

Pri sčítaní modulo \( 6 \) alebo modulo \( 9 \) sa v tabuľke ukazuje pravidelný cyklický posun výsledkov.

4. Násobenie v zvyškových triedach

Okrem sčítania možno na zvyškových triedach uvažovať aj násobenie modulo \( m \).

Príklad

Pri modulo \( 5 \) môžeme skúmať množinu

\[ Z_5^{*} = \{1, 2, 3, 4\}. \]

Na nej uvažujeme násobenie modulo \( 5 \). Výsledky možno opäť zapísať do Cayleyho tabuľky. V tejto situácii:

• neutrálnym prvkom je \( 1 \),
• každý prvok má inverzný prvok,
• preto táto množina s násobením modulo \( 5 \) tvorí grupu.

Príklad

Podobne pri modulo \( 7 \) dostaneme množinu

\[ Z_7^{*} = \{1, 2, 3, 4, 5, 6\}, \]

ktorá pri násobení modulo \( 7 \) tiež tvorí grupu.

Poznámka

Tu je dôležitá najmä myšlienka: pri násobení modulo nie každá zvyšková trieda musí mať inverzný prvok, ale v uvedených príkladoch sa pracuje práve s takými prvkami, ktoré inverzné prvky majú.

5. Jednoznačnosť neutrálneho prvku

Veta

V každej grupe existuje práve jeden neutrálny prvok.

Význam tvrdenia

Definícia grupy hovorí, že neutrálny prvok existuje. Táto veta ide o krok ďalej: hovorí, že nemôžu existovať dva rôzne neutrálne prvky.

To je dôležité, pretože potom o neutrálnom prvku môžeme hovoriť jednoznačne ako o „tom“ neutrálnom prvku grupy.

Dôkaz

Predpokladajme, že v grupe existujú dva neutrálne prvky, označme ich \( e_1 \) a \( e_2 \).

Keďže \( e_1 \) je neutrálny prvok, musí platiť

\[ e_1 \circ e_2 = e_2. \]

Dôvod je ten, že neutrálny prvok nemení prvok, s ktorým sa skladá.

Zároveň, keďže \( e_2 \) je tiež neutrálny prvok, musí platiť

\[ e_1 \circ e_2 = e_1. \]

Máme teda dve rovnosti pre ten istý výraz \( e_1 \circ e_2 \):

\[ e_1 \circ e_2 = e_1 \]

a zároveň

\[ e_1 \circ e_2 = e_2. \]

Z toho vyplýva

\[ e_1 = e_2. \]

Tým je dokázané, že neutrálny prvok je jediný.

6. Jednoznačnosť inverzného prvku

Veta

Ku každému prvku grupy existuje práve jeden inverzný prvok.

Význam tvrdenia

Definícia grupy zaručuje, že ku každému prvku nejaký inverzný prvok existuje. Táto veta hovorí, že takýto prvok nemôže byť viac než jeden.

Vďaka tomu môžeme inverzný prvok označovať jednoznačne symbolom

\[ a^{-1}. \]

Pri sčítacích grupách sa často namiesto toho používa zápis \( -a \).

Dôkaz

Nech \( q \) patrí do grupy \( G \). Predpokladajme, že \( q \) má dva inverzné prvky, označme ich \( \bar q_1 \) a \( \bar q_2 \).

To znamená, že platí

\[ q \circ \bar q_1 = e \]

a

\[ q \circ \bar q_2 = e. \]

Chceme ukázať, že \( \bar q_1 = \bar q_2 \).

Začneme prvkom \( \bar q_1 \). Keďže \( e \) je neutrálny prvok, platí

\[ \bar q_1 = \bar q_1 \circ e. \]

Keďže \( q \circ \bar q_2 = e \), môžeme namiesto \( e \) napísať \( q \circ \bar q_2 \):

\[ \bar q_1 = \bar q_1 \circ (q \circ \bar q_2). \]

Teraz použijeme asociativitu:

\[ \bar q_1 \circ (q \circ \bar q_2) = (\bar q_1 \circ q) \circ \bar q_2. \]

Keďže \( \bar q_1 \) je inverzný prvok k \( q \), platí

\[ \bar q_1 \circ q = e. \]

Dostávame teda

\[ (\bar q_1 \circ q) \circ \bar q_2 = e \circ \bar q_2 = \bar q_2. \]

Spojením krokov dostaneme

\[ \bar q_1 = \bar q_2. \]

Tým je dokázané, že inverzný prvok je jediný.

7. Inverz súčinu prvkov

Pri práci v grupe je veľmi dôležité vedieť určiť inverzný prvok zloženejšieho výrazu.

Inverz súčinu dvoch prvkov

Veta

Pre prvky \( g_1, g_2 \) z \( G \) platí

\[ (g_1 \circ g_2)^{-1} = g_2^{-1} \circ g_1^{-1}. \]

Čo táto veta hovorí

Inverz súčinu nedostaneme tak, že len zoberieme inverzy jednotlivých prvkov. Musíme pritom obrátiť poradie.

To je veľmi dôležité. Poradie sa mení preto, že pri skladaní musíme prvky „odstraňovať“ v opačnom poradí, než boli vytvorené.

Dôkaz

Aby sme ukázali, že \( g_2^{-1} \circ g_1^{-1} \) je inverzný prvok k \( g_1 \circ g_2 \), musíme overiť dve rovnosti:

\[ (g_1 \circ g_2) \circ (g_2^{-1} \circ g_1^{-1}) = e \]

a

\[ (g_2^{-1} \circ g_1^{-1}) \circ (g_1 \circ g_2) = e. \]

Najprv prvá rovnosť. Pomocou asociativity môžeme zátvorky preskupovať:

\[ \begin{aligned} (g_1 \circ g_2) \circ (g_2^{-1} \circ g_1^{-1}) &= g_1 \circ (g_2 \circ g_2^{-1}) \circ g_1^{-1} \\ &= g_1 \circ e \circ g_1^{-1} \\ &= g_1 \circ g_1^{-1} \\ &= e. \end{aligned} \]

Teraz druhá rovnosť:

\[ \begin{aligned} (g_2^{-1} \circ g_1^{-1}) \circ (g_1 \circ g_2) &= g_2^{-1} \circ (g_1^{-1} \circ g_1) \circ g_2 \\ &= g_2^{-1} \circ e \circ g_2 \\ &= g_2^{-1} \circ g_2 \\ &= e. \end{aligned} \]

Keďže obidve zloženia dávajú neutrálny prvok, prvok \( g_2^{-1} \circ g_1^{-1} \) je skutočne inverzný k prvku \( g_1 \circ g_2 \).

Inverz súčinu troch prvkov

Podobne platí

\[ (g_1 \circ g_2 \circ g_3)^{-1} = g_3^{-1} \circ g_2^{-1} \circ g_1^{-1}. \]

Aj tu sa zachováva rovnaké pravidlo: inverzy sa píšu v opačnom poradí.

Inverz súčinu štyroch a viacerých prvkov

Rovnako dostávame

\[ (g_1 \circ g_2 \circ g_3 \circ g_4)^{-1} = g_4^{-1} \circ g_3^{-1} \circ g_2^{-1} \circ g_1^{-1}. \]

Z predchádzajúcich prípadov je vidieť všeobecný vzor:

• pri inverzii súčinu sa poradie prvkov obráti,
• každý prvok sa nahradí svojím inverzným prvkom.

8. Kongruencia modulo \( m \)

Ďalšou dôležitou témou je pojem kongruencie.

Definícia

Nech \( m \) je prirodzené číslo a nech \( a, b \) sú celé čísla. Píšeme

\[ a \equiv b \pmod{m}, \]

ak majú čísla \( a \) a \( b \) rovnaký zvyšok po delení číslom \( m \).

Tento zápis sa číta:

„\( a \) je kongruentné s \( b \) modulo \( m \)“.

Význam definície

Kongruencia hovorí, že z pohľadu delenia číslom \( m \) sa čísla \( a \) a \( b \) správajú rovnako, pretože po delení dávajú ten istý zvyšok.

Príklad

• \( 7 \equiv 2 \pmod{5} \), lebo \( 7 \) aj \( 2 \) dávajú po delení \( 5 \) zvyšok \( 2 \),
• \( 6 \equiv 1 \pmod{5} \), lebo \( 6 \) aj \( 1 \) dávajú po delení \( 5 \) zvyšok \( 1 \),
• \( 29 \equiv 12 \pmod{17} \), lebo \( 29 - 12 = 17 \), teda rozdiel je deliteľný \( 17 \).

Práve posledný príklad naznačuje veľmi dôležitú myšlienku: kongruenciu možno chápať aj cez deliteľnosť rozdielu.

Ak je

\[ a \equiv b \pmod{m}, \]

tak rozdiel \( a - b \) je deliteľný číslom \( m \).

9. Sčítanie a násobenie kongruencií

Veta

Nech \( m \) je prirodzené číslo a nech

\[ a_1 \equiv b_1 \pmod{m}, \]

\[ a_2 \equiv b_2 \pmod{m}. \]

Potom platí:

\[ a_1 + a_2 \equiv b_1 + b_2 \pmod{m}, \]

\[ a_1 a_2 \equiv b_1 b_2 \pmod{m}. \]

Čo veta znamená

Táto veta hovorí, že pri kongruenciách môžeme korektne sčítať aj násobiť.

To je veľmi dôležité, pretože v modulo počítaní vieme zložité výrazy nahrádzať jednoduchšími zvyškami a pritom nestratiť správnosť výsledku.

Dôkaz

Dôkaz pre sčítanie

Z predpokladu

\[ a_1 \equiv b_1 \pmod{m} \]

vyplýva, že \( m \) delí rozdiel \( a_1 - b_1 \).

Rovnako z predpokladu

\[ a_2 \equiv b_2 \pmod{m} \]

vyplýva, že \( m \) delí rozdiel \( a_2 - b_2 \).

Keďže \( m \) delí oba tieto rozdiely, delí aj ich súčet:

\[ (a_1 - b_1) + (a_2 - b_2). \]

Teraz tento súčet upravíme:

\[ \begin{aligned} (a_1 - b_1) + (a_2 - b_2) &= a_1 + a_2 - b_1 - b_2 \\ &= (a_1 + a_2) - (b_1 + b_2). \end{aligned} \]

Teda \( m \) delí rozdiel

\[ (a_1 + a_2) - (b_1 + b_2). \]

To podľa definície kongruencie znamená

\[ a_1 + a_2 \equiv b_1 + b_2 \pmod{m}. \]

Dôkaz

Dôkaz pre násobenie

Opäť predpokladáme

\[ a_1 \equiv b_1 \pmod{m}, \]

\[ a_2 \equiv b_2 \pmod{m}. \]

To znamená, že \( m \) delí rozdiely \( a_1 - b_1 \) a \( a_2 - b_2 \).

Chceme ukázať, že \( m \) delí aj rozdiel

\[ a_1 a_2 - b_1 b_2. \]

Tento rozdiel upravíme šikovným pridaním a odčítaním člena \( b_1 a_2 \):

\[ \begin{aligned} a_1 a_2 - b_1 b_2 &= a_1 a_2 - b_1 a_2 + b_1 a_2 - b_1 b_2. \end{aligned} \]

Teraz vyberieme spoločné činitele:

\[ a_2(a_1 - b_1) + b_1(a_2 - b_2). \]

Vieme, že \( m \) delí \( a_1 - b_1 \). Preto \( m \) delí aj súčin \( a_2(a_1 - b_1) \).

Rovnako \( m \) delí \( a_2 - b_2 \). Preto \( m \) delí aj súčin \( b_1(a_2 - b_2) \).

Ak \( m \) delí oba sčítance, delí aj ich súčet. Teda \( m \) delí

\[ a_2(a_1 - b_1) + b_1(a_2 - b_2), \]

čiže delí

\[ a_1 a_2 - b_1 b_2. \]

To znamená

\[ a_1 a_2 \equiv b_1 b_2 \pmod{m}. \]

10. Ciferný súčet a zvyšok po delení \( 9 \)

Jedným z pekných použití kongruencií je pravidlo o cifernom súčte pri delení deviatimi.

Základná myšlienka

Pri modulo \( 9 \) platí

\[ 10 \equiv 1 \pmod{9}. \]

Odtiaľ okamžite dostávame aj

\[ 10^2 \equiv 1 \pmod{9}, \]

\[ 10^3 \equiv 1 \pmod{9}, \]

\[ \ldots \]

\[ 10^n \equiv 1 \pmod{9}. \]

To znamená, že každá mocnina desiatky sa pri počítaní modulo \( 9 \) správa rovnako ako číslo \( 1 \).

Rozklad čísla na cifry

Nech číslo \( a \) má desiatkový zápis

\[ a = a_0 + a_1 \cdot 10 + a_2 \cdot 10^2 + \ldots + a_n \cdot 10^n. \]

Keďže každé \( 10^k \) je kongruentné s \( 1 \) modulo \( 9 \), môžeme nahradiť všetky mocniny desiatky číslom \( 1 \). Dostávame

\[ a \equiv a_0 + a_1 + a_2 + \ldots + a_n \pmod{9}. \]

To znamená:

Dôsledok

Číslo je modulo \( 9 \) kongruentné so súčtom svojich cifier.

Preto pri delení deviatimi stačí sčítať cifry.

Príklad

Uvažujme číslo

\[ 87349536423. \]

Súčet jeho cifier je

\[ 8 + 7 + 3 + 4 + 9 + 5 + 3 + 6 + 4 + 2 + 3 = 58 \]

Potom môžeme ešte raz sčítať cifry čísla \( 58 \):

\[ 5 + 8 = 13, \]

a potom cifry čísla \( 13 \):

\[ 1 + 3 = 4. \]

Teda dané číslo je kongruentné s \( 4 \) modulo \( 9 \), čiže pri delení \( 9 \) dáva zvyšok \( 4 \).

Zápisom:

\[ 87349536423 \equiv 4 \pmod{9}. \]

Zmysel tohto postupu je praktický: veľké číslo vieme pri delení \( 9 \) nahradiť oveľa menším číslom bez toho, aby sa zmenil zvyšok.

Zhrnutie

Táto kapitola ukazuje dve základné línie algebry:

• na jednej strane prácu s operáciami na množinách, ktorá vedie k pojmu grupy,
• na druhej strane prácu so zvyškami po delení, ktorá vedie ku kongruenciám.

Obe témy spolu úzko súvisia, pretože aj zvyškové triedy modulo \( m \) môžu pri vhodne zvolenej operácii tvoriť grupy.