1. Algebry a podalgebry

4.10.

Buď n přirozené číslo a položme Z_{n} = {0, 1, …, n − 1}. Definujme na Z_{n} binární operace + a · předpisem a + b = (a + b)modn a a · b = (a · b)modn, kde vlevo vždy uvažujeme standardní sčítání a násobení celých čísel a modn znamená zbytek po celočíselném dělení hodnotou n.

1.1. Najděte všechny podalgebry algebry (Z_{5}, +).

Připomeňme, že podalgebrou rozumíme jakoukoli neprázdnou podmnožinu P množiny Z_{5}, která je uzavřená na všechny operace dané algebry, v daném případě tedy na jedinou operaci +. Dále připomeňme, že neprázdný průnik podalgeber je opět podalgebra, díky čemuž můžeme postupně uvažovat nejmenší podalgebry (Z_{5}, +) obsahující podmnožinu G, které budeme značit ⟨G⟩ (resp. ⟨g_{1}, …, g_{n}⟩ místo ⟨{g_{1}, …, g_{n}}⟩) a nazývat podalgebrami generovanými množinou G.

Nejprve uvážíme podalgebry generované jednoprvkovou množinou. Všimněme si, že

⟨0⟩ = {0} a ⟨1⟩ = {1, 1 + 1, 1 + 1 + 1, 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1} = Z_{5}.

Nyní stačí nahlédnout, že součtem b kopií prvku a dostaneme právě hodnotu a · b (samozřejmě s násobením modulo 5) a že umíme pro každé a ∈ {2, 3, 4} najít b, jímž je právě inverzní prvek v tělese Z_{5}, pro který a · b = 1. To znamená, že 1 ∈ ⟨2⟩, 1 ∈ ⟨3⟩ a 1 ∈ ⟨4⟩, a proto

Z_{5} = ⟨1⟩ = ⟨2⟩ = ⟨3⟩ = ⟨4⟩.

Konečně, všechny aspoň dvouprvkové množiny už zřejmě generují celé Z_{5}. Zjistili jsme, že algebra (Z_{5}, +) obsahuje právě dvě podalgebry {0} a Z_{5}. □

1.2. Najděte všechny podalgebry algebry (Z_{5}, ·).

Uvažujeme podobně jako v předchozí úloze. Nejprve vidíme, že

⟨0⟩ = {0}, ⟨1⟩ = {1}, ⟨2⟩ = {2, 4, 3, 1}, ⟨3⟩ = {3, 4, 2, 1}, ⟨4⟩ = {4, 1}.

Snadno nahlédneme, že pro podlagbery ⟨a, b⟩, kde a ≠ 0 ≠ b, buď ⟨a, b⟩ = ⟨a⟩ nebo ⟨a, b⟩ = ⟨b⟩, a ⟨a, 0⟩ = ⟨a⟩ ∪ {0}. Konečně třígenerované podalgebry žádné nové příklady zřejmě nedají, tedy

{0}, {1}, {0, 1}, {1, 4}, {0, 1, 4}, {1, 2, 3, 4}, Z_{5}

jsou právě všechny podalgebry (Z_{5}, ·). □

1.3. Najděte všechny podalgebry algebry (Z_{5}, +, ·, 0).

Tentokrát buď vezmem průnik systémů podalgeber z úloh 1.1, 1.2 a všimneme si, že obě podmnožiny obsahují 0 nebo uvážíme, že násobení i 0 dostaneme iterováním sčítání (u nuly právě pětkrát), tedy hledaný systém všech podalgeber je totožný s nalezeným systémem v úloze 1.1. □

1.4. Najděte všechny podalgebry algebry (Z_{10}, +, 0).

Postupujeme jako v 1.1. Snadno si opět uvědomíme, že ⟨0⟩ = {0}, každá podlagebra algebry (Z_{10}, +, 0) musí obsahovat 0 a dále, že

⟨1⟩ = ⟨3⟩ = ⟨7⟩ = ⟨9⟩ = Z_{10}, ⟨2⟩ = ⟨4⟩ = ⟨6⟩ = ⟨8⟩ = {0, 2, 4, 6, 8}, ⟨5⟩ = {0, 5}

Připomeňme, že pomocí Eukleidova algoritmu umíme pro každá dvě kladná celá čísla a, b najít celá čísla u a v, aby NSD(a, b) = ua+vb a odtud snadno nahlédneme, že ⟨a, b⟩ = ⟨NSD(a, b)⟩. To ovšem znamená, že {0}, {0, 5}, {0, 2, 4, 6, 8} a Z_{10} jsou právě všechny podalgebry algebry (Z_{10}, +, 0). □

