[1]
BI-LIN, grupy, 17, P. Olsˇa´k
[2]
Rea´lna´ cˇı´sla, inspirace
Grupy, teˇlesa
Na mnozˇineˇ R rea´lny´ch cˇ´ısel ma´me operaci +. Prˇitom platı´:
• teˇleso: mnozˇina se dveˇma „rozumny´mi“ operacemi
• x + (y + z) = (x + y) + z . . . (asociativnı´ za´kon), • existuje prvek 0 ∈ R takovy´, zˇe 0 + x = x + 0 = x ∀x ∈ R . . . (existence neutra´lnı´ho prvku), • ∀x ∈ R existuje opacˇny´ prvek y ∈ R tak, zˇe x + y = y + x = 0 . . . (existence opacˇne´ho prvku, znacˇ´ıme y = −x), • x + y = y + x . . . (komutativnı´ za´kon).
• prˇ´ıklady teˇles, vlastnosti, charakteristika teˇlesa
Na mnozˇineˇ R ma´me take´ operaci ⋅, ktera´ splnˇuje:
• linea´rnı´ prostor nad teˇlesem
• x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z . . . (asociativnı´ za´kon), • existuje prvek 1 ∈ R takovy´, zˇe 1 ⋅ x = x ⋅ 1 = x ∀x ∈ R . . . (existence jednotkove´ho prvku), • ∀x ∈ R, x 6= 0 existuje prvek y ∈ R tak, zˇe x ⋅ y = y ⋅ x = 1 . . . (existence inverznı´ho prvku, znacˇ´ıme y = x−1), • x ⋅ y = y ⋅ x . . . (komutativnı´ za´kon).
• grupa: mnozˇina s jednou „rozumnou“ operacı´ • prˇ´ıklady grup, vlastnosti
• polynomy nad teˇlesem • polynomy modulo polynom
a) grupy, 17, b) P. Olsˇa´k, FEL CˇVUT, c) P. Olsˇa´k 2010, d) BI-LIN, e) L, f) 2009/2010, g)
L
. Viz p. d. 4/2010
BI-LIN, grupy, 17, P. Olsˇa´k
[3]
BI-LIN, grupy, 17, P. Olsˇa´k
Mnozˇina s jednou operacı´: grupoid, grupa
Prˇı´klady
Definice: Prˇedpokla´dejme mnozˇinu G a na nı´ operaci . Da´le uvazˇujme vlastnosti:
• R s operacı´ + je komutativnı´ grupa.
(1) x (y z) = (x y) z ∀x, y, z ∈ G . . . (asociativnı´ za´kon),
[4]
• R s operacı´ ⋅ je pologrupa, R \ {0} je komutativnı´ grupa. • Q, Z s operacı´ + jsou komutativnı´ grupy (podgrupy grupy R s +).
(2) existuje prvek e ∈ G takovy´, zˇe e x = x e = x ∀x ∈ G . . . (existence neutra´lnı´ho/jednotkove´ho prvku),
• Z \ {0} s operacı´ ⋅ nenı´ grupa (je to pologrupa).
(3) ∀x ∈ G existuje prvek y ∈ G tak, zˇe x y = y x = e . . . (existence opacˇne´ho/inverznı´ho prvku),
• Mnozˇina regula´rnı´ch matic s maticovy´m na´sobenı´m je grupa.
• Mnozˇina {e} s operacı´ , pro kterou e e = e, je grupa.
(4) x y = y x ∀x, y ∈ G . . . (komutativnı´ za´kon).
• Mnozˇina ctvercovy´ch matic s na´sobenı´m je pologrupa.
• Mnozˇina G s operacı´ se nazy´va´ grupoid.
• Mnozˇina funkcı´ R → R prosty´ch a na s operacı´ skla´da´nı´ je grupa.
• Grupoid, kde platı´ asociativnı´ za´kon (1), se nazy´va´ pologrupa.
• Mnozˇina bijektivnı´ch zobrazenı´ M → M s op. skla´da´nı´ je grupa.
• Pologrupa s vlastnostmi (2) a (3) se nazy´va´ grupa.
• Mnozˇina permutacı´ s operacı´ skla´da´nı´ je grupa
• Grupa, kde platı´ komutativnı´ za´kon (4), je komutativnı´ grupa.
• Mnozˇina {0, 1, . . . , m − 1} s operacı´ „+ modulo m“ je grupa.
BI-LIN, grupy, 17, P. Olsˇa´k
[5]
BI-LIN, grupy, 17, P. Olsˇa´k
[6]
Terminologie: jednotkovy´/neutra´lnı´ prvek
Za´kladnı´ vlastnosti grupy
Operace komutativnı´ grupy by´va´ neˇkdy oznacˇena symbolem +. V takove´m prˇ´ıpadeˇ prvek e z vlastnosti (2) grupy se nazy´va´ neutra´lnı´ prvek a prvek y z vlastnosti (3) se nazy´va´ opacˇny´ prvek.
• Neutra´lnı´/jednotkovy´ prvek je v grupeˇ jediny´. Kdyby byly dva e, f , pak e = e f = f , takzˇe nemohou by´t ru˚zne´.
Neutra´lnı´ prvek se v tomto prˇ´ıpadeˇ znacˇ´ı symbolem 0 a opacˇny´ prvek k prvku x se znacˇ´ı −x. Operaci a + (−b) znacˇ´ıme strucˇneˇji a − b a rˇ´ıka´me ji odecˇ´ıta´nı´.
• Opacˇny´/inverznı´ prvek existuje ke kazˇde´mu prvku x ∈ G jediny´. Kdyby existovaly y1, y2 tak, zˇe y1 x = e, x y2 = e, pak y1 = y1 e = y1 (x y2) = (y1 x) y2 = e y2 = y2.
Je-li operace grupy oznacˇena symbolem ⋅ (kra´t), pak prvku e z vlastnosti (2) grupy rˇ´ıka´me jednotkovy´ prvek a prvku y z vlastnosti (3) rˇ´ıka´me inverznı´ prvek.
• Pologrupa G je grupou pra´veˇ kdyzˇ pro kazˇde´ a, b ∈ G existujı´ rˇesˇenı´ rovnic a x = b, y a = b.
Jednotkovy´ prvek v takove´m prˇ´ıpadeˇ znacˇ´ıme symbolem 1 a inverznı´ prvek k prvku x znacˇ´ıme x−1. Je-li grupa komutativnı´, pak operaci a ⋅ b−1 znacˇ´ıme strucˇneˇji a/b a rˇ´ıka´me ji deˇlenı´.
Na´znak du˚kazu: Je-li G grupa, pak x = a−1 b a y = b a−1 jsou rˇesˇenı´ uvedeny´ch rovnic. Umı´me-li rˇesˇit tyto rovnice, pak jednotkovy´ prvek e je rˇesˇenı´ rovnice a e = a (je trˇeba uka´zat, zˇe to neza´visı´ na volbeˇ a). Da´le inverznı´ prvek k a je rˇesˇenı´ a x = e (je trˇeba uka´zat, zˇe je to tote´zˇ, jako rˇesˇenı´ rovnice y a = e).
BI-LIN, grupy, 17, P. Olsˇa´k
[7]
BI-LIN, grupy, 17, P. Olsˇa´k
[8]
Vlastnosti inverznı´ch prvku ˚ grupy
Mocnina
• Jednotkovy´ prvek e ma´ inverznı´ prvek e (je inverznı´ sa´m sobeˇ). Skutecˇneˇ: e = e e.
Je-li a ∈ G, pak symbolem ak oznacˇme prvek a a · · · a (k-kra´t).
• Je-li a−1 invernzı´ prvek k a, je-li da´le b−1 inverznı´ prvek k b, pak inverznı´ prvek k a b je tvaru b−1 a−1. Skutecˇneˇ: (b−1 a−1 ) (a b) = b−1 (a−1 a) b = b−1 e b = b−1 b = e, (a b) (b−1 a−1 ) = a (b b−1) a−1 = a e a−1 = a a−1 = e. −1
−1
• Je-li a inverznı´ k a, pak a je inverznı´ k a . Skutecˇneˇ: a−1 a = a a−1 = e.
Tvrzenı´: Je-li G konecˇna´ komutativnı´ grupa s n prvky, pak pro kazˇde´ a ∈ G je an = e. Du˚kaz: Oznacˇme G = {g1, g2, . . . , gn} a zvolme a ∈ G. Uka´zˇeme, zˇe {g1, g2, . . . , gn} = {a g1, a g2 , . . . , a gn}. Zobrazenı´, ktere´ prˇirˇadı´ prvku gi prvek a gi je proste´, protozˇe, pokud a gi = a gj , pak po aplikaci a−1 zleva ma´me gi = gj . Uvedene´ mnozˇiny jsou tedy stejneˇ pocˇetne´ a tedy stejne´ a majı´ tedy stejny´ soucˇin vsˇech prvku˚: a g1 a g2 · · · a gn = g1 g2 · · · gn = u Dı´ky komutativnı´mu za´konu se rovnost da´ prˇepsat na an u = u a dokazovana´ rovnost plyne aplikacı´ u−1 na obeˇ strany rovnosti.
BI-LIN, grupy, 17, P. Olsˇa´k
[9]
BI-LIN, grupy, 17, P. Olsˇa´k
[10]
Podgrupy
Vlastnosti pologrupy „kra´t modulo m“
Podgrupa P je podmnozˇina grupy G se stejnou operacı´, ktera´ je sama grupou. Tj. P musı´ mı´t (stejny´) jednotkovy´ prvek a kazˇdy´ prvek z P musı´ mı´t inverzi v P.
Prˇedpokla´dejme mnozˇinu {0, 1, 2, . . . , m−1} s operacı´ „kra´t modulo m“, tj. a ◦ b = a ⋅ b pro a ⋅ b < m, jinak a ◦ b je zbytek po deˇlenı´ cˇ´ısla a ⋅ b cˇ´ıslem m. Je to pologrupa. Tato pologrupa ma´ jednotkovy´ prvek: 1.
Prˇı´klady:
Tvrzenı´: je-li m slozˇene´, tj. m = n1 ⋅ n2 , (n1 6= 1, n2 6= 1) pak cˇ´ıslo n1 nema´ inverznı´ prvek.
• Q a Z je podgrupa grupy R s operacı´ +, • Q \ {0} je podgrupa grupy R \ {0} s operacı´ ⋅, • symetricke´ matice tvorˇ´ı podgrupu cˇtvercovy´ch matic s operacı´ +, • matice s det = 1 tvorˇ´ı podgrupu regula´rnı´ch matic s operacı´ ⋅,
Du˚kaz: v ◦ n1 = z, tj. vn1 = kn1 n2 + z, tj. z = n1 (v − kn2 ), takzˇe z musı´ by´t na´sobek n1 a nemu˚zˇe tedy by´t roven jedne´. Tvrzenı´: je-li m prvocˇ´ıslo, pak mnozˇina {1, 2, . . . , m−1} s operacı´ ◦ je grupa.
• Suda´ cˇ´ısla tvorˇ´ı podgrupu Z s operacı´ +,
Doka´zˇeme*, zˇe kazˇdy´ nenulovy´ prvek a ma´ inverzi. Platı´ totizˇ, zˇe {a, 2 ◦ a, . . . , (m − 1) ◦ a} = {1, · · · , m − 1}. Du˚vod: pro k1 6= k2 je a ◦ k1 6= a ◦ k2 , protozˇe z a (k1 − k2 ) = km plyne k1 − k2 = k′ m (je a nesoudeˇlne´ s m). Protozˇe 0 ≤ k1 − k2 < m, musı´ k′ = 0, takzˇe k1 = k2 .
• Kladna´ cˇ´ısla tvorˇ´ı podgrupu grupy R s operacı´ ⋅.
BI-LIN, grupy, 17, P. Olsˇa´k
[11]
BI-LIN, grupy, 17, P. Olsˇa´k
[12]
Mala´ Fermatova veˇta
Mnozˇina se dveˇma operacemi: okruh, teˇleso
Necht’ p je prvocˇ´ıslo, necht’ a je prˇirozene´ cˇ´ıslo, a < p. Pak
Definice: Okruh je mnozˇina T s operacemi + a ⋅, pro ktere´ platı´:
a
p−1
= 1 (modulo p).
Du˚kaz: stacˇ´ı si uveˇdomit, zˇe grupa {1, 2, . . . , p − 1} s operacı´ „kra´t modulo p“ ma´ p − 1 prvku˚ a pouzˇ´ıt veˇtu ze stra´nky [8].
(1) T s operacı´ + je komutativnı´ grupa (neutra´lnı´ prvek znacˇ´ıme 0), (2) T s operacı´ ⋅ je pologrupa, (3) ∀ x, y, z ∈ T platı´ x ⋅ (y + z) = (x ⋅ y) + (x ⋅ z), (y + z) ⋅ x = (y ⋅ x) + (z ⋅ x). . . . (distributivnı´ za´kon). Definice: Teˇleso je mnozˇina T s operacemi + a ⋅, pro ktere´ platı´: (1) T s operacı´ + je komutativnı´ grupa (neutra´lnı´ prvek znacˇ´ıme 0), (2) T \ {0} s operacı´ ⋅ je grupa (jednotkovy´ prvek znacˇ´ıme 1), (3) ∀ x, y, z ∈ T platı´ x ⋅ (y + z) = (x ⋅ y) + (x ⋅ z), (y + z) ⋅ x = (y ⋅ x) + (z ⋅ x). . . . (distributivnı´ za´kon). Pozorova´nı´: Kazˇde´ teˇleso musı´ mı´t asponˇ dva prvky: 0 a 1.
BI-LIN, grupy, 17, P. Olsˇa´k
[13]
BI-LIN, grupy, 17, P. Olsˇa´k
Varianty okruhu ˚ a teˇles
Prˇı´klady
Prˇedpokla´dejme mnozˇinu T s vlastnostmi (1) a (3).
• Mnozˇina rea´lny´ch cˇ´ısel s operacemi + a ⋅ tvorˇ´ı teˇleso.
• Je-li T s operacı´ ⋅ komutativnı´ pologrupa, pak T se nazy´va´ komutativnı´ okruh.
• Mnozˇiny Q a C s operacemi + a ⋅ jsou take´ teˇlesa.
• Je-li T s operacı´ ⋅ pologrupa a ma´-li jednotkovy´ prvek, pak T se nazy´va´ okruh s jednotkou. • Je-li T s operacı´ ⋅ komutativnı´ pologrupa a ma´-li jednotkovy´ prvek, pak T se nazy´va´ komutativnı´ okruh s jednotkou. • Je-li T \ {0} s operacı´ ⋅ komutativnı´ grupa, pak T se nazy´va´ komutativnı´ teˇleso. Pozna´mcˇicˇka: prˇ´ıklad nekomutativnı´ho teˇlesa (kvaterniony) pro nedostatek mı´sta vynecha´me. Vsˇechna ostatnı´ teˇlesa, o ktery´ch budeme mluvit, jsou komutativnı´ teˇlesa. Takzˇe slovo „komutativnı´ “ nebudeme v prˇ´ıpadeˇ teˇles nada´le zdu˚raznˇovat.
BI-LIN, grupy, 17, P. Olsˇa´k
[14]
• Mnozˇina Z s operacemi + a ⋅ je to komutativnı´ okruh s jednotkou. • Mnozˇina sudy´ch cely´ch cˇ´ısel s + a ⋅ je komutativnı´ okruh. • Mnozˇina regula´rnı´ch matic s operacemi + a ⋅ nenı´ teˇleso ani okruh, protozˇe soucˇet dvou reg. matic nemusı´ by´t regula´rnı´. • Mnozˇina cˇtvercovy´ch matic (stejne´ho typu) s operacemi + a ⋅ je nekomutativnı´ okruh s jednotkou. Nenı´ to teˇleso. • Mnozˇina {0, 1} s operacemi 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 0, 0 ⋅ a = a ⋅ 0 = 0, 1 ⋅ a = a ⋅ 1 = a, tvorˇ´ı teˇleso. • Mnozˇina {0, 1, . . . , p − 1} s operacemi „+ modulo p“ a „kra´t modulo p“ tvorˇ´ı teˇleso, pra´veˇ kdyzˇ je p prvocˇ´ıslo. Jinak je to okruh.
[15]
BI-LIN, grupy, 17, P. Olsˇa´k
[16]
Konecˇna´ (Galoisova) teˇlesa
Za´kladnı´ vlastnosti teˇlesa
Da´ se uka´zat, zˇe pokud je teˇleso T konecˇne´, pak nasta´va´ jen jedna z na´sledujı´cı´ch mozˇnostı´:
• Pro libovolne´ a, b ∈ T je: a ⋅ b = 0, pra´veˇ kdyzˇ a = 0 nebo b = 0. Du˚kaz: Necht’ a 6= 0 a b 6= 0. Pak a ⋅ b 6= 0 z vlastnosti (2) definice ´ NO a = 0, uka´zˇeme, zˇe 0 ⋅ b = 0. Platı´: teˇlesa. Obra´ceneˇ: BU
• T = {0, 1, 2, . . . , p − 1} s operacı´ „+ modulo p“ a „kra´t modulo p“, kde p je prvocˇ´ıslo. Toto teˇleso se znacˇ´ı Zp a ma´ p prvku˚. • T je mnozˇina vsˇech polynomu˚ nad Zp stupneˇ mensˇ´ıho nezˇ n s operacemi „plus a kra´t modulo ireducibilnı´ polynom stupneˇ n“. Toto teˇleso ma´ pn prvku˚, podrobneˇji se k neˇmu vra´tı´me za chvı´li. Jine´ konecˇne´ teˇleso (azˇ na izomorfismus) neexistuje. Konecˇna´ teˇlesa se neˇkdy znacˇ´ı GF(pn), kde argument informuje o pocˇtu prvku˚ teˇlesa a GF je zkratka pro „Galois field“. Prˇı´klady: neexistuje teˇleso, ktere´ ma´ 6 prvku˚. Existuje ale teˇleso, ktere´ ma´ 8 prvku˚: GF(23 ) nebo 9 prvku˚: GF(32 ). Z5 je teˇleso, ale Z8 nenı´ teˇleso (je to jen okruh).
0 ⋅ b = (0 + 0) ⋅ b = 0 ⋅ b + 0 ⋅ b. Prˇicˇtenı´m − (0 ⋅ b) k obeˇma strana´m rovnosti ma´me 0 = 0 ⋅ b. • Jestlizˇe existuje konecˇny´ pocˇet jednicˇek, ktere´ v soucˇtu dajı´ nulu, je nejmensˇ´ı takovy´ pocˇet prvocˇ´ıslo. Du˚kaz: Nejmensˇ´ı pocˇet jednicˇek, ktere´ dajı´ v soucˇtu nulu, oznacˇ´ım λ . Pro spor budizˇ λ = m ⋅ n, m < λ , n < λ . Pak ! ! m
∑1 1
⋅
n
∑1 1
=
mn
λ
1
1
∑ 1 = ∑1 = 0
takzˇe (dle prˇedchozı´ vlastnosti) musı´ by´t asponˇ jedna za´vorka nulova´. Tj. existuje mensˇ´ı pocˇet jednicˇek, ktere´ majı´ soucˇet nula.
BI-LIN, grupy, 17, P. Olsˇa´k
[17]
BI-LIN, grupy, 17, P. Olsˇa´k
[18]
Charakteristika teˇlesa
Znovu definice linea´rnı´ho prostoru
Definice: Charakteristika teˇlesa λ je nejmensˇ´ı pocˇet jednicˇek, ktere´ dajı´ v soucˇtu nulu. Pokud konecˇny´ pocˇet jednicˇek s touto vlastnostı´ neexistuje, klademe λ = 0.
Definice: Linea´rnı´ prostor nad teˇlesem T je nepra´zdna´ mnozˇina L s operacemi + : L × L → L a ⋅ : T × L → L, ktere´ splnˇujı´ vlastnosti: → (+) L s operacı´ + je komutativnı´ grupa, nulovy´ prvek znacˇ´ıme − o,
Prˇı´klady:
→ → → x ) = (α ⋅ β ) ⋅ − x pro vsˇechna − x ∈ L, α , β ∈ T, (A) α ⋅ (β ⋅ − − → − → − → − → → → x ,− y ∈ L, α ∈ T, (B) α ⋅ ( x + y ) = α ⋅ x + α ⋅ y pro vsˇechna − − → − → − → − → (C) (α + β ) ⋅ x = α ⋅ x + β ⋅ x pro vsˇechna x ∈ L, α , β ∈ T,
• Teˇlesa Q, R, C majı´ charakteristiku λ = 0. • Teˇleso Zp (p prvocˇ´ıslo) ma´ charakteristku λ = p. Pozorova´nı´: z prˇedchozı´ stra´nky vı´me, zˇe charakteristika teˇlesa je rovna prvocˇ´ıslu (je-li konecˇna´).
→ → → (D) 1 ⋅ − x =− x pro vsˇechna − x ∈ L.
Tvrzenı´:
Pozorova´nı´: Pro T = R se definice shoduje s pu˚vodnı´ definicı´ lin. → → → prostoru. Stacˇ´ı oveˇrˇit, zˇe platı´ (7): 0 ⋅ − x =− o pro vsˇechny − x ∈ L:
• Je-li p charakteristika teˇlesa, pak (a + b)p = ap + bp . • V teˇlese Zp dokonce platı´: ap = a (dı´ky male´ Fermatoveˇ veˇteˇ). • V obecne´m teˇlese s charakteristikou p ovsˇem neplatı´ ap = a.
BI-LIN, grupy, 17, P. Olsˇa´k
Aritmeticky´ linea´rnı´ prostor T
→ → → → 0⋅− x = (0 + 0) ⋅ − x =0⋅− x +0⋅− x, → → → k te´to rovnosti prˇicˇteme − (0 ⋅ − x ) a dosta´va´me − o =0⋅− x.
[19]
n
je analogiı´ linea´rnı´ho prostoru Rn . Mnozˇina T n je mnozˇinou vsˇech usporˇa´dany´ch n-tic prvku˚ z teˇlesa T s operacemi scˇ´ıta´nı´ n-tic a na´sobenı´ n-tice skala´rem z T, ktere´ jsou definova´ny takto: (1) (a1, a2 , . . . , an) + (b1 , b2 , . . . , bn ) = (a1 + b1 , a2 + b2 , . . . , an + bn ), (2) α ⋅ (a1, a2, . . . , an) = (α ⋅ a1, α ⋅ a2 , . . . , α ⋅ an). Pozorova´nı´: Tento linea´rnı´ prostor ma´ ba´zi (1, 0, . . . , 0), (0, 1, . . . , 0), . . . , (0, 0, . . . , 1), takzˇe ma´ dimenzi n. Je-li T konecˇne´ teˇleso, ktere´ ma´ m prvku˚, pak celkovy´ pocˇet vektoru˚ v T n je mn. Kazˇdy´ podprostor prostoru T n dimenze k ma´ mk prvku˚, protozˇe existuje mk ru˚zny´ch linea´rnı´ch kombinacı´ ba´ze.
BI-LIN, grupy, 17, P. Olsˇa´k
Prˇı´klad: linea´rnı´ prostor
[20]
Zn2
je linea´rnı´ prostor usporˇa´dany´ch n-tic jednicˇek a nul nad teˇlesem Z2 . Prvky teˇlesa Z2 = {0, 1} scˇ´ıta´me podle pravidla 0 + 0 = 0,
0 + 1 = 1 + 0 = 1,
1+1=0
a vektory (usporˇa´dane´ n-tice) scˇ´ıta´me a na´sobı´me po slozˇka´ch, jako → → → na prˇedchozı´ stra´nce. Jmenoviteˇ pro libovolny´ − u ∈ Zn2 je 1 ⋅ − u =− u → → a0⋅− u =− o . S jiny´mi skala´ry nepracujeme.
BI-LIN, grupy, 17, P. Olsˇa´k
[21]
BI-LIN, grupy, 17, P. Olsˇa´k
Prˇı´klad: soustava linea´rnı´ch rovnic v Z5
Polynom nad komutativnı´m teˇlesem T
Vyrˇesˇ´ıme soustavu linea´rnı´ch rovnic v Z5 s na´sledujı´cı´ rozsˇ´ırˇenou maticı´. V prvnı´ eliminacˇnı´ u´praveˇ jsem secˇetl prvnı´ rˇa´dek s druhy´m a da´le od trˇetı´ho odecˇetl dvojna´sobek prvnı´ho. 2 3 1 1 4 2 3 1 1 4 2 3 1 1 4 3 1 2 2 2 ∼ 0 4 3 3 1 ∼ 0 2 1 4 3
je vzorec
4
3 3
1
1
0
2 1
4
3
0
0 1
0
0
Mnozˇina rˇesˇenı´ prˇidruzˇene´ homogennı´ soustavy M0 = 〈(0, 3, 0, 1)〉 a partikula´rnı´ rˇesˇenı´ je naprˇ. (1, 4, 0, 0). Vsˇechny principy linea´rnı´ algebry (o dimenzı´ch, linea´rnı´ch obalech, ba´zı´ch) zu˚sta´vajı´ v platnosti. Rozdı´l proti lin. prostoru nad R je jen ten, zˇe zde jsou (pod)prostory konecˇne´. Naprˇ. M0 zde ma´ peˇt prvku˚ (vektor je mozˇne´ na´sobit jen cˇ´ısly 0, 1, 2, 3, 4,), takzˇe mnozˇinu rˇesˇenı´ mu˚zˇeme zapsat vy´cˇtem prvku˚:
[22]
anxn + an−1xn−1 + · · · + a1 x + a0 kde ai ∈ T. Tento vzorec vymezuje prˇedpis pro hodnoty zobrazenı´ z T do T (za x dosazujeme prvky z teˇlesa T a dosta´va´me hodnoty polynomu: prvky z teˇlesa T). Rovnost polynomu ˚ : dva polynomy se rovnajı´, kdyzˇ se rovnajı´ jejich odpovı´dajı´cı´ koeficienty (azˇ na prˇ´ıpadne´ prˇebytecˇne´ nulove´ koeficienty s nejvysˇsˇ´ımi indexy). Pozor: rovnost nenı´ zarucˇena rovnostı´ zobrazenı´ T → T. Prˇı´klad: Polynom x2 + 1 nad Z2 odpovı´da´ zobrazenı´ 0 → 1, 1 → 0. Polynom x3 + 1 odpovı´da´ stejne´mu zobrazenı´, ale nenı´ to stejny´ polynom.
M = {(1, 4, 0, 0), (1, 2, 0, 1), (1, 0, 0, 2), (1, 3, 0, 3), (1, 1, 0, 4)}
BI-LIN, grupy, 17, P. Olsˇa´k
[23]
BI-LIN, grupy, 17, P. Olsˇa´k
[24]
Operace s polynomy nad teˇlesem
ˇ a´stecˇny´ podı´l polynomu C ˚
Soucˇet, rozdı´l nebo soucˇin polynomu˚ nad T provedeme jako soucˇet, rozdı´l nebo soucˇin prˇ´ıslusˇny´ch vzorcu˚. Prˇitom prova´dı´me vy´pocˇty s jednotlivy´mi koeficienty polynomu˚ za pouzˇitı´ operacı´ v teˇlese T.
Veˇta: pro kazˇde´ dva polynomy p, q (q nenulovy´) existujı´ jednoznacˇneˇ polynomy r, z tak, zˇe 1) p = r ⋅ q + z, 2) stupenˇ z je mensˇ´ı nezˇ stupenˇ q.
Prˇı´klad: Secˇteme polynomy nad Z5 : (2x3 +4x2+2x+1)+(3x2 +2x) = 2x3 +(4+3)x2 +(2+2)x+1 = 2x3 +2x2+4x+1. Prˇı´klad: Vyna´sobı´me polynomy nad Z5: (2x3 + 4x2 + 2x + 1) ⋅ (3x2 + 2x) = = (2 ⋅ 3)x + (4 ⋅ 3)x + (2 ⋅ 3)x3 + 3x2 + (2 ⋅ 2)x4 + (4 ⋅ 2)x3 + (2 ⋅ 2)x2 + 2x = = x5 + 2x4 + x3 + 3x2 + 4x4 + 3x3 + 4x2 + 2x = = x5 + (2 + 4)x4 + (1 + 3)x3 + (3 + 4)x2 + 2x = = x5 + x4 + 4x3 + 2x2 + 2x 5
4
Algoritmus cˇa´stecˇne´ho deˇlenı´ polynomu polynomem lze pouzˇ´ıt stejneˇ nad libovolny´m teˇlesem. Naucˇili jsme se ho pouzˇ´ıvat pro polynomy nad R a nynı´ jej budeme pouzˇ´ıvat pro polynomy nad libovolny´m teˇlesem. Zaskocˇit na´s mu˚zˇe jen u´kon deˇlenı´ koeficientu a koeficientem b, cozˇ je ale v kazˇde´m komutativnı´m teˇlese proveditelne´ jako a ⋅ b−1.
BI-LIN, grupy, 17, P. Olsˇa´k
[25]
BI-LIN, grupy, 17, P. Olsˇa´k
Prˇı´klad: algoritmus cˇa´stecˇne´ho podı´lu
Operace modulo polynom
Vydeˇlı´me polynomy nad Z5. V tomto prˇ´ıpadeˇ si uveˇdomı´me, zˇe 3−1 = 2, protozˇe 3 ⋅ 2 = 1 modulo 5. Takzˇe naprˇ´ıklad prvnı´ krok algoritmu obsahuje vy´pocˇet 2x3 : 3x2 = (2 ⋅ 3−1) x = (2 ⋅ 2) x = 4x
Srovnejme dveˇ tvrzenı´:
(2x3 + 4x2 + 2x + 1) : (3x2 + 2x) = 4x + 2 − (2x3 + 3x2 )
[26]
• Pro kazˇde´ dveˇ cela´ cˇ´ısla a, b (b nenulove´) existujı´ cela´ cˇ´ısla r, z tak, zˇe a = rb + z, prˇitom 0 ≤ z < b. Cˇ´ıslo z je zbytek po deˇlenı´ a cˇ´ıslem b. • Pro kazˇde´ dva polynomy p, q (q nenulovy´) existujı´ polynomy r, z tak, zˇe p = r ⋅ q + z, prˇitom st z < st q. Polynom z je zbytek po deˇlenı´ p polynomem q.
x2 + 2x + 1 − (x2 + 4x) −2x + 1 Podı´l dany´ch polynomu˚ roven 4x + 2 a zbytek je −2x + 1 = 3x + 1.
Tak jako mu˚zˇeme pro dveˇ cˇ´ısla najı´t zbytek po deˇlenı´, mu˚zˇeme pro dva polynomy najı´t zbytek po deˇlenı´. Je-li da´n nenulovy´ polynom, modul q, pak kazˇdy´ polynom p mu˚zˇeme ztotozˇnit se zbytkem po deˇlenı´ p polynomem q. Oznacˇ´ıme-li z tento zbytek, pak rˇ´ıka´me: p=z
BI-LIN, grupy, 17, P. Olsˇa´k
modulo q.
[27]
BI-LIN, grupy, 17, P. Olsˇa´k
[28]
Okruh polynomu ˚ modulo polynom
Ireducibilnı´ polynom
Zvolme nenulovy´ polynom q stupneˇ n jako modul a prvocˇ´ıslo p. Symbolem Zp [x]/q oznacˇ´ıme mnozˇinu vsˇech polynomu˚ nad teˇlesem Zp, ktera´ ma´ stupenˇ mensˇ´ı nezˇ n. Zavedeme tyto operace:
Polynom q je ireducibilnı´, pra´veˇ kdyzˇ jej nelze rozlozˇit na soucˇin dvou polynomu˚ nizˇsˇ´ıch stupnˇu˚.
• Scˇı´ta´nı´ prvku˚ z Zp[x]/q: provedeme jako obvykle´ scˇ´ıta´nı´ polynomu˚ nad Zp. Stupenˇ soucˇtu je jisteˇ mensˇ´ı nezˇ n, takzˇe lezˇ´ı v Zp [x]/q. Mnozˇina Zp[x]/q s tı´mto scˇ´ıta´nı´m zjevneˇ tvorˇ´ı komutativnı´ grupu. • Na´sobenı´ prvku˚ a Zp [x]/q: provedeme obvykle´ na´sobenı´ polynomu˚ nad Zp . Pokud stupenˇ vy´sledku je veˇtsˇ´ı nebo roven n, provedeme navı´c na vy´sledek operaci „modulo polynom q“. Mnozˇina Zp [x]/q s tı´mto na´sobenı´m je pologrupa. Platı´ distributivnı´ za´kony: tj. mnozˇina Zp [x]/q s uvedeny´mi operacemi je okruh.
Prˇı´klad: Polynom x2 +x+1 nad Z2 je ireducibilnı´, protozˇe kdyby sˇel rozlozˇit na soucˇin polynomu˚ nizˇsˇ´ıch stupnˇu˚, pak je to soucˇin korˇenovy´ch cˇinitelu˚, ale tento polynom v Z2 nema´ korˇeny (vyzkousˇejte postupny´m dosazenı´m cˇ´ısel 0 a 1). Prˇı´klad: Polynom x3 + x + 1 nad Z2 je ireducibilnı´ (ze stejny´ch du˚vodu˚). Prˇı´klad: Polynom x5 + x4 + 1 nad Z2 je reducibilnı´, protozˇe x5 + x4 + 1 = (x3 + x + 1) ⋅ (x2 + x + 1). V prˇ´ıpadeˇ polynomu stupneˇ 4. a vı´ce na´m test existence korˇenu˚ k rozhodnutı´ o ireducibiliteˇ nepomu˚zˇe.
BI-LIN, grupy, 17, P. Olsˇa´k
[29]
BI-LIN, grupy, 17, P. Olsˇa´k
[30]
3
Polynomy modulo ireducibilnı´ polynom
Prˇı´klad: teˇleso Z2[x]/(x + x + 1)
Da´ se uka´zat, zˇe pokud je polynom q ireducibilnı´, pak okruh Zp[x]/q je teˇleso, tj. kazˇdy´ polynom z mnozˇiny Zp[x]/q ma´ prˇi operaci na´sobenı´ inverznı´ polynom.
Modul (x3 + x + 1) je ireducibilnı´. Toto teˇleso obsahuje:
Du˚kaz* se da´ prove´st anoalogicky, jako s cˇ´ısly. Povsˇimneme si te´to podobnosti:
Scˇ´ıta´nı´ prvku˚ prova´dı´me jako scˇ´ıta´nı´ polynomu˚ nad Z2, naprˇ´ıklad:
• p je prvocˇ´ıslo, tj. nelze rozlozˇit na soucˇin mensˇ´ıch cˇ´ısel. • q je ireducibilnı´, tj. nelze rozlozˇit na soucˇin polynomu˚ mensˇ´ıch stupnˇu˚. Je mozˇne´ prˇecˇ´ıst du˚kaz tvrzenı´ ze stra´nky [10] znovu, jen slovo cˇ´ıslo nahradı´me slovem polynom, slovo prvocˇ´ıslo slovem ireducibilnı´ polynom a vy´rok „cˇ´ıslo a je mensˇ´ı nezˇ b“ vy´rokem „stupenˇ polynomu p je mensˇ´ı nezˇ stupenˇ q“.
BI-LIN, grupy, 17, P. Olsˇa´k
[31]
Prˇı´klad: komplexnı´ cˇı´sla Polynom x2 + 1 je nad R ireducibilnı´. Oznacˇme symbolem R[x] vsˇechny polynomy nad R a da´le R[x]/(x2 + 1) bude znacˇit mnozˇinu vsˇech polynomu˚ nejvy´sˇe prvnı´ho stupneˇ s obvyklou operacı´ + a s operacı´ „kra´t modulo polynom x2 + 1“. Takzˇe R[x]/(x2 + 1) = {a + bx; a, b ∈ R} Dva polynomy v R[x]/(x2 + 1) scˇ´ıta´me podle pravidla: (a + bx) + (c + dx) = (a + c) + (b + d)x. Dva polynomy v R[x]/(x2 + 1) na´sobı´me podle pravidla: (a + bx) ⋅ (c + dx) = bdx2 + (ad + bc)x + ac = = (ac − bd) + (ad + bc)x modulo x2 + 1 Nahrazenı´m symbolu x symbolem i shleda´va´me, zˇe teˇleso R[x]/(x2 + 1) je izomorfnı´ s teˇlesem komplexnı´ch cˇ´ısel.
Z2 [x]/x3 + x + 1 = {0, 1, x, x + 1, x2, x2 + 1, x2 + x, x2 + x + 1}
(x + 1) + (x2 + x) = x2 + 1 Na´sobenı´ prvku˚ prova´dı´me jako na´sobenı´ polynomu˚ nad Z2 s prˇ´ıpadnou dodatecˇnou operacı´ „modulo x3 + x + 1“. Naprˇ´ıklad: (x + 1) ⋅ (x2 + x) = x3 + x = 1 modulo (x3 + x + 1) Vidı´me, zˇe prvky x + 1 a x2 + x jsou si vza´jemneˇ inverznı´. Toto je prˇ´ıklad teˇlesa, ktery´ obsahuje 8 prvku˚, je to tedy GF(23 ). • Ma´-li ireducibilnı´ modul q stupenˇ n, je Zp [x]/q = GF(pn).
