33 5. Okruh celých čísel 5.1. Definice. Nechť Q = (G,-), H — (H,-) jsou grupoidy. Řekneme, že grupoid Q lze vnořit do grupoidu H, jestliže existuje vnoření (tj. injektivní homo-morfismus) / grupoidu Q do grupoidu "H. Vyřešíme nyní otázku, kdy komutativní grupoid lze vnořit do nějaké grupy. (Nekomutativní případ přesahuje rámec tohoto textu.) 5.2. Věta. Nechť Q = (G, •) je komutativní grupoid. Pak následující výroky jsou ekvivalentní: (a) Grupoid Q je asociativní a platí v něm zákon o krácení. (b) Grupoid Q lze vnořit do nějaké grupy. Důkaz. Nejdříve ukážeme implikaci „(b)=»(a)". Nechť tedy existuje grupa H — (H, •) a vnoření / grupoidu Q do grupoidu Ti. Pak pro libovolná a, b, c G G můžeme psát: f (a- (b-c)) = f (a) -f (b-c) = f (a) ■ (f(b) ■ f(c)) = (f (a) ■ f (b)) ■ f (c) = = f(a-b)-f(c) = f((a-b)-c) & z injektivnosti zobrazení / plyne a-(b-c) = (a-b)-c. Grupoid Q je tudíž asociativní. Nechť dále platí a • c = b • c. Pak f (a) ■ f (c) = = f [a-c) — f {b-c) — f (b) ■ f (c) a jelikož v grupě platí zákon o krácení, dostáváme f (a) = f (b), z čehož plyne a — b. Platí výrok (a). Nyní dokazujeme implikaci „(a)=^(b)". Předpokládejme tedy, že grupoid Q je asociativní a platí v něm zákon o krácení. Prvek a = [a, b ] € G x G nazveme zlomkem grupoidu Q a na množině G x G všech zlomků grupoidu Q definujeme relaci ~ následující podmínkou: pro a = [a,b ] € G x G & f3 = [c,d ] € G x G položme a ~ P, jestliže a • d — b ■ c. Snadno se nahlédne, že relace ~ je reflexivní a symetrická. Sami si dokážte, že její tranzitivnost plyne ze zákona o krácení. Zlomky a, P G G x G, a ~ P nazýváme ekvivalentní. Rozklad na G x G příslušný relaci ~ označme T. Prvek z T je pak třída ekvivalentních zlomků grupoidu Q. Na množině F budeme definovat operaci o . Pro A, B G T nechť a = [a,b] 6 A, P = [crd ] € B a nechť G € T je třída určená podmínkou [o • c, b ■ d ] G C. Jestliže ax = [■£»!,&i ] 6 A, Pi = [ci,di ] € B, pak a ~ «i, 0 ~ Pi, tudíž a ■ &i - a^-b, c-di = Ci-d. Odtud plyne a-c-bi-d\ = d\-C\-b-d, tedy [a-c,b-d] ~ [«ii-ci,&i-d\ ], tudíž [ai ?Ci,&i -di ] € C. Třída G nezávisí na volbě reprezentantů a, P tříd A,B, a je tedy jednoznačně určena třídami A, B. Můžeme pak položit A o B = G. Tím je definována operace o na množině T. Snadno se ověří, že (F, o ) je komutativní grupa. Jednotkovým prvkem je třída E = {[9,9 } I 9 S G} a pro A € V je A~l = {[b,a } | [a,b ] G A}. Pro g e G je Ag = {[g ■ x,x } \ x e G} prvek grupy {T,o). Nyní definujme zobrazení i/> : G ľ vztahem ip(g) = Ag pro g € G, o kterém se snadno přesvědčíme, že je vnořením grupoidu Q do grupy (r, o). Pro libovolné g,h G G totiž platí [ g ■ g, g } G Ag, { h ■ h, h ] G Ah, odkud [ (g ■ h) ■ (g • h),g ■ h } G Ag o Současně -(g-h), g-h } G >lg/l,atedy AgoAh = Dokázali jsme, žei/»je 34 Obory pň'roze/iýcii, celých a racfoná/n/cJi čísei homomorŕismus. Sami si dokažte, opět s využitím zákona o krácení, že zobrazení \\) je prosté. Věta je dokázána. 5.3. Definice. Grupa (r, o) konstruovaná v důkazu věty 5.2 se nazývá podílová grupa grupoidu Q. Vnoření tp se nazývá kanonické vnoření grupoidu Q do jeho podílové grupy, Jelikož není nebezpečí nedorozumění, často označujeme operaci o na F stejným symbolem jako operaci na grupoidu Q. Užíváme-li aditivní zápis operace, mluvíme o rozdílové grupě (místo podílové) a místo názvu zlomek se užívá název rozdíl. Často se prvek g G G identifikuje se svým obrazem ip(g) — {[g ■ x, x } \ x G G}. Pologrupa (G, •) je potom podgrupoid své podílové grupy (F, ■). 5.4. Poznámka. Jestliže pro a = [a, b ], P — [c, d] E G x G definujeme a - P = [a ■ c, b-d], pak ekvivalence ~ na G x G definovaná v důkazu věty 5.2 je kongruence na grupoidu (G x G,-) a rozklad T je vytvořující rozklad na tomto grupoidu. Podílová grupa (r, •) je pak faktorgrupoid grupoidu (G x G, • )• Všimněme si ještě, že pro [ a, b ] G A G T platí A = ip(a) ■ t/>(6)-1. Mezi grupami, do kterých se dá uvažovaný grupoid vnořit, má podílová grupa význačné postavení charakterizované následující větou. 5.5. Věta. Nechť (F, ■) je podílová grupa asociativního a komutativního grupoidu Q ss (G, •), ve kterém platí zákon o krácení. Nechť ip je kanonické vnoření grupoidu Q do grupoidu {V,-) a nechť f je homomorfísmus grupoidu Q do nějaké grupy (r0,-)- Pak existuje právě jeden homomorfísmus f grupy (F, •) do grupy (To, •) tak, že f orp = f. Jestliže f je vnoření, pak f je taktéž vnoření. Můžeme pak říci, že diagram na obrázku 5 komutuje. (IV) (IV) Obr. 5. Důkaz. Ukážeme nejdříve, že pro x,y G G platí f (x)-f (y) = f (y)-f (x) a f (x) ■ ■ fbtV1,- f (y)'1 ■ f (x). Skutečně z x ■ y = y ■ x plyne f (x) ■ f (y) = f {y) ■ f (x)., z čehož dostáváme taktéž f (y)"1 • f (x) = f (x) ■ /(y)-1. Nechť A G T je libovolné. Pro a = [a, b j É A, ai = [a\, 6i ] G A máme a ~ aj, tudíž &i • a — Qi • b, odkud plyne f(bi) ■ f (a) — f(ai) ■ f (b), z čehož dostáváme Kap. 5. Okruh celých čísel 35 /(a) • = /(h)'1 ■ f(d)j= /(ai) • /(fci)-1. Hodnota /(a) • /(6)_1 závisí jen na třídě A a můžeme položit f (A) = f (a) • /(6)_1. Pak / je zobrazení F do T0. Buď A,B G T, a = [a,6 ) € A, 0 = [c,d ] € B. Pak /(A) = /(a) • f(b)~\ f(B) = f(c) • /(d)-1, a protože [a ■ c,b• d ] € A • B, platí /(A ■ £) = f (a • c) • . /(Ď . = /(a) ■ /(c) • [/(&) • /(d)]-1 = /(a) • f(c) ■ [f(d) ■ = f (a) ■ f(c) ■ • /(&)"1 • fid)'1 = /(o) • /W-1 • /(c) ' = /(^) ■ /(£)■ Zobrazení / je tudíž homomorfismus grupy (r, •) do (r0, •). Nechť g € G. Pak Xš) = {[ár-.«,a? ] | x G G}, odkud plyne (položíme-li x = 3) (Jo t/OGri = /(S • 9) ■ /(í)"1 = /(í) • /(ff) • /(i)'1 - Sis)- Tedy / o i(V»(a)) ■ /iOM&))-1 = = /i(V(o)) ■ JiWW1) - 7i(V»(a) • VM-1) = /i(A) (podle 5A). Tudíž J= Ji. Buď / injekce, A, B G T, /(A) = f (B), [ a, 6 ] G A, [ c, d ] G B. Potom /(a) • f (b)'1 = /(c) • f (d)-1, tedy /(Ď)"1 • /(a) = f (c) • /(d)"1. Odtud plyne /(a) - /(d) = f (b)-f (c), a tedy /(a-d) = /(6-c), z čehož díky tomu, že / je injekce, dostáváme a-d = b-c, A -B. Zobrazení / je tedy též injekce. Věta je dokázána. 5.6. Poznámka. Věta 5.5 skutečně charakterizuje podílovou grupu, neboť lze dokázat i opačnou implikaci. Přesněji platí: Nechť- f:: G -> H je vnoření komutativního grupoidu Q = (G, •) do grupy (H, ■) takové, že ke každému vnoření g grupoidu G do libovolné grupy (H0, ■) existuje jediné vnoření h grupy {H, ■) do grupy (H0,-) s vlastností h o f = g. Potom (H, ■) je izomorfní podílové grupě grupoidu Q. 5.7. Definice. Rozdílová grupa pologrupy (N, + ) se nazývá aditivní grupa celých čísel a značí se (Z, + ). Prvek množiny Z se nazývá celé číslo. Celé číslo je tedy třída ekvivalentních rozdílů [ a, b } G N x N pologrupy (N, + ). Přirozené číslo n G N identifikujeme s jeho obrazem v Z při kanonickém vnoření, tudíž n - {[ n + x,x } \ x G N}. Množina N je pak podmnožina Z a pologrupa (N, +) je podgrupoid grupy (Z, +). Připomeňme, žě nulovým prvkem této grupy je třída {[ x,x ) \ x G N}, která se označuje symbolem 0 a nazývá se číslo nula nebo jen nula. Pro z G Z je —z — {[ b, a ] \ [ a, b ] G z}. 5.8. Definice. Na množině Z definujeme operaci násobení následujícím způsobem. Pro a, P G Z, [ a, b J G a, [ c, d ] G j8. klademe a • /? = 7, kde 7 G Z je třída určená podmínkou [ ac + bd, ad + bc ] G 7. Jestliže [u, u] G a, [r, 3] G 0 jsou jiní reprezentanti tříd a, P, pak [a, 6] ~ [u, v], [ c, d ] ~ [r, s ], tudíž a + u = ií + ř>, c + s = d + r, odkud plyne ca + cu = cu + cb, db + du = da + dv, uc + us = ud + ur, ud+tr == uc+ws. Sečtením a užitím zákona o odečítání 4.7 dostaneme ac+bd + us + vr = ad + bc + ur + su, což znamená, že rozdíly [ac+ bd,ad+ bc] a [ ur + sv, as + vr ] jsou ekvivalentní. Třída 7 nezávisí tudíž na volbě reprezentantů tříd a,/3. Definice operace násobení je tudíž korektní. 36 Obory přirozených, celých a racionálních čísel Zřejmě pro přirozená čísla a, (3 je součin a-/? rovea dříve definovanému součinu na N. Stejně jako na množině přirozených čísel při zápisu operace násobení často vynecháváme symbol ■, píšeme tedy a/3 místo a ■ f3. 5.9. Tvrzení. Grupoid (Z,-) je komutativní, asociativní a má jednotkový prvek, který je roven přirozenému číslu 1. Pro a, 7 G Z, 7 ^ 0 platí a • 7 = /3 ■ 7 a = P (tzv. omezený zákon o krácení). Důkaz. Platnost komutativního zákona plyne ihned z definice. Buď a, 0,7 G 1,[a,b ] G a, [c, d ] € j9,[e,/ ] G 7. Pak [ ac + 6d, ad 4- bc ] G a • /3, [ ce + df, cf + de ] G P ■ 7. Tedy [ (ac + bd)e + (ad + 6c)/, (ac + bd)f + (ad + bc)e } G (a ■ $) ■ 7, [ (ce + d/)a + (cf + de)6, (ce + d/)6 + (c/ + de)a ] G a •(0 • 7). Jelikož se oba tyto rozdíly rovnají, platí (a • 0) • 7 = a • (0 • 7). Nechť a; G N. Pak [ 1 + x, x ] G 1, tudíž [ a(l + x) + bx, 6(1 + x) + ax ] G 1 • a. Jelikož [ a(l + x) + bx, 6(1 + x) + ax ] ~ [ a, 6 ], platí 1 ■ a = a. Nechť 7^0aa-7 = /3-7. Pak [ ae + 6/, a/ + 6e ] ~ [ ce + df, cf + de ], tudíž ae + bf + cf + de = af + be + ce + df, odkud plyne (a + d)e + (b + c)f = (b + c)e + (a + d)f (*). Jelikož 7^0, platí e ^ /, a pak e < / nebo / < e. Existuje tudíž n G N tak, že f = e + n nebo e = / + n. Dosazením do rovnosti (*) dostaneme v obou případech pomocí zákona o odečítání 4.7 rovnost n(6 + c) = n(a + d), z čehož užitím 4.25 (b) plyne 6 + c = a + d, tedy [ a, 6 ] ~ [ c, d ] a a = 0. Tvrzení je tím dokázáno. Sami si dokažte, že operace + a • na Z jsou svázány distributivním zákonem, z čehož pak podle 5.9 plyne: 5.10. Věta. Trojice (Z, + ,-)je obor integrity, jehož jednotkový prvek je roven přirozenému číslu 1. 5.11. Definice. Pro celá čísla a, 0 nechť [a, b ] G a, [c, d] e 0. Položme a < 0, jestliže a + d < b + c. Vztah a < 0 nezávisí na volbě reprezentantů tříd a,0: pokud [u,v ] G a, [r,s ] G 0, pak [a,6 ] ~ [u,v ],[c,d ] ~ [r,s ],•• tudíž a + v = b + u, d + r — c + s, odkud dostaneme sečtením a + d + r + v = b + c + u + s. Je-li a + d = 6 + c, pak u + s — r + v. Jestliže a + d < b + c, pak existuje přirozené číslo n tak, že platí a + d + n = b + c, tedy r + v = u + s + n, odkud plyne u + s < r + v. Ověřili jsme, žeza + d<6 + c plyne u + s < r + v; analogicky je možné ověřit opačnou implikaci. Výše uvedená definice relace < je proto korektní. Kap. 5. Okruh celých čísel 37 38 Obory přirozených, celých a racionálních čísel Tím je definována na množině Z relace <, která zřejmě pro přirozená čísla souhlasí s dříve definovanou relací < na množině N. Pro celá čísla a, 0 G Z klademe a < 0, jestliže a < 0 a a ^ 0. O číslu a řekneme, že je kladné (resp. záporné), jesliže 0 < a (resp. a < 0). V opačném případě hovoříme o čísle nekladném (resp. nezáporném). 5.12. Věta. .Relace < na množině Z je lineární uspořádání. Důkaz. Zřejmě je relace < reflexivní. Nechť a,0,7 G Z, [a, Ď ] 6 a, [c,d ] G /?, [e,/ ]>T Jestliže a < 0, 0 < a, pak platí a + cř<ř> + c, 6 + c /(&) < /(a). Důkaz. Pro a,6 G N, a < 6 platí nerovnost a + a + a < a-f-6 + a. Jelikož [a, a + a ] G -a, [ a, a + 6 ] G —6, pak —b < -a, tedy f (b) < f {a). Odtud se již snadno dokáže, že / je bijekce splňující uvedenou podmínku. 5.15. Poznámka. Nechť (P, <), (Q, <) jsou lineárně uspořádané množiny, / bijekce P na Q. Zobrazení / se nazývá antiizomorfismus uspořádané množiny (P, < ) na (Q, < ), jestliže platí: a,b G P,a < b f {b) < f (a). Zobrazení / z 5.14 je tudíž antiizomorfismus uspořádané množiny (N, <) na uspořádanou množinu ({-n I n G N},<). 5.16. Věta. Necht! 0,0,1,6 G Z. Pak platí (a) a < 0 4=» a + 7 a + 7 < 0 + ô, (e) pro 0 < 7 piat/: a < 0 <=> a • 7 < /? • 7, a < 0 <=> a ■ 7 ^ /3 • 7, (f) pro 7 < 0 piat/: a < /3 4=> /3 ■ 7 < a • 7, a < 0 0 ■ 7 < a • 7. Důkaz. Nechť [ a, 6 ] G a, [ c, d ]£/?,[ e, /] G 7. > Jestliže a < 0, pak a + (i < 6 + c a z 4.12 (a) plyne a + e + ci + / < 6+/ + c + e. Jelikož [a + e,6 + / ] Ga + 7, [c + e, d + / ] G^ + 7, pak a + 7 < 0 + 7. Je-li a + 7 < /? + 7, potom podle předchozího a = (a + 7) + (-7) < (0 + j) + + (—7) = 0. Platí tudíž (a), odkud se snadno odvodí výroky (b), (c), (d). Nechť 0 < 7. Pak / + / < e + / a z 4.12 (a) dostáváme '/ < e, tedy existuje n G N tak, že / + n = e. Nerovnost a < 0 platí právě tehdy, když a + d < b + c, což nastane podle 4.25 (a) právě tehdy, když (a + d)n < (b + c)n. Tato nerovnost je ekvivalentní s nerovností (a + d)e + (b + c)f < (b + c)e + (a + d)f, která platí, právě když a • 7 < 0 -7. Odtud pak plyne druhá ekvivalence ve výroku (e). Výrok (f) plyne z (e) a z tvrzení 5.14. 5.17. Definice. Pro celé číslo a G Z položíme a, pro a > 0, -a, pro a < 0, 1, pro a >c0, 0, pro a = 0, -1, pro a < 0. Číslo |a| se nazývá absolutní hodnota čísla a a zřejmě \a\ > 0. Číslo, sgna se nazývá znaménko (signum) čísla a. Zřejmě platí: 5.18. Tvrzení. Proa,0 G Z platí \a-0\ = \a\-\0\, \ct\ = a-sgna, a = |a|-sgna. 5.19. Věta (o dělení dvou celých čísel se zbytkem). Nechť a, 0 jsou celá čísla, 0^0. Pak existují celá čísla 7, g tak, že platí: a — 0 ■ j + q, 0 < g < \0\. Čísla 7, g s těmito vlastnostmi jsou určena jednoznačně. Důkaz. Položme M = {a — 0 ■ x \ x G Z, a — 0 ■ x > 0}. Ukážeme, že a — 0 ■ ■ (-sgn0) ■ |a| G M. Skutečně a - 0 ■ (-sgn/3,) -\a\=a + \0\ ■ \a\ > a + \a\ > 0, neboť \0\ > 1. Tedy M £ 0 a podle 4.15 má množina M nejmenší prvek g. Pak existuje 7 G Z takové, že a - 0j - g, tedy a = 0j + Q. Pokud \0\ < g,- pak 0 < g — \0\ = a — 0(*y + sgn/3) a tudíž g - \0\ G M, což je spor, neboť g byl nejmenší prvek M. Odtud plyne g < \0\. Kap. 5. Okruh celých čísel 39 Ukažme nyní jednoznačnost čísel 7, g. Buďte 7,71,5,01 6 Z, a = 01 + g = == >7i■+ :'ť?i, 0 < Q < \0\, 0 < 01 < \0\, pak j9(7 - 71) = Qi ~ Q- Vzhledem k -\0\ < -í> < 0 máme < 51 - £> < \/3\, tzn. - e| < |j9|. Odtud plyne \0\ > 1/3(7 - 7i)l = \0\ ■ Í7 ~ Til, což vzhledem k \0\ > 0 dává I7-71I < 1. Tedy 7 = 71, z čehož plyne také g = Q\. Věta je dokázána. 5.20. Definice. Číslo 7 z věty 5.19 se nazývá (neúplný) podíl po dělení čísla a číslem P a číslo 5 se nazývá zbytek po dělení čísla a číslem /9. Jestliže zbytek po dělení čísla a číslem 0 je roven 0, říkáme, že číslo 0 dělí číslo a a píšeme /? | a. Číslo /? se pak nazývá dělitel čísla a a číslo a násobek čísla 0. Každé číslo a má dělitele 1,-1,a, —a. Tito dělitelé se nazývají nevlastní dělitelé čísla a, ostatní dělitelé se nazývají vlastní dělitelé čísla a. Zřejmě číslo 1 má pouze dva nevlastní dělitele. Jestliže celé číslo p > 1 nemá vlastní dělitele, nazývá se prvočíslo. Prvočísla jsou 2,3,5,7,... . Dělitel celého čísla a, který je prvočíslem, se nazývá prvočinitel čísla a. Z věty 5.19 o dělení dvou celých čísel se zbytkem se dá odvodit následující věta o jednoznačnosti rozkladu celého čísla na prvočinitele. Důkaz této věty lze nalézt např. v [4, věta 2.3. v kap. 3]. 5.21. Základní věta arithietiky celých čísel. Každé celé Číslo m ^ 0 lze jednoznačně, až na pořadí, psát ve tvaru m — g p"1 .. .pakk, kde pi,... ,pu jsou navzájem různá prvočísla, ai,..., o* přirozená čísla, e 6 {1, -1} a k > 0 celé číslo. 5.22. Poznámka. Výrazy typu p"1 .. .p^, ái + ••• + a* a pod. se definují rekurentně. Pro k — 0 rozumíme výrazem ep"1 .. .p£fc číslo e. 5.23. Definice. Pro celé číslo m ^ 0 se tvar čísla m v 5.21 nazývá kanonický rozklad čísla m na prvočinitele. Z 5.21 pak plyne, že množina prvočinitelů m je rovna množině {pi,... ,Pfc}. Buď p prvočíslo. Jestliže p je prvočinitel čísla m, položme vp(m) — a*, kde p — Pi. Není-li p prvočinitel čísla m (tj. p nedělí m), položíme vv(m) — 0. Hodnota vp(m) se nazývá exponent čísla m příslušný prvočíslu p. Je tedy vp zobrazení množiny celých nenulových čísel na množinu celých nezáporných čísel. Pro celá nenulová čísla o, & a prvočíslo p platí vp(a ■ b) = vp(a) + vp(b). Dále pro a, b € Z,aj^ 0 jí b platí: a — ±b právě tehdy, když vp(a) = vp{b) pro každé prvočíslo p. Celé nenulové číslo m budeme často vyjadřovat ve tvaru tzv. formálně nekonečného součinu: p€7> kde e € {1, —1} a T7 je množina všech prvočísel. Uvědomte si, že všichni činitelé v tomto součinu s výjimkou konečně mnoha se rovnají jedné.