11.10.

Všimněm se, že bychom úvahou z předchozí úlohy uměli dokázat, že pro každou podalgebru P algebry (Z_{n}, +) existje takové a ∈ Z_{n}, pro něž P = ⟨a⟩. Protože bude pozorování později dokázáno na přednášce, upustíme pro tento okamžik od důkazu a vezmeme ho jako fakt.

V následujícím textu budeme největšího společného dělitele čísel a_{0} a a_{1} značit NSD(a_{0}, a_{1})

1.5. Dokažte, že pro každé a ∈ Z_{n} existuje takové k, že buď k/n nebo k = 0 a ⟨a⟩ = ⟨k⟩.

Předně poznamenejme, že pro a = 0 vezmeme k = 0. Předpokládejme, že k > 0, a položme k = NSD(a, b). Protože k/a, máme a ∈ ⟨k⟩, a tedy ⟨a⟩ ⊆ ⟨k⟩, protože ⟨a⟩ je nejmenší podalgebra vzhledem k inkluzi obsahující prvek a a o podalgebře ⟨k⟩ jsme ukázali, že prvek a rovněž obsahuje. Eukleidův algoritmus nám zajišťuje existenci celých čísel u a v, pro něž k = NSD(a, n) = ua + vn, navíc můžeme vzít u kladné, proto k = (u · a)modn ∈ ⟨a⟩. Dostali jsme i druhou inkluzi ⟨k⟩ ⊆ ⟨a⟩, tudíž ⟨a⟩ = ⟨k⟩. □

1.6. Najděte všechny podalgebry algebry (Z_{15}, +, ·).

Předchozí úvahy nám říkají, že se stačí omezit na podmnožiny uzavřené na + (viz 1.3) a hledané podalgebry jsou tvaru ⟨k⟩ = kZ_{15} = {k · x| x ∈ Z_{15/k}} pro k/n nebo k = 0 (viz 1.4 a 1.5). To znamená, že

0Z_{15} = {0}, 5Z_{15} = {0, 5, 10}, 3Z_{15} = {0, 3, 6, 9, 12}, 1Z_{15} = Z_{15}

jsou právě všechny podalgebry algebry (Z_{15}, +, ·). □

1.7. Kolik existuje podalgeber algebry (Z_{1100} , +).

Uvážili jsme, že pro každý dělitel čísla 1100 existuje právě jedna podalgebra algebry (Z_{1100} , +). Protože 1100 = 2^{2} · 5^{2} · 11^{1}, máme právě 3 · 3 · 2 = 18 jeho dělitelů, tedy algebra (Z_{1100} , +) obsahuje 18 podalgeber. □

1.8. Najděte všechny podalgebry algebry (Z_{6}, 1).

Jediný požadavek, který tentokrát klademe na podalgebru, je, aby šlo o množinu obsahující prvek 1, snadno nahlédneme, že takových množin máme k dispozici právě 2^{5} = 32. □

Nechť a_{0} ≥ a_{1} jsou dvě přirozená čísla. Připomeňme Eukleidův algoritmus hledání největšího společného dělitele čísel a_{0} a a_{1}:

Známe-li a_{i−1} a a_{i} spočteme a_{i+1} = (a_{i−1})mod a_{i}. Tedy víme, že existuje takové q_{i} ∈ N že a_{i−1} = q_{i}a_{i} + a_{i+1} a a_{i+1} < a_{i}. Algoritmus skončí, když a_{n+1} = 0, potom a_{n} = NSD(a_{0}, a_{1}).

1.9. Najděte pomocí Eukleidova algoritmu největší společný dělitel čísel 72 a 93. Najděte dále taková celá čísla x a y, aby NSD(72, 93) = x.72 + y.93.

První část úkolu je snadná, sepišme si i jakým způsobem jednotlivé zbytky po celočíselném dělení získáme:

a_{0} = 93, a_{1} = 72, a_{2} = 93 − 72 = 21, a_{3} = 72 − 3.21 = 9, a_{4} = 21 − 3.9 = 3 = NSD(93, 72) a_{5} = 0. Druhou část úlohy vyřešíme rovněž pomocí Eukleidova algoritmu, stačí si uvě-

domit, že každé z čísel a_{i+1} dostaneme jako celočíselnou lineární kombinaci dvou předchozích hodnot a_{i−1} a a_{i}. Jednoduchou indukční úvahou zjistíme, že každé číslo a_{i+1} je celočíselnou lineární kombinaci hodnot a_{0} a a_{1}. Konkrétně:

