Matematika IV - 5. přednáška Okruhy a tělesa, okruhy polynomů
Michal Bulant
Masarykova univerzita Fakulta informatiky
22. 3. 2010
□         S
oooooooooooo
Obsah přednášky
Okruhy a tělesa
ô Dělitelnost a nerozložitelnost
n          S           -           =          -E      -00*0
oooooooooooo
Doporučené zdroje
•  Martin Panák, Jan Slovák, Drsná matematika, e-text.
•  Předmětové záložky v IS MU
□     s
oooooooooooo
Doporučené zdroje
•  Martin Panák, Jan Slovák, Drsná matematika, e-text. a Předmětové záložky v IS MU
•   R. B. Ash, Abstract algebra,
http://www.math.uiuc.edu/~r-ash/Algebra.html.
•  Jiří Rosický, Algebra, PřF MU, 2002.
•  Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF).
•  Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone , Handbook of Applied Cryptography, CRC Press, 2001, 780 p., http://www.cacr.math.uwaterloo.ca/hac/
oooooooooooo
Plán přednášky
Okruhy a tělesa
iost a nerc
n          S           -           =          -E      -00*0
S grupami se potkáváme nejčastěji jako s množinami transformací. U skalárů ale vystupovalo hned více obdobných struktur zároveň. Jako standardní příklady mějme na mysli skaláry (tj. celá čísla Z, racionální čísla Q, reální či komplexní čísla R, C) a množiny polynomů nad takovými skaláry R. Klasickým příkladem konečného okruhu je pak Zm.
Okruhy
S grupami se potkáváme nejčastěji jako s množinami transformací. U skalárů ale vystupovalo hned více obdobných struktur zároveň. Jako standardní příklady mějme na mysli skaláry (tj. celá čísla Z, racionální čísla Q, reální či komplexní čísla R, C) a množiny polynomů nad takovými skaláry R. Klasickým příkladem konečného okruhu je pak Zm.
Definice			
Komutativní grupa (/?,+) s neutrálním prvkem s operací • se nazývá komutativní okruh (/?, +		Oe	R, spolu pokud splňuje
• (a • b) ■ c = a ■ (b ■ c),	xo všechny a, b, c G	R	(asociativita);
• a ■ b = b ■ a, pro všechny a, b G R			(komutativita);
• existuje prvek 1 takový (existence jedničky);	že pro všechny a G	R	platí 1 • a = a
• a(b + c) = ab + a-(distributivita).	c, pro všechny a, b,	c e	R -■
Definice
Jestliže v komutativním okruhu R platí c • d = 0 právě, když je alespoň jeden z prvků c a d nulový, pak okruh R nazýváme oborem integrity.
□     s
Definice
Jestliže v komutativním okruhu R platí c • d = 0 právě, když je alespoň jeden z prvků c a d nulový, pak okruh R nazýváme oborem integrity.
Pokud neplatí vlastnost komutativity operace •, hovoříme
o nekomutativním okruhu (nebo pouze o okruhu). V dalším se
obvykle omezíme pouze na okruhy komutativní.
□      s       -
Definice
Jestliže v komutativním okruhu R platí c • d = 0 právě, když je alespoň jeden z prvků c a d nulový, pak okruh R nazýváme oborem integrity.
Pokud neplatí vlastnost komutativity operace •, hovoříme
o nekomutativním okruhu (nebo pouze o okruhu). V dalším se
obvykle omezíme pouze na okruhy komutativní.
Operaci + budeme říkat sčítání a operaci • násobení. Navíc
budeme vždy předpokládat existenci jedničky 1 pro operaci
násobení, neutrálnímu prvku pro sčítání říkáme nula.
□      s
V každém komutativním okruhu R s jedničkou platí následující vztahy (které nám jistě připadají samozřejmé u skalárů)
O 0 • c = c • 0 = 0 pro všechny c G R,
@ —c = (—1) ■ c = c ■ (—1) pro všechny c G R,
Q —(c • d) = (—c) ■ d = c ■ (—d) pro všechny c, d e R,
a ■ (b — c) = a ■ b — a ■ c,
Dělitelnost v okruhu
Obecně říkáme, že a G R dělí cg/?, jestliže existuje b tak, že a ■ b = c. Skutečnost že c G R je dělitelné a G R zapisujeme a\c.
□     s
Obecně říkáme, že a G R dělí c G R, jestliže existuje b tak, že a ■ b = c. Skutečnost že c e R je dělitelné a e R zapisujeme a\c. Dodatečnou vlastností oboru integrity oproti obecnému okruhu je neexistence netriviálních dělitelů nuly. Okamžitě odtud také vyplývá jednoznačnost dělitelů:
Dělitelnost v okruhu
Obecně říkáme, že a G R dělí cg/?, jestliže existuje b tak, že a ■ b = c. Skutečnost že c G R je dělitelné a G R zapisujeme a\c. Dodatečnou vlastností oboru integrity oproti obecnému okruhu je neexistence netriviálních dělitelů nuly. Okamžitě odtud také vyplývá jednoznačnost dělitelů:
Platí-li v oboru integrity a dáno volbou a, b.
b ■ c a b 7^ 0, pak c je jednoznačně
□     s
Dělitelnost v okruhu
Obecně říkáme, že a G R dělí cg/?, jestliže existuje b tak, že a ■ b = c. Skutečnost že c G R je dělitelné a G R zapisujeme a\c. Dodatečnou vlastností oboru integrity oproti obecnému okruhu je neexistence netriviálních dělitelů nuly. Okamžitě odtud také vyplývá jednoznačnost dělitelů:
Platí-li v oboru integrity a dáno volbou a, b.
b ■ c a b 7^ 0, pak c je jednoznačně
Pro a = be = be' totiž platí 0 = b ■ (c — c') a b ^ 0, proto
D
□         S
Dělitelé jedničky, tj. invertibilní prvky v R, se nazývají jednotky. Jednotky v komutativním okruhu vždy tvoří komutativní grupu. Netriviální (komutativní) okruh, ve kterém jsou všechny nenulové prvky invertibilní, se nazývá (komutativní) těleso.
□      s
Dělitelé jedničky, tj. invertibilní prvky v R, se nazývají jednotky. Jednotky v komutativním okruhu vždy tvoří komutativní grupu. Netriviální (komutativní) okruh, ve kterém jsou všechny nenulové prvky invertibilní, se nazývá (komutativní) těleso. V české literatuře se někdy v případě komutativního tělesa můžete setkat s pojmenováním pole (z angl. field).
□     s
Typickým příkladem komutativních těles jsou číselné obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p.
□      s
Typickým příkladem komutativních těles jsou číselné obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p. Základním příkladem nekomutativního okruhu s jedničkou je množina Matk(R) všech čtvercových matic nad okruhem R s k řádky a sloupci. Jak jsme viděli dávno, není to ani obor integrity.
□      s
Typickým příkladem komutativních těles jsou číselné obory Q, R, C. Dále pak všechny okruhy zbytkových tříd Zp s prvočíselným p. Základním příkladem nekomutativního okruhu s jedničkou je množina Matk(R) všech čtvercových matic nad okruhem R s k řádky a sloupci. Jak jsme viděli dávno, není to ani obor integrity. Jako příklad nekomutativního okruhu, kde existují inverze k nenulovým prvkům (tzv. okruh s dělením) uveďme okruh kvaternionů
H = {a + b ■ i + c ■ j + d ■ k; a, b, c, d G R},
se sčítáním po složkách a násobením odvozeným ze základních relací
i2=ß = k2
U
-ji = k,    jk = —kj = i,     ki = —ik = j.
□     s
Obor integrity vs. těleso
Každý konečný obor integrity je těleso.
Dokazuje se prostřednictvím homomorfismu f : R —> R, f (x) = ax (je to injekce, proto surjekce, proto je R těleso (rozmyslete!).       D
□     s
Obor integrity vs. těleso
Každý konečný obor integrity je těleso.
Dokazuje se prostřednictvím homomorfismu f : R —> R, f (x) = ax
(je to injekce, proto surjekce, proto je R těleso (rozmyslete!).       D
^--------                                     -
A co obráceně? Samozřejmě je každé těleso oborem integrity.
□     s
Obor integrity vs. těleso
Každý konečný obor integrity je těleso.
Dokazuje se prostřednictvím homomorfismu f : R —> R, f (x) = ax
(je to injekce, proto surjekce, proto je R těleso (rozmyslete!).       D
^--------                                     -
A co obráceně? Samozřejmě je každé těleso oborem integrity.
Příklad
Zřejmě je např. Z obor integrity, který není těleso.
□       s
Polynomem rozumíme jakýkoliv konečný výraz, který lze poskládat ze známých konstantních prvků R a jedné neznámé proměnné pomocí operací sčítání a násobení:
Polynomy
Polynomem rozumíme jakýkoliv konečný v<jkzt, který lze poskládat ze známých konstantních prvků R a jedné neznámé proměnné pomocí operací sčítání a násobení:
Definice
Nechť R je jakýkoliv (dále vždy) komutativní okruh skalárů. Polynomem nad R rozumíme konečný výraz
f (x) = £ a,x'-
kde a,- G R, i = 0,1,..., k, jsou tzv. koeficienty polynomu. Je-li a k 7^ 0, říkáme, že f (x) má stupeň k, píšeme stf = k. Nulový polynom nemá stupeň, polynomy stupně nula jsou právě nenulové prvky v R, kterým říkáme konstantní polynomy.
Polynomy
Polynomem rozumíme jakýkoliv konečný v<jkzt, který lze poskládat ze známých konstantních prvků R a jedné neznámé proměnné pomocí operací sčítání a násobení:
Definice
Nechť R je jakýkoliv (dále vždy) komutativní okruh skalárů. Polynomem nad R rozumíme konečný výraz
f (x) = £ a,x'-
kde a,- G R, i = 0,1,..., k, jsou tzv. koeficienty polynomu. Je-li a k 7^ 0, říkáme, že f (x) má stupeň k, píšeme stf = k. Nulový polynom nemá stupeň, polynomy stupně nula jsou právě nenulové prvky v R, kterým říkáme konstantní polynomy. Polynomy f (x) a g{x) jsou stejné, jestliže mají stejné koeficienty. Množinu všech polynomů nad okruhem R budeme značit R[x].
Každý polynom zadáva zobrazení f : R —> R, jehož hodnota vznikne dosazením hodnoty c za nezávislou proměnnou x, tj.
f (c) = a0 + a\c H--------h a^ck.
Všimněme si, že konstantní polynomy odpovídají právě konstantním zobrazením.
□      s       -
Každý polynom zadáva zobrazení f : R —> R, jehož hodnota vznikne dosazením hodnoty c za nezávislou proměnnou x, tj.
f (c) = a0 + a\c H--------h a^ck.
Všimněme si, že konstantní polynomy odpovídají právě konstantním zobrazením.
Kořen polynomu f(x) je takový prvek cg/?, pro který je f(c) = 0 e /?.
□         S
Každý polynom zadává zobrazení f : R —> R, jehož hodnota vznikne dosazením hodnoty c za nezávislou proměnnou x, tj.
f (c) = a0 + a\c H--------h a/tC^.
Všimněme si, že konstantní polynomy odpovídají právě
konstantním zobrazením.
Kořen polynomu f(x) je takový prvek cg/?, pro který je
f(c) = 0 e /?.
Obecně se může stát, že různé polynomy definují stejná zobrazení.
Např. polynom x2 +x G 2^[x] zadává identicky nulové zobrazení.
Obecněji, pro každý konečný okruh R = {ao, a\,..., ai<} zadává
polynom f (x) = (x — 3o)(x — a\)... (x — a^) identicky nulové
zobrazení. Zároveň ale platí tvrzení, které dokážeme zanedlouho:
Jestliže Je R nekonečný okruh, pak dva polynomy f(x) a g{x) nad R Jsou stejné právě tehdy, když Jsou stejná příslušná zobrazení f a
g-
Dva polynomy f (x) = J2j a,x' a g{x) = J2j bjX1 umíme přirozeně také sčítat i násobit:
(f + g)(x) = (*o + bo) + (ai + by)x + (f ■ g)(x) = (a0bo) + ■■■ + (aobi + + ■
■ + (ak + bk)xk + aebo)xe + ...
kde uvažujeme nulové koeficienty všude, kde v původním výrazu pro polynomy nenulové koeficienty nejsou a u sčítání nechť je k maximální ze stupňů f a g.
□      s       -
Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f,g:R—>R, díky vlastnostem skalárů v původním okruhu R.
□      s
Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f,g:R—>R, díky vlastnostem skalárů v původním okruhu R.
Přímo z definice vyplývá, že množina polynomů R[x] nad komutativním okruhem s jedničkou je opět komutativním okruhem s jedničkou, přičemž jedničkou v R[x] je opět jednička 1 v okruhu R vnímaná jako polynom stupně nula.
Lemma
Okruh polynomů nad oborem integrity je opět obor integrity
□       s
Tato definice vskutku odpovídá příslušným operacím sčítání a násobení hodnot zobrazení f,g:R—>R, díky vlastnostem skalárů v původním okruhu R.
Přímo z definice vyplývá, že množina polynomů R[x] nad komutativním okruhem s jedničkou je opět komutativním okruhem s jedničkou, přičemž jedničkou v R[x] je opět jednička 1 v okruhu R vnímaná jako polynom stupně nula.
Lemma
Okruh polynomů nad oborem integrity je opět obor integrity.
Důkaz.
Máme ukázat, že v R[x] mohou být netriviální dělitelé nuly pouze tehdy, jestliže jsou už v R. To je ale zřejmé z definice násobení polynomů. Jsou-li f(x) a g{x) polynomy stupně k a í jako výše, pak koeficient u xk+e v součinu f (x) • g{x) je součin a k ■ bga ten musí být nenulový, pokud nejsou dělitelé nuly v R.                           D
V Matematice III jsme pracovali s formálními mocninnými řadami a neformálně jsme prohlásili, že s nimi můžeme provádět analogické operace jako s polynomy. Nyní toto tvrzení můžeme zasadit do formálního algebraického kontextu:
Formální mocninné řady
V Matematice III jsme pracovali s formálními mocninnými řadami a neformálně jsme prohlásili, že s nimi můžeme provádět analogické operace jako s polynomy. Nyní toto tvrzení můžeme zasadit do formálního algebraického kontextu:
Definice
Nechť R je okruh skalárů. Formální mocninou řadou nad R rozumíme (obecně nekonečný) formální výraz f(x) = Yľh=oaix' kde a-, G R, i = 0,1,..., jsou tzv. koeficienty řady.
□     s
Formální mocninné řady
V Matematice III jsme pracovali s formálními mocninnými řadami a neformálně jsme prohlásili, že s nimi můžeme provádět analogické operace jako s polynomy. Nyní toto tvrzení můžeme zasadit do formálního algebraického kontextu:
Definice
Nechť R je okruh skalárů. Formální mocninou řadou nad R rozumíme (obecně nekonečný) formální výraz f(x) = Yľh=o3ix'i kde a-, G R, i = 0,1,..., jsou tzv. koeficienty řady.
Snadno se ukáže, že s dříve definovanými operacemi sčítání a násobení tvoří formální mocnině řady okruh, který značíme R[[x]] (a jehož je R[x] podokruhem). Sami si zkuste rozmyslet, které prvky tohoto okruhu jsou invertibilní.
□      s
oooooooooooo
Plán přednášky
<ruhy a tělesa
O Dělitelnost a nerozložitelnost
□         g         -         =         ^      -00*0
Směřujeme nyní ke zobecnění rozkladů polynomů nad číselnými obory a k tomu nejprve potřebujeme ujasnit, co je dělitelnost v základním okruhu R samotném. Uvažujme proto nějaký pevně zvolený obor integrity Z?1, třeba celá čísla Z nebo okruh Zp s prvočíselným p. V R definujeme dělitelnost analogicky jako to známe ze Z: b\a  <š=>  3c G R : a = b ■ c .
^bor integrity proto, aby bylo jednoznačné delení!
Směřujeme nyní ke zobecnění rozkladů polynomů nad číselnými obory a k tomu nejprve potřebujeme ujasnit, co je dělitelnost v základním okruhu R samotném. Uvažujme proto nějaký pevně zvolený obor integrity Z?1, třeba celá čísla Z nebo okruh Zp s prvočíselným p. V R definujeme dělitelnost analogicky jako to známe ze Z: b\a  <š=>  3c G R : a = b ■ c .
Pak platí:
•  je-li a\b a zároveň b\c pak také a|c;
•  a\b a zároveň a\c pak také a\(ctb + ßc) pro všechny ct,ß<ER;
•  a\0 pro všechny a G R (je totiž a ■ 0 = 0);
•  každý prvek a G R je dělitelný všemi jednotkami e G /? a jejich násobky a • e (jak přímo plyne z existence e_1)
^bor integrity proto, aby bylo jednoznačné dělení!
Řekneme, že prvek a G R je nerozložitelný (ireducibilní), jestliže • je nenulový a není jednotkou (tj. a\ 1),
□      s       -
Řekneme, že prvek a G R je nerozložitelný (ireducibilní), jestliže
•  je nenulový a není jednotkou (tj. a\ 1),
•  je dělitelný pouze jednotkami e e R a čísly a • e (tzv. čísla asociovaná s a - tj. taková b <E R, že a\b a b\a).
□     s
Řekneme, že prvek a G R je nerozložitelný (ireducibilní), jestliže
•  je nenulový a není jednotkou (tj. a\ 1),
•  je dělitelný pouze jednotkami e e R a čísly a • e (tzv. čísla asociovaná s a - tj. taková b <E R, že a\b a b\a).
□     s
Řekneme, že prvek a G R je nerozložitelný (ireducibilní), jestliže
•  je nenulový a není jednotkou (tj. a\ 1),
•  je dělitelný pouze jednotkami e G R a čísly a • e (tzv. čísla asociovaná s a - tj. taková b <E R, že a\b a b\a).
Řekneme, že okruh R je obor integrity s jednoznačným rozkladem, jestliže platí:
•  pro každý nenulový prvek a G R, který není jednotkou, existují nerozložitelné a\,..., ar G R takové, že a = a\ ■ a-i... ar
•  jsou-li prvky a\,..., ar a b\,..., bs nerozložitelné, nejsou mezi nimi žádné jednotky a ai32 ... ar = b\bi ■ ■ ■ bs, pak je r = s a ve vhodném přeuspořádání platí ay = e,-6/ pro vhodné jednotky e,-.
□      s
Příklad
O Z, R[x] jsou obory integrity s jednoznačným rozkladem (ireducibilní prvky v Z jsou prvočísla a čísla k nim opačná).
□      s
Příklad
O Z, R[x] jsou obory integrity s jednoznačným rozkladem (ireducibilní prvky v Z jsou prvočísla a čísla k nim opačná).
9 Každé těleso je obor integrity s jednoznačným rozkladem (kde každý nenulový prvek je jednotka).
□     s
Příklad
Z, R[x] jsou obory integrity s jednoznačným rozkladem (ireducibilní prvky v Z jsou prvočísla a čísla k nim opačná).
Každé těleso je obor integrity s jednoznačným rozkladem (kde každý nenulový prvek je jednotka).
Např. v okruhu R[\/—5] = {a + b\f—b; a, b e M} existují dva různé rozklady čísla 6 na nerozložitelné prvky:
6 = 2 • 3 = (1 - ^5)(1 + V^5).a
aTo, že uvedené prvky jsou ireducibilní a že nejsou asociované, je ale třeba trochu "odpracovat".
□       s
Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme.
Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme.
Lemma (Věta o dělení se zbytkem pro polynomy)
Nechi R je komutativní okruh bez dělitelů nuly a f,g G R[x] polynomy g ^ 0. Pak existuje a G R, a 7^ 0, a polynomy q a r splňující af = qg + r, kde r = 0 nebo str < st g. Je-Ii navíc R těleso neboje aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně.
□      s
Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme.
Lemma (Věta o dělení se zbytkem pro polynomy)
Nechi R je komutativní okruh bez dělitelů nuly a f,g G R[x] polynomy g ^ 0. Pak existuje a G R, a 7^ 0, a polynomy q a r splňující af = qg + r, kde r = 0 nebo str < st g. Je-Ii navíc R těleso neboje aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně.
Poznámka
Toto tvrzení je možné aplikovat i obecněji (viz Euklidovské okruhy), je ale třeba správně definovat, jak budeme porovnávat prvky.