Opakování: zbytkové třídy Definice. Nechť m ∈ N. Pro libovolné a ∈ Z definujeme množinu [a]m = {a + k · m; k ∈ Z}, kterou nazýváme zbytková třída modulo m obsahující a. Poznámka. Množina [a]m se skládá z právě těch celých čísel, která mají stejný zbytek po dělení číslem m jako číslo a. Věta. Pro libovolná a, b ∈ Z, m ∈ N nastává [a]m = [b]m právě tehdy, když m | a − b, tj. právě když a ≡ b (mod m). Označení. Množinu všech zbytkových tříd modulo m ∈ N značíme Zm. Je tedy Zm = [0]m, [1]m, [2]m, . . . , [m − 1]m . Opakování: operace na množině Zm Věta. Nechť m ∈ N, a, b, c, d ∈ Z jsou libovolná. Jestliže platí [a]m = [c]m, [b]m = [d]m, pak také [a + b]m = [c + d]m, [a · b]m = [c · d]m. Důsledek. Nechť m ∈ N. Vztahy [a]m + [b]m = [a + b]m, [a]m · [b]m = [a · b]m pro libovolná a, b ∈ Z definují operace + a · na množině Zm. Tato množina s těmito operacemi tvoří komutativní okruh (Zm, +, ·). Tento okruh je obor integrity, právě tehdy, když je tento okruh těleso, což nastává právě tehdy, když je m prvočíslo. Zbytkové třídy polynomů nad okruhem zbytkových tříd Definice. Nechť m ∈ Z, m > 1. Zvolme pevně normovaný polynom f (x) ∈ Zm[x], st(f (x)) > 1. Pro libovolný polynom g(x) ∈ Zm[x] definujeme množinu [g(x)]f (x) = g(x) + k(x) · f (x); k(x) ∈ Zm[x] , kterou nazveme zbytková třída okruhu polynomů Zm[x] modulo f (x) obsahující polynom g(x). Věta. Nechť m ∈ Z, m > 1 a polynom f (x) ∈ Zm[x] je normovaný, st(f (x)) > 1. Pro libovolný polynom g(x) ∈ Zm[x] se množina [g(x)]f (x) skládá z právě těch polynomů ze Zm[x], které mají stejný zbytek po dělení polynomem f (x) jako polynom g(x) (polynomem f (x) můžeme dělit se zbytkem díky tomu, že je normovaný). Pro libovolné polynomy g(x), h(x) ∈ Zm[x] nastává [g(x)]f (x) = [h(x)]f (x) právě tehdy, když f (x) | g(x) − h(x). Množina zbytkových tříd polynomů Označení. Množinu všech zbytkových tříd okruhu polynomů Zm[x] modulo f (x) ∈ Zm[x] značíme Zm[x]/(f (x)). Je tedy Zm[x]/(f (x)) = [g(x)]f (x) | g(x) ∈ Zm[x] . Poznámka. Uvedené označení je speciální případ označení obecnější konstrukce (tzv. faktorizace okruhů podle ideálu), použili jsme jej, protože označení analogické označení okruhu zbytkových tříd (tedy označení (Zm[x])f (x) nebo něco podobného) se v této situaci nepoužívá. Zřejmě pro každou zbytkovou třídu platí, že společný zbytek jejích prvků po dělení polynomem f (x) je také jejím prvkem, proto Zm[x]/(f (x)) = [g(x)]f (x) | g(x) ∈ Zm[x], st(g(x)) < st(f (x)) . Protože různé zbytky patří do různých tříd, má množina Zm[x]/(f (x)) právě mst(f (x)) prvků. Příklad: množina Z2[x]/(x2 + x + [1]2) Příklad. Zvolme m = 2, f (x) = x2 + x + [1]2 ∈ Z2[x]. Zbytek po dělení kvadratickým polynomem je polynom stupně menšího než dva, proto máme právě čtyři možné zbytky, totiž polynomy [0]2, [1]2, x, x + [1]2. Proto je množina Z2[x]/(x2 +x+[1]2) = [0]2 f (x) , [1]2 f (x) , x f (x) , x+[1]2 f (x) čtyřprvková. Tento přesný zápis je poněkud nepřehledný, proto pro zjednodušení zápisu budeme dále tyto zbytky psát jako 0, 1, x, x + 1 a polynom f (x) jako x2 + x + 1. Tedy Z2[x]/(x2 +x+1) = [0]x2+x+1, [1]x2+x+1, [x]x2+x+1, [x+1]x2+x+1 . Operace na množině Zm[x]/(f (x)) Věta. Nechť m ∈ Z, m > 1 a polynom f (x) ∈ Zm[x] je normovaný, st(f (x)) > 1. Jestliže pro polynomy g(x), h(x), r(x), s(x) ∈ Zm[x] platí [g(x)]f (x) = [r(x)]f (x), [h(x)]f (x) = [s(x)]f (x), pak také platí [g(x) + h(x)]f (x) = [r(x) + s(x)]f (x), [g(x) · h(x)]f (x) = [r(x) · s(x)]f (x). Důsledek. Nechť m ∈ Z, m > 1 a polynom f (x) ∈ Zm[x] je normovaný, st(f (x)) > 1. Vztahy [g(x)]f (x) + [h(x)]f (x) = [g(x) + h(x)]f (x), [g(x)]f (x) · [h(x)]f (x) = [g(x) · h(x)]f (x) pro libovolné polynomy g(x), h(x) ∈ Zm[x] definují operace + a · na množině Zm[x]/(f (x)). Tato množina s těmito operacemi tvoří netriviální komutativní okruh (Zm[x]/(f (x)), +, ·). Tento okruh je obor integrity, právě tehdy, když je tento okruh těleso, což nastává právě tehdy, když je m prvočíslo a současně polynom f (x) je ireducibilní nad Zm. Důkaz. Z předchozí věty plyne korektnost uvedených definic obou operací (tedy nezávislost výsledku operace na zvolených reprezentantech). Každý z axiomů komutativního okruhu pro novou algebraickou strukturu (Zm[x]/(f (x)), +, ·) plyne z platnosti tohoto axiomu pro komutativní okruh Zm[x], ukažme si to například na komutativitě sčítání: pro libovolné polynomy g(x), h(x) ∈ Zm[x] platí [g(x)]f (x) + [h(x)]f (x) = [g(x) + h(x)]f (x) = = [h(x) + g(x)]f (x) = [h(x)]f (x) + [g(x)]f (x). Nulou (resp. jedničkou) v novém okruhu je třída obsahující konstantní polynom [0]m (resp. [1]m). Třída [−g(x)]f (x) je opačným prvkem ke třídě [g(x)]f (x). Je tedy Zm[x]/(f (x)) netriviální komutativní okruh. Protože je konečný, je to obor integrity, právě když je to těleso. Jestliže m není prvočíslo, existují r, s ∈ Z, r > 1, s > 1, rs = m, a náš okruh obsahuje dělitele nuly [r]m, [s]m, protože [r]m = [0]m = [s]m, [r]m · [s]m = [m]m = [0]m. Nechť je dále m prvočíslo. Jestliže polynom f (x) není ireducibilní nad Zm, existují r(x), s(x) ∈ Zm[x], st(r(x)) > 0, st(s(x)) > 0, r(x) · s(x) = f (x), a náš okruh obsahuje dělitele nuly [r(x)]f (x), [s(x)]f (x), protože st(s(x)) < st(f (x)), st(r(x)) < st(f (x)), a tedy tyto prvky jsou nenulové, přitom [r(x)]f (x) · [s(x)]f (x) = [f (x)]f (x) = [[0]m]f (x), což je nula našeho okruhu. Nechť je dále polynom f (x) ireducibilní nad Zm. Zvolme libovolně nenulový prvek [g(x)]f (x) ∈ Zm[x]/(f (x)). Tedy g(x) ∈ Zm[x] není dělitelný polynomem f (x). Protože Zm je těleso, z ireducibibity f (x) plyne (g(x), f (x)) = [1]m a z Bezoutovy rovnosti dostáváme existenci polynomů a(x), b(x) ∈ Zm[x] takových, že a(x) · g(x) + b(x) · f (x) = [1]m. Pak [[1]m]f (x) = [a(x) · g(x) + b(x) · f (x)]f (x) = = [a(x)]f (x) · [g(x)]f (x) + [b(x)]f (x) · [f (x)]f (x) = = [a(x)]f (x) · [g(x)]f (x), a tedy [a(x)]f (x) je inverzní prvek k prvku [g(x)]f (x). Dostali jsme, že Zm[x]/(f (x)) je těleso. Příklad: čtyřprvkové těleso Z2[x]/(x2 + x + [1]2) Příklad. Opět zvolme m = 2, f (x) = x2 + x + [1]2 ∈ Z2[x]. Víme, že Z2[x]/(x2 +x+1) = [0]x2+x+1, [1]x2+x+1, [x]x2+x+1, [x+1]x2+x+1 . Operace na této množině provádíme pomocí reprezentantů, pokud při násobení reprezentantů dostaneme polynom příliš vysokého stupně, nahradíme jej zbytkem po dělení polynomem x2 + x + 1, například [x]x2+x+1 + [x + 1]x2+x+1 = [x + (x + 1)]x2+x+1 = [1]x2+x+1, [x]x2+x+1 · [x + 1]x2+x+1 = [x · (x + 1)]x2+x+1 = = [x2 + x]x2+x+1 = [1]x2+x+1, kde poslední rovnost jsme dostali z toho, že zbytek po dělení polynomu x2 + x polynomem x2 + x + 1 je 1. Jiný příklad: devítiprvkové těleso Příklad. Sestrojme devítiprvkové těleso. K tomu potřebujeme normovaný ireducibilní kvadratický polynom f (x) ∈ Z3[x]. Pro kvadratické (a kubické) polynomy platí, že jsou ireducibilní nad Zm, právě když nejsou dělitelné lineárním polynomem ze Zm[x], tj. právě když nemají kořen v Zm. Snadno se ověří, že tuto podmínku splňuje polynom x2 + 1 ∈ Z3[x] (stejně jako dříve budeme používat tento přehlednější zápis místo přesnějšího x2 + [1]3). Zřejmě Z3[x]/(x2 + 1) = {[0]x2+1, [1]x2+1, [2]x2+1, [x]x2+1, [x + 1]x2+1, [x + 2]x2+1, [2x]x2+1, [2x + 1]x2+1, [2x + 2]x2+1}. Ukažme si, že důkaz existence inverzního prvku na konci důkazu předchozí věty byl konstruktivní a dává nám užitečný algoritmus: spočítejme inverzní prvek [2x + 1]−1 x2+1 k prvku [2x + 1]x2+1. Nejprve pomocí Eukleidova algoritmu najdeme největší společný dělitel polynomů x2 + 1, 2x + 1 ∈ Z3[x], přestože předem víme, že jsou nesoudělné. Největší společný dělitel najdeme v tomto případě jediným dělením: x2 + 1 = (2x + 1)(2x − 1) + 2, kde jsme užili 4x2 = x2, neboť počítáme v Z3[x], a tedy 1 = −(x2 + 1) + (2x + 1)(2x − 1), proto [2x + 1]−1 x2+1 = [2x − 1]x2+1. Pro jistotu si udělejme zkoušku: skutečně platí [2x + 1]x2+1 · [2x − 1]x2+1 = [4x2 − 1]x2+1 = [x2 − 1]x2+1 = = [−2]x2+1 = [1]x2+1.