Ťahák ;D

Predpokladajme, že \( e_1 \) a \( e_2 \) sú neutrálne prvky.

Keďže \( e_2 \) je neutrálny prvok, pri operácii nič nemení. Preto

Zároveň, keďže \( e_1 \) je tiež neutrálny prvok, tak

Dostali sme teda dve rovnosti pre ten istý výraz:

a

Z toho vyplýva

Teda neutrálny prvok je jediný.

Nech \( q \in G \) a nech \( \bar{q}_1 \) a \( \bar{q}_2 \) sú dva inverzné prvky k \( q \).

To znamená, že

a zároveň

Odtiaľ dostaneme

Teraz zľava zoperujeme obidve strany prvkom \( \bar{q}_1 \). Dostaneme

Použijeme asociativitu:

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

Preto dostaneme

A keďže \( e \) je neutrálny prvok, platí

Teda inverzný prvok je jediný.

Z predpokladu

a

sa v dôkaze používa to, že \( m \) delí rozdiely

Teraz tieto dva rozdiely sčítame:

Po úprave dostaneme

Teda

Keďže \( m \) delí prvý rozdiel a tiež druhý rozdiel, delí aj ich súčet. Preto

To presne znamená

Tým je prvá časť dokázaná.

Teraz chceme ukázať, že

Začneme rozdielom oboch súčinov:

Tento rozdiel upravíme tak, aby sa v ňom objavili rozdiely \( a_1 - b_1 \) a \( a_2 - b_2 \), o ktorých vieme, že sú deliteľné číslom \( m \).

Napíšeme:

Táto úprava je dovolená, pretože sme vlastne iba pripočítali a odpočítali ten istý člen \( b_1 a_2 \).

Teraz prvé dva členy zoskupíme a posledné dva tiež:

A teraz príde hlavná myšlienka.

Z predpokladu vieme, že

Keď teda tento rozdiel vynásobíme číslom \( a_2 \), stále dostaneme číslo deliteľné \( m \). Teda

Rovnako z

dostaneme

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

Keďže tento výraz je rovný \( a_1 a_2 - b_1 b_2 \), dostaneme

A to znamená

Druhá časť vety je dokázaná.

Z predpokladu \( \gcd(a, m) = 1 \) vieme podľa Bézoutovej vety, že existujú celé čísla \( x \) a \( y \) tak, že

To je veľmi silný vzťah. Hovorí, že číslo \( 1 \) vieme vyjadriť ako lineárnu kombináciu čísel \( a \) a \( m \).

Teraz číslo \( x \) vydelíme číslom \( m \) so zvyškom. Teda napíšeme

kde \( b \) je zvyšok po delení \( x \) číslom \( m \). Preto platí

Dosadíme tento tvar za \( x \) do rovnosti \( ax + my = 1 \):

Roztvorme zátvorku:

Vyberieme \( m \) pred zátvorku z členov, ktoré ho obsahujú:

Teraz prenesme pozornosť na člen \( ab \). Rovnosť hovorí, že rozdiel \( 1 - ab \) je násobkom čísla \( m \). To znamená, že číslo \( m \) delí rozdiel \( ab - 1 \). Teda

Našli sme teda číslo \( b \), ktoré je inverzným prvkom k \( a \) modulo \( m \).

Ešte si všimnime, že \( b \) nemôže byť \( 0 \). Keby bolo \( b = 0 \), dostali by sme

čo nemôže byť rovné \( 1 \) modulo \( m \). Preto naozaj platí

Tým je veta dokázaná.

Treba overiť vlastnosti grupy jednu po druhej.

Asociativita

Asociativita násobenia modulo \( m \) vyplýva z asociativity obyčajného násobenia celých čísel. Keď násobíme tri prvky a potom berieme zvyšok modulo \( m \), nezáleží na tom, ako zátvorky rozložíme.

Teda pre všetky \( a, b, c \) platí

Komutatívnosť

Násobenie celých čísel je komutatívne, teda

Po prechode na zvyšky modulo \( m \) zostáva táto vlastnosť zachovaná:

Neutrálny prvok

Neutrálnym prvkom je číslo \( 1 \), pretože pre každý prvok \( a \) z množiny \( \mathbb{Z}_m^{*} \) platí

Zároveň číslo \( 1 \) patrí do \( \mathbb{Z}_m^{*} \), lebo \( \gcd(1, m) = 1 \).