a_{2} = 93 − 72 = 21, a_{3} = 9 = 72 − 3.21 = 72 − 3.(93 − 72) = 4.72 − 3.93, a_{4} = 3 = NSD(93, 72) = 21 − 2.9 = (93 − 72) − 2.(4.72 − 3.93) = 7.93 − 9.72. Zjistili jsme, že x = −9 a y = 7. □

1.10. Najděte celá čísla x a y tak, aby x.18 + y.25 = 1.

Protože NSD(18, 25) = 1, zaručuje nám Eukleidův algoritmus existenci požadovaných čísel x, y ∈ Z a tento algoritmus použijeme podobně jako v předchozí úloze i k jejich nalezení:

a_{0} = 25, a_{1} = 18, a_{2} = 7 = 25 − 18, a_{3} = 4 = 18 − 2 · 7 = 18 − 2 · (25 − 18) = 3 · 18 − 2 · 25, a_{4} = 3 = 7 − 4 = 25 − 18 − (3 · 18 − 2 · 25) = 3 · 25 − 4 · 18, a_{5} = NSD(25, 18) = 1 = 4 − 3 = 3 · 18 − 2 · 25 − (3 · 25 − 4 · 18) = 7 · 18 − 5 · 25. □

18.10.

1.11. Najděte celočíselné řešení rovnice x · 18 + y · 25 = 10.

Vynásobíme-li již vyřešenou rovnici 7 · 18 − 5 · 25 = 1 desítkou, okamžitě vidíme, že rovnici x · 18 + y · 25 = 10 řeší x = 10 · 7 = 70 a y = −5 · 10 = −50. □

Definujme nyní pro každé k ∈ Z_{217} zobrazení f_{k} : Z_{217} → Z_{217} ppředpisem f_{k}(x) = (k · x)mod217.

1.12. Rozhodněte, zda existuje x ∈ Z_{217}, aby f_{k}(x) = 11, jestliže a) k = 100, b) k = 98. Existuje-li řešení, najděte ho a rozhodněte, zda je určeno jednoznačně.

a) Hledáme x ∈ Z_{217}, pro které existuje y ∈ Z splňující podmínku 100x+217y = 11. Díky Eukleidovu algoritmu a faktu, že NSD(100, 217) = 1 dokonce víme, že lze vyřešit rovnici 100x + 217y = c opro každé c ∈ Z_{217}, tedy zobrazení f_{100} je na celou množinu Z_{217}. Protože ovšem zobrazuje konečnou množinu do sebe, musí jít i o prosté zobrazení, tedy existuje pr8v2 jedno řešení vztahu f_{100}(x) = 11. Zbývá ho najít stejnou cestou jako v předchozí úloze:

17 = 217 − 2 · 100,

15 = 100 − 5 · 17 = 100 − 5 · (217 − 2 · 100) = 11 · 100 − 5 · 217,

2 = 17 − 15 = 217 − 2 · 100 − (11 · 100 − 5 · 217) = 6 · 217 − 13 · 100,

1 = 15 − 7 · 2 = 11 · 100 − 5 · 217 − 7 · (6 · 217 − 13 · 100) = 102 · 100 − 47 · 217. Proto 11·102·100−11·47·217 = 11, tedy x = (11·102)mod217 = 37. Všimněme

si, že z druhého a třetího kroku Eukleidova algoritmu jsme přímo mohli dostat

11 = 15 − 2 · 2 = 11 · 100 − 5 · 217 − 2 · (6 · 217 − 13 · 100) = 37 · 100 − 17 · 217.

b) Tentokrát se ptáme, zda existuje x ∈ Z_{217} a y ∈ Z, pro něž 98x + 217y = 11. Protože 7 dělí 98 i 217, muselo by 7 dělit také číslo 11, což není pravda, proto takové x neexistuje. □

1.13. Rozhodněte, zda existuje a zda je určeno jednoznačně x ∈ Z_{217}, aby f_{98}(x) = 21.

Uvažujem stejně jako v předchozí úloze. Hledáme tedy x ∈ Z_{217} a y ∈ Z, pro něž 98x + 217y = 21. Protože NSD(98, 217) = 7 dělí 21 zaručuje nám Eukleidův algoritmus opět existenci řešení. Konkrétně hned v prvním kroku zjistíme, že 21 = 217 − 2 · 98, tedy x = (−2)mod217 = 215. Navíc (98 · 31)mod217 = 0, proto x = −2 + 31 = 29 také řeší f_{98}(x) = 21. □

1.14. Rozhodněte, pro která k je zobrazení f_{k} homomorfismem a) algebry (Z_{217}, +) do sebe b) algebry (Z_{217}, +, ·) do sebe, kde uvažujeme operace modulo 217.

