6.10.
Nechť a0 > a1 jsou dvě přirozená čísla. Připomeňme Euklidův algoritmus hledání největšího společného dělitele (NSD) čísel a0 a a1: Známe-li ai a ai+1 spočteme ai+2 = (ai)mod ai+1, algoritmus skončí, pokud an+1=0, potom an = NSD(a0, a1).
První část úkolu je snadná, sepišme si i jakým způsobem jednotlivé zbytky po celočíselném dělení získáme:
Druhou část úlohy vyřešíme rovněž pomocí Euklidova algoritmu, stačí si uvědomit, že každé z čísel ai+2 dostaneme jako celočíselnou lineární kombinaci dvou předchozích hodnot ai a ai+1. Jednoduchou indukční úvahou zjistíme, že každé číslo ai+2 je celočíselnou lineární kombinaci hodnot a0 a a1. Konkrétně:
Protože NSD(18,25)=1, zaručuje nám Euklidův algoritmus existenci požadovaných celých čísel x, y. Euklidův algoritmus použijeme (podobně jako v předchozí úloze) i k jejich nalezení
V předchozím příkladě jsme našli jedno řešení, označme ho (x0,y0). Uvažujme nyní libovolné další řešení (x,y). Podobnou úvahou jako při hledání všech řešení lineárních rovnic nad tělesem dostaneme
(x-x0).18 + (y-y0).25 = 0.
Všechna racionální řešení této rovnice jsou tvaru (q.25,-q.18), kde q je racionální číslo. Protože 25 a 18 jsou nesoudělná, tvoří celočíselné dvojice řešení dané homogenní rovnice právě dvojice (c.25,-c.18) pro c celé. Tedy zjistili jsme, že platí
(x-x0) = c.25 a (y-y0) = -c.18 pro vhodné celé c,
proto {(7+c.25, -5-c.18)| c-celé} tvoří množinu všech celočíselných řešení rovnice.
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. Úvaha, kterou nalezneme všechna řešení bude zcela stejná jako v předchozím příkladě (a analogická hledání řešení nehomogenní soustavy rovnic nad tělesem). Tedy množina všech celočíselných řešení rovnice je tvaru {(70+c.25, -50-c.18)| c-celé}.
Tentokrát vidíme, že NSD(18,24)/12, můžeme tedy celou rovnici vydělit hodnotou NSD(18,24) a řešit upravenou rovnici x.3 + y.4 = 2. Snadno nahlédneme, že (2,-1) je jedním řešením rovnice, a protože jsou čísla 3 a 4 nesoudělná, je množina všech celočíselných řešení tvaru {(2+c.4, -1-c.3)| c-celé}.
Postupujeme stejně jako v předchozích úlohách, jen zohledníme, že číslo 24 máme v rovnici se záporným znaménkem. Pomocí Euklidova algoritmu zjistíme, že 3.18 - 2.24 = 6, tedy 18.(-15) + 24.10 = -30, a dále 18.4 - 24.3 = 0. Vidíme, že množina všech celočíselných řešení má tvar {(-15+c.4, 10+c.3)| c-celé}.
Všimněme si, že jsme v úlohách 1-6 odvodili obecné kritérium nalezení a popis množiny všech celočíselných řešení (diofantické) rovnice ax+by=c, kde a,b,c jsou přirozená. Tedy řešení existuje právě tehdy, když NSD(a,b)/c (najdeme ho například pomocí Euklidova algoritmu), a máme-li jedno řešení (x0,y0), pak obecné řešení je tvaru (x0+c.B, y0-c.A), kde A=a/NSD(a,b) a B=b/NSD(a,b).
Připomeňme, že prvočíslem rozumíme každé přirozené číslo p větší než 1 splňující pro všechna přirozená a, b implikaci p=a.b ==> p=a nebo p=b.
13.10.
Víme, že NSD(a0, a1)=1 a budeme indukcí podle i dokazovat NSD(ai, ai+1) = 1. Předpokládejme, že NSD(ai-1, ai) = 1 a položme c = NSD(ai, ai+1). Protože c/ai i ai+1, c dělí i ai-1 = q.ai + ai+1, tedy c/1, tudíž c=1. Konečně zřejmě an = NSD(an-1, an) = 1.
Dokážeme snadno indukcí podle n. Číslo 2 je zřejmě prvočíslo. Pokud n není prvočíslo existují přirozená čísla k, l < n tak, že n = k.l. Obě jsou samozřejmě větší než jedna a podle indukčního předpokladu máme prvočíselný rozklad čísel k = p1...pr a l = q1...qs. Tedy číslo n je součinem prvočísel p1...pr.q1...qs.
Vyslovme sporný předpoklad, že p je prvočíslo a existují přirozená a, b tak, že p/a.b a p nedělí a ani b. Protože NSD(p,a)=1 (p má pouze dělitele 1 a p), existují celá x a y tak, že 1=a.x+p.y. Proto b=a.b.x+p.b.y. Protože p dělí a.b.x i p.b.y, platí, že p/b, což je spor s naším předpokladem.
Indukční rozšíření předchozího pozorování.
Dokážeme tvrzení indukcí dle n. Je-li n prvočíslo (speciálně n = 2), je prvočíselný rozklad zřejmě určen jednoznačně. Platí-li tvrzení pro všechna k < n a n = p1...pr = q1...ps jsou dva prvočíselné rozklady. Potom podle předchozího příkladu existuje j tak, že p1 / qj. Bez újmy na obecnosti můžeme předpokládat, že j=1. Protože p1 i q1 jsou prvočísla, máme p1 = q1. Nyní stačí použít indukční předpoklad pro p2...pr (= q2...ps).
Z jednoznačnosti prvočíselného rozkladu plyne, že číslo c je součinem některých prvočísel z prvočíselného rozkladu NSD(a,b).
Postupujme obdobně jako v úloze 10, tj, indukcí podle i dokážeme, že NSD(ai, ai+1) = NSD(ai-1, ai). Položme c = NSD(ai-1, ai) a položme d = NSD(ai, ai+1). Protože d/ai i ai+1, d dělí i ai-1 = q.ai + ai+1, tedy podle úlohy 15 máme d/c. Podobně nahlédneme, že c/d, tedy c=d. Protože zřejmě an = NSD(an-1, an), dostáváme, že an = NSD(a0, a1).
Buď p a q dva reálné polynomy. Definujme NSD(p,q) jako normovaný společný dělitel p a q nejvyššího možného stupně.
I tentokrát můžeme k hledání největšího společného dělitele (tj. polynomu, který oba uvedené polynomy dělí a je největšího možného stupně) použít Euklidův algoritmus. Místo celočíselného dělení se zbytkem budeme ovšem používat dělení polynomů se zbytkem (připomeňme, že zbytek po takovém dělení musí být buď nulový nebo musí mít stupeň menší než dělitel). Tedy počítejme:
Největším společným dělitelem polynomů x4+x3+2x2+x+1 a x3+x2+x+1 je tedy polynom x2+1. Zpětný běh Euklidova algoritmu má tentokrát jediný krok, tedy hledané polynomy jsou A = 1 a B = -x.
20.10.
Vezmeme-li prvky g1 a g2 z G*, platí, že existují prvky h1 a h2 z G, pro něž gihi=higi=e, kde i=1,2. Tedy (g1g2)(h2h1) = g1(g2h2)h1 = g1eh1 = g1h1 = e a symetricky (h2h1)(g1g2) = e. Zřejmě e.e=e, proto G* obsahuje prvek e. Tedy G* je podmonoid.
Poznamenejme, že je-li G* podmonoidem monoidu (G, . , e), a vezmeme-li operaci omezenou na tento podmonoid .|G*, je (G*, .|G*,e) monoid. Zbývá nám ověřit vlastnost grupy týkající se inverzního prvku. Pokud gh=hg=e=gk=kg, dostáváme h=he=hgk=ek=k, tedy inverzní prvek g-1 je určen jednoznačně. Navíc je množina G* zřejmě na operaci inverzního prvku uzavřena. Tím jsme nahlédli, že G*(.,-1,e) splňuje všechny axiomy grupy.
Přímo z definice dostáváme, že invertibilní prvky (Z,+,0) tvoří celé Z, invertibilní prvky (Z, . ,1) jsou pouze -1 a 1 a invertibilní prvky transformačního monoidu (T(X), . ,id) tvoří právě permutace S(X) na množině X.
Stačí si uvědomit, že k z množiny Zn je invertibilní právě tehdy, když existuje m takové, že (k.m)mod n = 1. Jestliže NSD(k,n)=1, umíme pomocí Euklidova algoritmu najít celá x a y, aby k.x+n.y = 1, hledané m = (x)mod n. Naopak jestliže NSD(k, n) = c > 1, pak pro libovolné m je buď (k.m)mod n = 0 nebo c / (k.m)mod n. Tím jsme ověřili, že Zn* = {k < n | NSD(k,n)=1}.
Použijeme-li právě dokázané tvrzení, dostáváme, že Z9* = {1,2,4,5,7,8}.
Číslo menší než pk je soudělné s pk, právě když je násobkem čísla p. Nezáporných násobků čísla p menších než pk je zřejmě právě pk-1. To znamená, že naopak čísel nesoudělných s pk máme |Zn*| = |Zn| - pk-1 = pk-pk-1= (p-1)pk-1.
Máme-li (Mi, * , 1) i=1,...,k monoidy, definujme na kartézském součinu M1xM2...xMk operaci * po složkách, tj. předpisem
(m1, m2, ..., mk) * (n1, n2, ..., nk) = (m1*n1, m2*n2, ..., mk*nk).
Přímočaře nahlédneme, že operace * je asociativní a (1,1,...,1) je neutrální vzhledem k *.
Definujme zobrazení P monoidu Zn do Zn1xZn1x...xZnk vztahem
P(a) = ((a)mod n1, (a)mod n2, ..., (a)mod nk).
Zřejmě P(0) = (0,...,0) a P(1) = (1,...,1). Protože
(a+b)mod ni =
((a)mod ni+(b)mod ni)mod ni a
(a.bl)mod ni =
((a)mod ni.(b)mod ni)mod ni
dostáváme, že P(a+b) = P(a)+P(b) a P(a.b) = P(a).P(b). Zbývá ověřit, že je P bijekce.
Všimneme-li si, že Zn a M mají stejný počet prvků (n) a že (Zn, +, 0) a (M, +, 0) lze dodefinovat na grupy (Zn, +, -, 0) a (M, +, -, 0), stačí, abychom dokázali, že P je prostý grupový homomorfismus, tj. Ker P=0. Ovšem P(a)=0 právě tehdy když ni/k pro všechna i, tedy nejmenší společný násobek n1,..., nk dělí a. Protože jsou čísla n1,..., nk po dvou nesoudělná a a je menší než n, musí a = 0.
27.10.
Definujme pro každé přirozené n > 1 takzvanou Eulerovu funkci předpisem f(n)=|{k < n | NSD(k,n)=1}|. Všimněme si, že podle příkladu 17 je f(n) rovno právě počtu invertibilních prvků monoidu (Zn, . , 1).
To, že (1,1) je neutrální prvek vzhledem k operaci * a že * je asociativní, dostaneme okamžitě z definice (stejně se v lineární algebře dokazuje, že Tn je vektorový prostor nad T).
Vezměme nejprve (m1, m2) z množiny invertibilních prvků (M1xM2)*. Potom definice zaručuje existenci takového prvku (n1, n2), že
(m1, m2) * (n1, n2)
= (m1.n1, m2.n2)
= (1,1),
(n1, n2) * (m1, m2)
= (n1.m1, n2.m2)
= (1,1).
To znamená, že ni.mi = mi.ni = 1 v monoidu Mi pro i=1,2, proto (m1, m2) leží v M1*xM2*.
Nechť naopak máme m1 z M1* a m2 z M2*. Víme, že potom existují inverzní prvky n1 a n2 k prvkům m1 a m2. Nyní už snadno nahlédneme, že
(m1, m2) * (n1, n2) = (n1, n2) * (m1, m2) = (1,1).
Tím máme ověřeno, že (m1, m2) leží v (M1xM2)*. Dokázali jsme dvě inkluze, tedy rovnost množin.
Nejprve poznamenejme, že monoidy (Zn.m, . ,1) a (ZnxZm, *, (1,1)) jsou podle čínské věty o zbytcích izomrfní. To mimo jiné znamená, že oba monoidy mají stejný počet invertibilních prvků (|Zn.m*| = |(ZnxZm)*|). Použuijeme-li nyní výsledek úlohy 22, dostáváme:
f(n.m) = |Zn.m*| = |(ZnxZm)*| = |Zn* x Zm*| = |Zn*| . |Zm*| = f(n).f(m).
Indukcí za použití předchozích dvou úloh.
Potřebujeme určit hodnotu f(1352) Eulerovy funkce na prvku 1352.Prvočíelný rozklad čísla 1352 je 23132, proto podle předchozího příkladu dostáváme, že |Z1352*|= f(1352)= (13-1).13.(2-1).4= 624.
Stačí si uvědomit, že monoidy mají různé algebraické vlastnosti, a proto nemohou být izomorfní. Zatímco v (Z, +, 0) ke každému prvku existuje inverzní prvek, v monoidu (Z, . , 1) máme invertibilní pouze prvky 1 a -1.
I tentokrát zjistíme, že monoidy mají různé algebraické vlastnosti, a proto nejsou izomorfní. Například si můžeme všimnout, že v monoidu (N0, +, 0) existuje prvek (1) takový, že vezmeme-li libovolný prvek b množiny N0 kromě neutrálního prvku, dostaneme ho pomocí sčítání, tj. b = 1+1+...+1, zatímco například prvek 6 monoidu (N, . , 1) nezískáme jako mocninu žádného přirozeného čísla.
Neexistenci izomorfismu můžeme dokázat také úvahou, že (N, . , 1) obsahuje nekonečně mnoho prvků, které mají až na pořadí jednoznačný rozklad p=x.y, tedy prvočísla. V monoidu (N0, +, 0) můžeme každé kladné číslo n větší než jedna napsat jako n = n+0 = (n-1)+1, tedy kromě dvou žádná další čísla nemají až na pořadí jednoznačný rozklad.
f(2N) = {f(2.n)| n z N} = {f(2) + f(n)| n z N} = {k z N| k+1 > f(2)}
Proto f(N-2N) = {k z N| k < f(2)}, tj. bijektivní obraz množiny všech lichých čísel je konečný, což je spor.
Opět dokážeme, že monoidy mají různé algebraické vlastnosti, a proto nejsou izomorfní. Například si můžeme všimnou, že monoid (Z, +, 0) je dvougenerovaný (konkrétně < 1,-1 > = Z), zatímco pro žádnou dvojici racionálních čísel neplatí, že by generovala (pomocí násobení) celé Q-{0}.
Uvědomíme-li si, že oba uvažované monoidy jsou dokonce grupy a připomeneme-li tvrzení z přednášky (Lemma 1.20), že zobrazení grup zachovávající binární operaci je nutně homomorfismem, pak monoidy (Z, +, 0) a (Q-{0}, . , 1) jsou izomorfní, právě když grupy (Z, +, -, 0) a (Q-{0}, . , -1 , 1) jsou cyklické. Ale zatímco grupa (Z, +, -, 0) je zjevně jednogenerovaná (tedy tzv. cyklická grupa), grupa (Q-{0}, . , -1 , 1) jedním prvkem generovaná není.
Stačí si rozmyslet, že pro všechny prvky a ze Z8* = {1,3,5,7} platí a . a = 1. V monoidu Z4(+,0) máme 3+3=2, což je různé od neutrálního prvku 0. tedy monoidy nejsou izomorfní.
Sestrojíme-li bijekci g: Z2xZ2 do Z8* výčtem g((0,0)) = 1, g((0,1)) = 3, g((1,0)) = 5 a g((1,1)) = 7, snadno ověříne, že se jedná o homomorfismus, tedy dané monoidy jsou izomorfní.
Zřejmě jsou operace násobení matic a skládání zobrazení asociativní a identita respektive jednotková matice jsou neutrální prvky vzhledem k příslušným operacím. Zvolíme-li bázi B prostoru Tn a definujeme-li zobrazení End(Tn) do Tnxn tak, že endomorfismu f přiřadíme jeho matici vzhledem k bázi B([f]B), pak nám tvrzení z lineární algebry dávají
[Id]B=E a [fg]B = [f]B [g]B,
tj. jde o homomorfismus monoidů. Konečně pozorování z lineární algebry (každému homomorfismu odpovídá právě jedna matice vzhledm k daným bázím) zajišťuje, že jde o vzájemně jednoznačné zobrazení, tj. izomorfismus.
3.11.
Nechť G(. , -1, 1) je grupa. Definujme indukcí mocninu na G pro každé celé číslo n:
g0 = 1, gn = g . gn-1 pro n>0, gn = (g-1)|n| pro n<0.
Připomeňme, že (G, . , -1, 1) je cyklická grupa, existuje-li její prvek g, pro nějž < g > = < {g} > = G (tj, jednoprvková množina {g} generuje celou nosnou množinu grupy. Všimněme si, že < g > = {gn; n ze Z}.
Zcela přirozenými příklady cyklických grup jsou celá čísla (Z,+, - ,0) se sčítáním a (Z = < 1 >) celá čísel Zn={0,1, ... , n-1} s počítáním modulo n (Zn, +, - ,0), i tady Zn = < 1 >.
Vezměme libovolnou podgrupu H grupy (Z, +, - ,0) a budeme dokazovat, že je nutně cyklická. Pokud H = {0} je H = < 0 >. Předpokládejme, že je H větší. Potom musí obsahovat nějaké kladné číslo. Vezměme nejmenší kladné číslo k takové, že k leží v H. Tvrdíme, že H = < k >. Zřejmě je < k > částí H. Nechť naopak x leží v H. Můžeme x vydělit se zbytkem číslem k: x = ak + b, kde b je menší než k. Ovšem ak i x jsou prvky H, tudíž i b = x - ak je prvek H. Protože b < k, musí nutně být b=0 a x je prvkem < k >.
Stačí nám definovat zobrazení F: Z do Zn předpisem F(k) = (k) mod n. Snadno nahlédneme, že je F homomorfismus na, tedy podle 1. věty o izomorfismu je Z/ker F izomorfní im F = Zn. Konečně ker F = < n >, odkud dostáváme závěr.
Tvrzení se dokáže rozborem případů. Pro n, m > 0 zřejmě platí, zjevně platí také pro n nebo m = 0. Předpokládejme, že n < 0 a m > 0. Pak gn+m = gm-|n|. Snadno z definice zjistíme, že gm-|n| = gn.gm pro |n| > m, |n| < m i |n| = m. Podobně dostaneme rovnost gn+m = gn.gm i pro další možnosti.
Uvědomme si, že číslo k je přitom generátorem právě tehdy, když podgrupa < k > obsahuje prvek 1 a to nastává právě tehdy, když je NSD(k, n) = 1. Vidíme, že množinu generátorů cyklické grupy (Zn, +, -, 0) tvoří právě invertibilní prvky monoidu (Zn, . , 1)
Podle předchozí úvahy a popisu množiny invertibilních prvků monoidu (Zn, . , 1) Potřebujeme určit hodnotu hodnotu Eulerovy funkce na prvku 50. Prvočíelný rozklad čísla 50 je 522, proto počet generátorů cyklické grupy řádu 100 je f(100)= (5-1).5.(2-1)= 20.
Uvážíme-li, že cyklické grupy řádu 81 je izomorfní grupě (Z81, +, -, 0), postujpujeme stejně jako c předchozím příkladu: prvočíelný rozklad čísla 81 je 34, tedy počet generátorů cyklické grupy řádu 81 je f(81)= (3-1).33= 54.