Inverzný prvok

Nech \( a \in \mathbb{Z}_m^{*} \). To znamená, že \( \gcd(a, m) = 1 \).

Podľa predchádzajúcej vety potom existuje \( b \) také, že

Teda \( b \) je inverzný prvok k \( a \) modulo \( m \).

Navyše z rovnosti

pre nejaké celé číslo \( t \) vidíme, že každý spoločný deliteľ čísel \( b \) a \( m \) by musel deliť aj pravú stranu, teda číslo \( 1 \). Preto

čiže aj \( b \) patrí do \( \mathbb{Z}_m^{*} \).

Tým je ukázané, že každý prvok má inverzný prvok v tej istej množine.

Všetky podmienky grupy sú splnené, a preto \( (\mathbb{Z}_m^{*}, \cdot) \) tvorí komutatívnu grupu.

Nech

To znamená, že \( a_1, a_2, \dots, a_{\varphi(m)} \) sú všetky zvyšky modulo \( m \), ktoré sú s \( m \) nesúdeliteľné.

Teraz vezmime pevné číslo \( a \) také, že

Pozrime sa na prvky

pričom všetko chápeme modulo \( m \).

Najprv ukážeme, že tieto nové prvky sú navzájom rôzne. Predpokladajme, že pre nejaké indexy \( i \) a \( j \) platí

Keďže \( \gcd(a, m) = 1 \), číslo \( a \) má modulo \( m \) inverzný prvok. Označme ho \( a^{-1} \).

Vynásobme obe strany kongruencie zľava týmto inverzným prvkom:

Použijeme asociativitu:

Keďže \( a^{-1}a \equiv 1 \pmod{m} \), dostaneme

teda

Ale prvky \( a_1, a_2, \dots, a_{\varphi(m)} \) boli všetky rôzne. Preto z toho vyplýva, že aj prvky

sú všetky navzájom rôzne modulo \( m \).

Ďalej si všimnime, že každý prvok \( aa_i \) je opäť nesúdeliteľný s \( m \), lebo súčin dvoch čísel nesúdeliteľných s \( m \) je opäť nesúdeliteľný s \( m \).

Máme teda \( \varphi(m) \) rôznych prvkov, ktoré všetky patria do \( \mathbb{Z}_m^{*} \).

Ale \( \mathbb{Z}_m^{*} \) má práve \( \varphi(m) \) prvkov. Preto množina

musí byť tá istá množina ako

len v inom poradí.

Keďže ide o tie isté prvky v inom poradí, ich súčin je modulo \( m \) rovnaký. Teda

Na ľavej strane sa číslo \( a \) vyskytuje \( \varphi(m) \)-krát, takže môžeme napísať

Označme si

Potom dostaneme

Teraz ukážeme, prečo môžeme faktor \( A \) skrátiť. Každý prvok \( a_i \) je nesúdeliteľný s \( m \). Preto aj ich súčin \( A \) je nesúdeliteľný s \( m \). To znamená, že \( A \) má modulo \( m \) inverzný prvok.

Môžeme teda obe strany kongruencie vynásobiť inverzným prvkom k \( A \) a dostaneme

Tým je Eulerova veta dokázaná.

Počet čísel z \( \{0, 1, \dots, m - 1\} \), ktoré sú deliteľné \( p_1 \), je

Počet čísel deliteľných \( p_2 \) je

Čísla deliteľné oboma prvočíslami sú deliteľné súčinom \( p_1p_2 \), a tých je

Preto počet čísel, ktoré nie sú nesúdeliteľné s \( m \), je

Počet čísel nesúdeliteľných s \( m \) teda dostaneme odčítaním od celkového počtu \( m \):

Vytkneme \( m \):

Tento výraz sa rozkladá na

Tým je dôkaz hotový.

Chceme ukázať, že obe strany robia s každým prvkom to isté.

Vezmime ľubovoľný prvok \( a \).

Pozrime sa na ľavú stranu:

Podľa definície skladania to znamená, že najprv pôsobí \( \pi_1 \circ \pi_2 \) a potom \( \pi_3 \). Teda

Teraz ešte rozbalíme výraz \( (\pi_1 \circ \pi_2)(a) \). Opäť podľa definície skladania platí

Preto

Teraz pravá strana:

Podľa definície skladania to znamená: najprv pôsobí \( \pi_1 \), potom \( \pi_2 \circ \pi_3 \). Teda

Teraz rozbalíme výraz \( (\pi_2 \circ \pi_3)(\pi_1(a)) \). To znamená: najprv \( \pi_2 \), potom \( \pi_3 \), aplikované na \( \pi_1(a) \). Dostaneme

Teda aj pravá strana je

Obe strany teda dávajú na ľubovoľnom prvku \( a \) rovnaký výsledok.

Preto

Dôkaz je hotový.

Smer 1

Ak \( H \) je podgrupa, tak platia podmienky 1, 2, 3.

Tento smer je jednoduchý.

Ak \( H \) je podgrupa, tak \( (H, \circ) \) je grupa.

Každá grupa:

• je neprázdna,
• je uzavretá na operáciu,
• obsahuje ku každému prvku jeho inverz.

Teda podmienky 1, 2, 3 platia automaticky.

Smer 2

Teraz predpokladajme, že platia podmienky:

• \( H \neq \varnothing \),
• ak \( h_1, h_2 \) patria do \( H \), tak \( h_1 \circ h_2 \) patrí do \( H \),
• ak \( h \) patrí do \( H \), tak \( h^{-1} \) patrí do \( H \).

Chceme ukázať, že \( H \) je podgrupa.

Teda chceme ukázať, že \( (H, \circ) \) je grupa.

Krok 1: asociativita

Tá platí automaticky, lebo operácia je tá istá ako v \( G \) a v \( G \) je asociatívna.

Krok 2: existencia neutrálneho prvku v \( H \)

Keďže \( H \neq \varnothing \), existuje aspoň jeden prvok \( h \) v \( H \).

Podľa tretej podmienky patrí do \( H \) aj \( h^{-1} \).

Podľa druhej podmienky potom patrí do \( H \) aj ich súčin

Ale v každej grupe platí

Teda \( e \) patrí do \( H \).

To je kľúčový krok. Takto sme ukázali, že neutrálna identita grupy \( G \) leží aj v \( H \).

Krok 3: existencia inverzov

To máme priamo z tretej podmienky.

Ak \( h \) patrí do \( H \), tak \( h^{-1} \) patrí do \( H \).

Krok 4: uzavretosť

To máme z druhej podmienky.

Ak \( h_1, h_2 \) patria do \( H \), tak \( h_1 \circ h_2 \) patrí do \( H \).

Teda všetky grupové vlastnosti sú splnené a \( H \) je podgrupa.

Dôkaz je hotový.

Predpokladajme, že \( G \) je konečná grupa a \( a \in G \).

Uvažujme prvky

Keďže \( G \) má len konečne veľa prvkov, v tejto nekonečnej postupnosti sa musia niektoré dva prvky zhodovať.

Teda existujú čísla \( n \) a \( k \), kde \( k > 0 \), také, že

Teraz chceme odstrániť \( a^n \) z oboch strán.

Keďže sme v grupe, prvok \( a^n \) má inverzný prvok. Označme ho \( (a^n)^{-1} \).

Vynásobíme zľava obidve strany týmto inverzným prvkom:

Pravá strana je \( e \).

Ľavá strana sa zjednoduší na

Dostávame teda

A to znamená, že existuje kladné číslo \( k \), pre ktoré \( a^k = e \).

Teda \( a \) má konečný rád.

Dôkaz je hotový.

Predpokladajme, že \( r \mid m \).

To znamená, že existuje celé číslo \( q \) také, že

Potom

Ale \( a^r = e \), lebo \( r \) je rád prvku \( a \).

Preto

Tento smer je hotový.

Teraz predpokladajme, že

Chceme dokázať, že \( r \mid m \).

Použijeme delenie so zvyškom. To znamená, že číslo \( m \) vieme zapísať v tvare

kde

Teraz počítame:

Ale predpokladáme, že \( a^m = e \), teda dostávame

Lenže \( r \) je najmenšie kladné číslo, pre ktoré \( a^r = e \).

Ak by bolo \( r_1 > 0 \), dostali by sme menšie kladné číslo než \( r \), pre ktoré tiež vyjde neutrálny prvok. To by odporovalo minimalite \( r \).

Preto musí byť

