5. Okruh celých čísel 5.1. Definice. Nechť Q = (G,-), % — {H,-) jsou grupoidy. Řekneme, že grupoid Q lze vnořit do grupoidu ri, jestliže existuje vnoření (tj. injektivní homo-morfismus) / grupoidu Q do grupoidu ri. 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 rt — {H, •) a vnoření / grupoidu Q do grupoidu ri. Pak pro libovolná a, b, c £ G můžemepsát:/(a-(6-c))=/(a)./(6-c) = /(a).(/(6)./(c)) = (/(a)-/W)-/(c) = = f i®-b)-f {c) = f ((a -b) -c) a 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 /(a) = /(&), 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 a ß = [c,d } € G x G položme q'<*- 0, jestliže a • d = b ■ c. Snadno se nahlédne, že relace ~ je reflexivní a symetrická. Sami si dokažte, že její tranzitivnost plyne ze-zákona o krácení. Zlomky a,/3eGxG,a~/3 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ě T budeme definovat operaci o . Pro A, B £ V nechť et = [a,b] £ A, ß — [ c, d ] £ B a nechť G € T je třída určená podmínkou [ a • c, b ■ d ] £ C. Jestliže ai = [ai,h ] £ A, ßi = [ci,di ] £ B, pak c*~ai,ß~ßi, tudíž a • bi = ax ■ &, c-di = c\-d. Odtud plyne a-c-bi-di = ai-ci-b-d, tedy [a-c, b-d] ~ [üi'Ci,bi-d\ ], tudíž [ai -ci,bi-di ] £ C. Třída C nezávisí na volbě reprezentantů a,ß tříd A,B, a je tedy jednoznačně určena třídami A, B. Můžeme pak položit A o B = C. Tím je definována operace o na množině T. Snadno se ověří, že (ľ, o ) je komutativní grupa. Jednotkovým prvkem je třída E = {[g,g } I g £ G} a pro A € ľ je A~x = {[b,a ] \ [a,b ] € A}. Pro 5 € G je Ap = {[ g ■ x, x } \ x € G} prvek grupy (V/o). Nyní definujme zobrazení ip : G '-) ľ vztahem %p(g) = Ag pro g G G, o kterém se snadno přesvědčíme, že je vnořením grupoidu Q do grupy (ľ, o). Pro libovolné g,h € G totiž platí [g ■ g,g ] € Ag, [h- h,h ] 6 Ah, odkud [(g ■ h) ■ (g'- h),g • h ) € Ag o Ah. Současně [(g-h)-(g-h),g-h] £ Ag.h, a tedy AgoAh - Ag.h. Dokázali jsme, že i/> je 34 Obory přirozených, celých a racionálních čísel homomorfismus. Sami si dokažte, opět s využitím zákona o krácení, že zobrazení ijj je prosté. Věta je dokázána. 5.3. Definice. Grupa (ľ, o) konstruovaná v důkazu věty 5.2 se nazývá podílová gr-upa grupoidu Q. Vnoření ip 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 identifikuje se svým obrazem ip(g) — {[g ■ x, x } | x £ G)■ Pologrupa (G, •) je potom podgrupoid své podílové grupy (r, •). 5.4. Poznámka. Jestliže pro a — [ a,b ], ß =s [ctd ] £ G x G definujeme a • ß = [a- c, b • d ], pak ekvivalence ~ na G x G definovaná v důkazu věty 5.2 je koiigruence na grupoidu (G x G,-) a rozklad ľ 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 ] £ A £ ľ platí A ~ yj(a) ■ i/)(b)~l. 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ť (P, •) je podílová grupa asociativního a komutativního grupoidu Q s (G,-), ve kterém platí zákon o krácení. Nechť tp je kanonické vnoření grupoidu G do grupoidu (T,-) a nechť / je homomorfísmus grupoidu Q do nějaké grupy (Po,-)- Pak existuje právě jeden homomorfísmus f grupy (T,-) do grupy (r0, •) tak, že f otp = 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) I / I I \ (IV) Obr. 5. Důkaz. Ukážeme nejdříve, že pro x,y £ G platí f{x)-f(y) — f(y)-f(x) a f(x) ■ ■ fteiy1,^ f{y)~l ■ 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)~x ■ f (x) = f (x) • /(y)-1. Nechť A £ T je libovolné. Pro a = [a, b ] £ A, oji = [oj, 6j ] £ A máme a ~ aj, tudíž b\ ■ a = ai ■ b, odkud plyne /(ř>i) • /(o) = /(aj.) • f (b), z čehož dostáváme Kap. 5. Okruh celých čísel 35 /(a) • /{b)-1 = f {h)'1 • /(«*i)j» /(ai) • fih)-1. Hodnota /(a) • /(o)"1 závisí jen na třídě A a můžeme položit f (A) = /(a) • /(b)-1. Pak / je zobrazení T do P0. Buď A,B G T, a = [o,6 ] G A, /3 = [c,d ) G £. Pak /(A) = }{a) ■ }{b)~\ fß) ~ f [c) ■ f (d)'1, a protože [ o • c, b • d ] 6 A ■ B, platí /(A ■ B) = /(a • c) ■ . /(& . d)-1 = /(a) - /(c) • [f (b) ■ /(d)]"1 = f (a) ■ f (c) ■ [f (d) ■ fib)}'1 = f (a) • /(c) • • fib)'1 ■ f (d)'1 = /(a) • /(ô)"1 • /(c) • /(d)"1 = /(A) • fß). Zobrazení /je tudíž homomorfismus grupy (ľ, •) do (ľo, • }• Nechť g eG. Pak i/>(#) = {[g ■ x, x ] \ x G G}, odkud plyne (položíme-li x- = g) (7° v»)(^= /(s • ô) • /(s)-1 = /(s) • /( ] e A. Pak f (A) = /(a) • /(o)"1 = /iW>(a)) • /iM*»))"1 = - /iW>(a)) • ÄW&r1) - AW>(a) ■ M)-1) = 7i(A) (podle 5A). Tudíž 7= 7i- Buď / injekce, A, B G P, /(A) = f (B), [a,b } e A, [c,d ] e B. Potom /(a) • fib)'1 = /(c)" • /(d)"1, tedy /(Ď)"1 ■ /(a) = /(c) • /(d)-1. Odtud plyne /(a). /(d) = /(&) • /(c), a tedy /(o-d) = /(&•c), z čehož díky tomu, že / je injekce, dostávame a- d = 6 • 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 r : G -4 H je vnoření komutativního grupoidu Q = (G, •) do grupy (ff, •) takové, že ke každému vnoření g grupoidu Q do libovolné grupy (H0,-) existuje jediné vnoření h grupy (ff, •) do grupy (#0,0 s vlastností h o / = g. Potom (Jí,-) 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 = {[ ň + x,x ] | a; G N}. Množina N je pak podmnožina Z a pologrupa (N, + ) je podgrupoid grupy (Z, +). Připomeňme, že nulovým prvkem této grupy je třída {[i,i]|i £ 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 ] 6 %}.. 5.8. Definice. Na množině Z definujeme operaci násobení následujícím, způsobem. Pro a,ß 6 Z, [a,b } € a, [c,d ) € ß klademe a ■ ß = 7, kde 7 G Z je třída určená podmínkou [ ac + bd, ad + bc ] G 7. Jestliže [u, v} G a,[r, s] G ß jsou jiní reprezentanti tříd a, ß, pak [a, b] ~ [ti,«], [c,d ] ~ [r,s.]', tudíž a + ü = tz + 6, c + s = d + r, odkud plyne ca + cu = eu + c6, db + dii = da + dv, uc + us = ud + ur, wd + i>7- = 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-4- sv, což znamená, že rozdíly [ ac + bd, ad+bc] a [ur + sv, us + vr ] jsou ekvivalentní. Třída 7 nezávisí tudíž na volbě reprezentantů tříd a,ß. 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, ß je součin a-ß roven 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ß místo a ■ ß. 5.9. Tvrzení. Grupoid (Z,') je komutativní, asociativní a má jednotkový prvek, který je roven přirozenému číslu 1. Pro a.^jSZj^O pJatí a • 7 — ß ■ 7 =*■ q =5 /3 (tzv. omezený zákon o krácení). Důkaz. Platnost komutativního zákona plyne ihned z definice. Buď«,/?,7GZ,[a,Ď]ea,[c,d] £ß,[e,f] £7. Pak [ ac + č>d, ad + bc ] G a ■ /?, [ ce + df, cf + de ] G ß ■ 7. Tedy [ iac + bd)e + (ad + ďc)/, (ac + bd)f + iad + bc)e } G (a • ß) • 7, [ (ce + d/)a + (c/ + de)b, (ce + d/)& + (c/ + de)a ] G a ■(ß ■ 7). Jelikož se oba tyto rozdíly rovnají, platí (a ■ /?) • 7 = a • (/3 • 7). Nechť a; G N. Pak [ 1 + x,x ] € 1, tudíž [ a(l + x) + bx, 6(1 + + 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 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, ß G Z klademe a < ß, jestliže a < ß a a ^ ß. 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,ß,y G Z, [a, b ] G a, [c, d] E ß, Jestliže a < /?, /3 < a, pak platí a + d < í> + c, b + c < a + d, tudíž a + d = b + c, odkud plyne [O,Í> ] ~ [c,d],.a tedy a — ß. Relace je antisymetrická. Nechť a < ß, ß < 7, potom a + d < 6 + c, c + / < e + d. Sečtením těchto nerovností (podle 4.12 (b), (d)) dostaneme a + f < b + e, tudíž a < 7. Relace < je tranzitivní. Platí a + d < b + c nebo b + c < a + d. V prvním případě dostaneme a < ß a ve druhém ß < a. Relace < je úplná. Věta je tímto dokázána. 5.13. Tvrzení. Při identiňkaci provedené v 5.7platí {z e Z | 0 < z} = N, {z e Z i z <0} = {-n | n £ N}. . . Důkaz. Nechť z e K Pak [ z + 1,1 ] G z, [ 1,1 ] G 0. Jelikož l + l f {b) < f (a). Zobrazení / z 5.14 je tudíž antiizomorfismus uspořádané množiny (N, <) na uspořádanou množinu ({-n | nGN},<). 38 Obory přirozených, celých a racionálních čísel 5.16. Věta. Nechť a, ß, 7,6 G Z. Pak platí (a) a < ß a + 7 a • 7 ^ /3 • 7, (f) pro 7 < 0 p/at/: a < /3 <ř=> /3 ■ 7 < a • 7, a4-/ + c + e. Jelikož [a + e,Ď + /]Ga + 7,[c+e, d + /]G/3 + 7, pak a + 7 < ß + 7. Je-li a + 7 < /? + 7, potom podle předchozího a = (a + 7) + (-7) < (ß + 7) -I-+ (-7) = /3. Platí tudíž (a), odkud se snadno odvodí výroky (b), (c), (d). Nechť 0 < 7. Pak / + / 0, -a, pro a < 0, 1, pro a >c0, sgna=^ 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,ß G Zplati\a-ß\ = |a|-|/3|, |a| = a-sgna, a = |a|-sgna. 5.19. Věta (o dělení dvou celých čísel se zbytkem). Nechť a, ß jsou celá čísla, ß ýí. 0. Pak existují celá čísla 7, g tak, že platí: a = ß • 7 + ß, 0 < g < \ß\. Čísla 7, g s těmito vlastnostmi jsou určena jednoznačně. Důkaz. Položme M = {a — ß • X | % € Z,a— ß • x > 0}. Ukážeme, že a — /3 • • (-sgn/3) • |a| G M. Skutečně a- ß ■ (-sgn/3,) • \a\ — a + \ß\ ■ \a\ > a + \a\ > 0, neboť \ß\ > 1. Tedy M ^ 0 a podle 4.15 má množina .M nejmenší prvek g. Pak existuje 7 G Z takové, že a - $7 — g, tedy a = ,#7 + g. Pokud |/?| < gf pak 0 < É" - \ß\ = a — ß{l + sgn/3) a tudíž g - \ß\ G M, což je spor, neboť g byl nejmenší prvek M. Odtud plyne g < \ß\. Kap. 5. Okruh celých čísel 39 Ukažme nyní jednoznačnost čísel 7, q. Buďte 7,71, Q,Q\ € Z, a = ßj + q — = ßli + ft, 0 < Q < \ß\, 0 < m < \ß\, pak /3(7 - 71) = 01 - ß. Vzhledem k -\ß\ < -q < 0 máme -|/3| < gi - q < \ß\, tzn. \qi - q\ < \ß\. Odtud plyne \ß\ > |/3(7 - 7i)| = |/3[ • I7 - 7i|, což vzhledem k \ß\ > 0 dává I7 - 7i| < 1. Tedy 7 — 7i, z čehož plyne také Q = 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 ß a číslo q se nazývá zbytek po dělení čísla a číslem ß. Jestliže zbytek po dělení čísla a číslem ß je roven 0, říkáme, že číslo ß dělí číslo a a píšeme ß | a. Číslo ß se pak nazývá dělitel čísla a a číslo a násobek čísla ß. 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álcladní věta aritnietiky celých čísel. Každé celé číslo m ^ 0 lze jednoznačně, až na pořadí, psát ve tvaru m = s p"1 . .".jj£*, lede Pi,...,p/. jsou navzájem různá prvočísla, Oi,.-..., o* přirozená čísla,, e g {1, -1} a k > 0 celé číslo. 5.22. Poznámka. Výrazy typu p"1 .. .p^, (ii + • •• + .a* a pod. se definují rekurentně. Pro /; = 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ě {pí,... ,Pk}- 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 vp(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 E Ii,a^ 0 ^ 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: m=e JJp"p(rn), pev kde e € {1, -1} a V 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é.