a) Snadno nahlédneme, že pro každé a, b ∈ Z_{217}

f_{k}(a + b) = ((a + b) · k)mod217 = (a · k + b · k)mod217 = f_{k}(a) + f_{k}(b),

tedy f_{k} je homomorfismus pro všechna k ∈ Z_{217}.

b) Právě jsme ověřili, že vzhledem k první operaci je zobrazení f_{k} slučitelné pro všechna k. Dále je zjevně splněna podmínka f_{1}(a · b) = a · b = f_{1}(a) · f_{1}(b) a f_{0}(a · b) = 0 = f_{0}(a) · f_{0}(b). Konečně jakmile k = f_{k}(1 · 1) = f_{k}(1) · f_{k}(1) = k · k, tedy musí 217/k^{2} − k. Snadno ovšem nahlédneme, že to platí pouze pro k = 0 nebo k = 1. Tedy jsme zjistili, že f_{k} je homomorfismus algebry (Z_{217}, +, ·) do sebe pouze pro k ∈ {0, 1}.

□

Uvažujme v dalším množinu A = {a, b, c} s binárními operacemi ∘ a ⋆ danými tabulkami:

\begin{matrix}∘ & a & b & c \\ a & c & b & a \\ b & b & a & b \\ c & a & b & c \end{matrix}  \begin{matrix}⋆ & a & b & c \\ a & a & b & c \\ b & b & c & a \\ c & c & a & b \end{matrix}

1.15. Najděte všechny podalgebry algebry (A, ∘).

Předně si uvědomme, že celá nosná množina A je podalgebrou každé algebry (s nosnou množinou A). Dále budeme postupně probírat podalgebry podle počtu prvků.

Je-li {x} jednoprvková podalgebra A, zřejmě musí platit x ∘ x = x, protože množina {x} má být uzavřená na operaci ∘. Snadno z tabulky vyčeme, že takovou vlastnost (mluvíme o idempotenci) splňuje pouze prvek c. Tedy máme právě jednu jednoprvkovou podalgebru c algebry A(∘).

Dále uvažme, které z dvou prvkových podmnožin {a, b}, {a, c} a {b, c} jsou podalgebry. Zjevně podalgebra obsahující prvek a už musí obsahovat i prvek c = a∘a, tedy {a, b} není podalgebrou. Podobně podalgebra obsahující prvkek b musí obsahovat i prvek a = b ∘ b, tedy ani {b, c} není podalgebrou. Konečně z tabulky vidíme, že množina {a, c} = ⟨a⟩ je uzavřená na operaci ∘, tedy {a, c} je jedinou dvouprvkovou podalgebra algebry (A, ∘).

Dostáváme systém všech podalgeber: {c}, {a, c}, {a, b, c}. □

1.16. Najděte všechny podalgebry algebry (A, ∘, a), kde a označuje nulární operaci vyznačující prvek a.

V předchozí úloze jsme našli všechny podmnožiny množiny A uzavřené na operaci ∘, z nichž potřebujeme nyní vybrat podmnožiny uzavřené na nulární operaci a, tedy právě ty, které obsahují prvek a. Podalgebry algebry (A, ∘, a) jsou tedy zřejmě právě množiny {a, c}, {a, b, c}. □

1.17. Najděte všechny podalgebry algebry (A, ∘, ⋆).

Tentokrát vybíráme ze systému množin uzavřených na operaci ∘ ty, které jsou navíc uzavřené na ⋆. Protože c ⋆ c = b, zbývá nám pouze množina A. □

Další úlohy

(1) Najděte všechny podalgebry a kongruence algebry C = {a, b, c, d, e, f} s jednou binární operací danou předpisem x ⊙ y = x.

(2) Uvažujme množinu Z_{n} s unární operací ^{+} definovanou předpisem a^{+} = (a + 1)mod n. Popište všechny podalgebry a všechny kongruence na Z_{n}(^{+} ).

(3) Najděte všechna celočíselná řešení rovnice 324 · x + 88 · y = c postupně pro c = 0, 2, 88, −4, −88.

(4) Najděte všechna celočíselná řešení rovnice 15 · x − 44 · y = c postupně pro c = 1, 2, −2.

(5) Najděte (všechna) celočíselná řešení rovnice 15 · x + 18 · y + 10 · z = 1.

(6) Spočítejte v tělese Z_{83} hodnoty 15^{−1} a (3^{−1} + 6 · 53^{−1})^{−1}.

(7) Vyřešte v tělese Z_{97} rovnici 7^{−1} · x = 51^{−1}.

(8) Ověřte, že Eukleidův algoritmus pracuje správně.