A keďže zvyšok pri delení je \( 0 \), znamená to, že \( r \) delí \( m \).

Dôkaz je hotový.

Predpokladajme, že pre všetky \( m \) platí

Potom to musí platiť aj pre \( m = 2 \).

Dostávame

To znamená

Teraz chceme z toho dostať, že \( ab = ba \).

Vynásobme zľava prvkom \( a^{-1} \). Dostaneme

Teraz vynásobme sprava prvkom \( b^{-1} \). Dostaneme

Teda \( a \) a \( b \) komutujú.

Nech \( r = \operatorname{rad} a \).

Keďže

rád prvku \( r \) delí \( p \).

Ale \( p \) je prvočíslo, takže jeho jediné kladné delitele sú \( 1 \) a \( p \).

Preto:

• ak \( r = 1 \), potom \( a = e \),
• ak \( r \neq 1 \), musí byť \( r = p \).

Teda naozaj platí, že buď \( a = e \), alebo \( \operatorname{rad} a = p \).

Krok 1: \( H \) nie je prázdna

Stačí ukázať, že \( e \in H \).

Máme

Teda

Preto \( e \in H \).

Krok 2: uzavretosť na súčin

Nech \( h_1, h_2 \in H \).

To znamená, že

Chceme ukázať, že aj \( h_1 h_2 \in H \), teda že

Začnime z jednej strany:

Keďže \( h_2 \in H \), môžeme zameniť \( h_2 a \) za \( a h_2 \):

Teraz použijeme asociativitu:

A keďže \( h_1 \in H \), máme \( h_1 a = a h_1 \), teda

Dostali sme

Preto \( h_1 h_2 \in H \).

Krok 3: uzavretosť na inverz

Nech \( h \in H \). Potom

Chceme dokázať, že aj \( h^{-1} \in H \), teda že

Začneme rovnosťou

Vynásobme ju zľava prvkom \( h^{-1} \):

Na pravej strane je \( h^{-1}h = e \), takže dostaneme

Teraz vynásobme túto rovnosť sprava prvkom \( h^{-1} \):

Teda naozaj \( h^{-1} \in H \).

Keďže sú splnené všetky tri podmienky, \( H \) je podgrupa grupy \( G \).

Nech

Potom

Treba ukázať, že tieto prvky sú všetky navzájom rôzne.

Predpokladajme, že

Keďže sme v grupe, prvok \( a \) má inverz \( a^{-1} \). Vynásobme rovnosť zľava prvkom \( a^{-1} \):

Podľa asociativity dostaneme

Keďže \( a^{-1}a = e \), platí

teda

To znamená, že ak sa dva prvky v \( aH \) rovnajú, museli už byť rovnaké aj pôvodné prvky v \( H \).

Preto sa pri prechode z \( H \) na \( aH \) nič „nezlepí“. Počet prvkov sa nezmení.

Teda

Predpokladajme, že prienik \( a_1H \cap a_2H \) nie je prázdny.

Potom existuje prvok \( c \) taký, že

Z definície triedy rozkladu to znamená, že existujú prvky \( h_1, h_2 \in H \) tak, že

Z tejto rovnosti chceme vyjadriť \( a_1 \) pomocou \( a_2 \).

Máme

Vynásobme sprava prvkom \( h_1^{-1} \):

Označme si

Keďže \( H \) je podgrupa, patrí do nej aj súčin \( h_2h_1^{-1} \). Teda \( h_3 \in H \).

Dostali sme

Teraz vezmime ľubovoľný prvok \( v \in a_1H \). Potom existuje \( h \in H \) tak, že

Dosadíme za \( a_1 \) výraz \( a_2h_3 \):

Keďže \( h_3 \) aj \( h \) patria do \( H \) a \( H \) je uzavretá na súčin, prvok \( h_3h \in H \).

Teda \( v \in a_2H \).

Ukázali sme, že

Úplne rovnakým postupom sa ukáže aj opačné zahrnutie:

Preto

Nech všetky rôzne triedy rozkladu sú:

Keďže ich zjednotenie je \( G \) a sú navzájom disjunktné, dostávame

Preto počet prvkov celej grupy je súčet počtov prvkov týchto tried:

Každá z týchto tried má podľa prvej lemy práve \( |H| \) prvkov, teda

Takže

čiže

To znamená, že

Tým je Lagrangeova veta dokázaná.