\chyph

\hoffset=-1cm \voffset=-1.2cm \hsize=18cm

\ifx\pdfoutput\undefined \else
\pdfpagewidth=21cm
\pdfpageheight=15cm
\fi

\font\logocvut=lev scaled400

\ifx\zkratka\undefined\edef\zkratka{\jobname}\fi
\def\cislo{17}

\headline={\setfonts[/10]\rm
   \ifnum\pageno>1 
   \hfill {\setfonts[/7] BI-LIN, \zkratka, \cislo, P. Olšák \quad}\else
   \firstpage\hfill\fi [\the\pageno]}
\footline={}

\def\firstpage{\vbox to0pt{\kern13.7cm\hbox{%
\setfonts[/8] a) \zkratka, \cislo, b) P. Olšák, FEL ČVUT, c) P. Olšák 2010,
  d) BI-LIN, e) L, f) 2009/2010, g) \lower1pt\hbox{\logocvut L}. 
  Viz p. d. 4/2010
}\vss}}

\input ofs [a35]  %\def\fomenc{CM}  

%\showfonts \end
%\displayfontmessages
\setfonts[NewCentury/17]  \setmath[17/12/8]  
\baselineskip=22pt \normalbaselineskip=\baselineskip

\message{\fontname\tenit}

\medskipamount=9pt
\let\ms=\medskip

\parskip=\medskipamount

\def\n#1\par{\vfill\break}

\def\g#1\par{{\null \vskip-31pt \baselineskip=30pt\setfonts[/23]\bf #1\par}\medskip}
\def\gg#1\par{{\setfonts[/55]\bf #1}\medskip}
\def\hb{\hfil\break}

\def\emerge{{\emergencystretch=2em\par}}

\parindent=0pt

\catcode`\*=13 
\def* {\par \hangindent=15pt \hangafter=1 
   \noindent \hbox to\hangindent {$\bullet$\hss}}

\let\em=\it

\def\C{{\bf C}}
\def\R{{\bf R}}
\def\Q{{\bf Q}}
\def\a{{A}}
\def\A{{\bf A}}
\def\B{{\bf B}}
\def\D{{\bf D}}
\def\E{{\bf E}}
\def\P{{\bf P}}
\def\L{{\bf L}}
\def\U{{\bf U}}
\def\X{{\bf X}}
\def\Z{{\bf Z}}
\def\Circ{\mathbin{\raise.1em\hbox{$\scriptscriptstyle\bigcirc$}}}
\def\ker{\mathop{\rm Ker}}
\def\st{\mathop{\rm St}}
\def\hod{\mathop{\rm hod}}
\def\vecc #1_#2{\vec#1_1, \vec#1_2, \ldots, \vec#1_{#2}}
\def\lob<#1>{\langle #1\rangle}
\def\|{||}

% ===============================================================

\vglue .5cm

\gg Grupy, tělesa

\bigskip\bigskip

* grupa: množina s jednou \uv{rozumnou} operací

* příklady grup, vlastnosti

* těleso: množina se dvěma \uv{rozumnými} operacemi

* příklady těles, vlastnosti,  charakteristika tělesa

* lineární prostor nad tělesem

* polynomy nad tělesem

* polynomy modulo polynom


\n ---------------------------------------------------------------


\g Reálná čísla, inspirace

Na množině $\R$ reálných čísel máme operaci $+$. Přitom platí:

{\medskip\parskip=0pt
* $x+(y+z) = (x+y)+z$ \dots\ (asociativní zákon),
* existuje prvek $0\in\R$ takový, že $0+x = x+0 = x$ \ $\forall x\in\R$\hb
  \dots\ (existence neutrálního prvku),
* $\forall x\in\R$ existuje opačný prvek $y\in\R$ tak, že
  $x+y=y+x=0$\hb
  \dots\ (existence opačného prvku, značíme $y=-x$),
* $x+y = y+x$ \dots\ (komutativní zákon).
\par}

Na množině $\R$ máme také operaci $\cdot$, která splňuje:

{\medskip\parskip=0pt
* $x\cdot(y\cdot z) = (x\cdot y)\cdot z$ \dots\ (asociativní zákon),
* existuje prvek $1\in\R$ takový, že $1\cdot x = x\cdot 1 = x$ \ $\forall x\in\R$\hb
  \dots\ (existence jednotkového prvku),
* $\forall x\in\R$, $x\not=0$ existuje prvek $y\in\R$ tak, že
  $x\cdot y=y\cdot x=1$\hb
  \dots\ (existence inverzního prvku, značíme $y=x^{-1}$),
* $x\cdot y = y\cdot x$ \dots\ (komutativní zákon).
\par}

\n -------------------------------------------------------

\g Množina s jednou operací: grupoid, grupa

{\bf Definice}: Předpokládejme množinu $G$ a na ní operaci $\Circ$.\hb
Dále uvažujme vlastnosti:

(1) $x\Circ(y\Circ z) = (x\Circ y)\Circ z$ \ $\forall x,y,z\in G$
    \dots\ (asociativní zákon),

(2) existuje prvek $e\in G$ takový, že $e\Circ x = x\Circ e = x$ \
    $\forall x\in G$\hb \dots\ (existence neutrálního/jednotkového prvku),

(3) $\forall x\in G$ existuje prvek $y\in G$ tak, že
  $x\Circ y=y\Circ x=e$\hb
  \dots\ (existence opačného/inverzního prvku),

(4) $x\Circ y = y\Circ x$ \ $\forall x,y\in G$ \dots\ (komutativní zákon).

* Množina $G$ s operací $\Circ$ se nazývá {\em grupoid}.

* Grupoid, kde platí asociativní zákon (1), se nazývá {\em pologrupa}.

* Pologrupa s vlastnostmi (2) a (3) se nazývá {\em grupa}.

* Grupa, kde platí komutativní zákon (4), je
  {\em komutativní grupa}.


\n --------------------------------------------------------

\g Příklady

* $\R$ s operací $+$ je komutativní grupa.

* $\R$ s operací \ $\cdot$ \ je pologrupa, $\R\setminus\{0\}$ je komutativní grupa.

* $\Q$, $\Z$ s operací $+$ jsou komutativní grupy (podgrupy grupy $\R$ s $+$).

* $\Z\setminus\{0\}$ s operací \ $\cdot$ \ není grupa (je to pologrupa). 

* Množina $\{e\}$ s operací $\Circ$, pro kterou $e\Circ e=e$, je grupa.

* Množina regulárních matic s maticovým násobením je grupa.

* Množina ctvercových matic s násobením je pologrupa.

* Množina funkcí $\R\to\R$ prostých a na s operací skládání je grupa.

* Množina bijektivních zobrazení $M\to M$ s op. skládání je grupa.

* Množina permutací s operací skládání je grupa

* Množina $\{0,1,\ldots,m-1\}$ s operací \uv{$+$ modulo $m$} je grupa.


\n ----------------------------------------------------------

\g Terminologie: jednotkový/neutrální prvek

Operace komutativní grupy bývá někdy označena symbolem $+$.
V~takovém případě prvek $e$ z vlastnosti (2) grupy se nazývá {\em ne\-utrální prvek}
a prvek $y$ z vlastnosti (3) se nazývá {\em opačný prvek}.

Neutrální prvek se v tomto případě značí symbolem $0$ a opačný prvek
k prvku $x$ se značí $-x$. Operaci $a + (-b)$ značíme stručněji $a-b$
a říkáme ji {\em odečítání}.

Je-li operace grupy označena symbolem \ $\cdot$ \ (krát), pak
prvku $e$ z~vlastnosti (2) grupy říkáme {\em jednotkový prvek} a 
prvku $y$ z~vlastnosti (3) říkáme {\em inverzní prvek}. 

Jednotkový prvek v takovém případě značíme symbolem $1$ a inverzní
prvek k prvku $x$ značíme $x^{-1}$. Je-li grupa komutativní, pak
operaci $a\cdot b^{-1}$ značíme stručněji $a/b$ a říkáme ji {\em dělení}.

\n -----------------------------------------------------------

\g Základní vlastnosti grupy

* Neutrální/jednotkový prvek je v grupě jediný.\hb
  Kdyby byly dva $e$, $f$, pak $e = e\Circ f = f$, takže nemohou být různé.

* Opačný/inverzní prvek existuje ke každému prvku $x\in G$ jediný.\hb
  Kdyby existovaly $y_1$, $y_2$ tak, že $y_1\Circ x = e$, $x\Circ y_2= e$, pak
  $$
    y_1 = y_1 \Circ e = y_1\Circ (x\Circ y_2) = (y_1\Circ x)\Circ y_2
    = e\Circ y_2 = y_2.
  $$
* Pologrupa $G$ je grupou právě když pro každé $a,b\in G$ existují řešení rovnic
  $$
    a\Circ x = b, \qquad y\Circ a = b.
  $$
  Náznak důkazu: Je-li $G$ grupa, pak $x=a^{-1}\Circ b$ a $y = b\Circ a^{-1}$
  jsou řešení uvedených rovnic.
  Umíme-li řešit tyto rovnice, pak jednotkový prvek $e$ je řešení
  rovnice $a\Circ e=a$ (je třeba ukázat, že to nezávisí na volbě $a$).
  Dále inverzní prvek k $a$ je řešení $a\Circ x = e$ (je třeba ukázat,
  že je to totéž, jako řešení rovnice $y\Circ a = e$). 

\n -----------------------------------------------------------

\g Vlastnosti inverzních prvků grupy

* Jednotkový prvek $e$ má inverzní prvek $e$ (je inverzní sám sobě).\hb
Skutečně:  $e = e\Circ e$.

* Je-li $a^{-1}$ invernzí prvek k $a$, je-li dále $b^{-1}$ inverzní
prvek k $b$, pak inverzní prvek k $a\Circ b$ je tvaru $b^{-1}\Circ a^{-1}$.\hb
Skutečně: 
$$
  \displaylines{
  (b^{-1}\Circ a^{-1})\Circ(a\Circ b) = b^{-1}\Circ (a^{-1}\Circ
  a)\Circ b = b^{-1}\Circ e\Circ b = b^{-1}\Circ b = e,\cr
  (a\Circ b)\Circ(b^{-1}\Circ a^{-1}) = a\Circ (b\Circ b^{-1})\Circ a^{-1}
  =  a\Circ e\Circ a^{-1} = a\Circ a^{-1} = e.
} 
$$

* Je-li $a^{-1}$ inverzní k $a$, pak $a$ je inverzní k $a^{-1}$.\hb
Skutečně: $a^{-1}\Circ a = a\Circ a^{-1} = e $.

\n -----------------------------------------------------------

\g Mocnina

Je-li $a\in G$, pak symbolem $a^k$ označme prvek
$a\Circ a\Circ \cdots \Circ a$ ($k$-krát).

{\bf Tvrzení}: Je-li $G$ konečná komutativní grupa s $n$ prvky, pak pro každé
$a\in G$ je 
$$
  a^n=e.
$$
Důkaz: Označme $G = \{g_1,g_2,\ldots, g_n\}$ a zvolme $a\in
G$. Ukážeme, že
$$
  \{g_1,g_2,\ldots, g_n\} \ = \
  \{a\Circ g_1,a\Circ g_2,\ldots, a\Circ g_n\}.
$$ 
Zobrazení, které přiřadí prvku $g_i$ prvek $a\Circ g_i$ je prosté,
protože, pokud $a\Circ g_i = a\Circ g_j$, pak po aplikaci $a^{-1}$
zleva máme $g_i = g_j$. Uvedené množiny jsou tedy stejně početné a
tedy stejné a mají tedy stejný součin všech prvků:
$$
  a\Circ g_1\Circ a\Circ g_2\Circ \cdots\Circ a\Circ g_n \ = \
  g_1\Circ g_2\Circ\cdots\Circ g_n = u
$$
Díky komutativnímu zákonu se rovnost dá přepsat na $a^n\Circ u = u$
a dokazovaná rovnost plyne aplikací $u^{-1}$ na obě strany rovnosti.


\n -----------------------------------------------------------

\g Podgrupy

{\em Podgrupa\/} $P$ je podmnožina grupy $G$ se stejnou operací, která je sama
grupou. Tj. $P$ musí mít (stejný) jednotkový prvek a každý prvek z $P$
musí mít inverzi v $P$.

{\bf Příklady}:

* $\Q$ a $\Z$ je podgrupa grupy $\R$ s operací $+$,

* $\Q\setminus\{0\}$ je podgrupa grupy $\R\setminus\{0\}$ s operací $\cdot$, 

* symetrické matice tvoří podgrupu čtvercových matic s operací~$+$,

* matice s $\det=1$ tvoří podgrupu regulárních matic s operací $\cdot$,

* Sudá čísla tvoří podgrupu $\Z$ s operací $+$,

* Kladná čísla tvoří podgrupu grupy $\R$ s operací $\cdot$.

\n -----------------------------------------------------------

\g Vlastnosti pologrupy \uv{krát modulo $\setmath[//]m$}

Předpokládejme množinu $\{0,1,2,\ldots,m-1\}$ s operací \uv{krát modulo
$m$}, tj.  $a\circ b = a\cdot b$ pro $a\cdot b<m$, jinak $a\circ b$ je zbytek po
dělení čísla $a\cdot b$ číslem $m$. Je to pologrupa. Tato pologrupa má
jednotkový prvek: 1.

{\bf Tvrzení}: je-li $m$ složené, tj. $m=n_1\cdot n_2$, ($n_1\not=1$, $n_2\not=1$)
pak číslo $n_1$ nemá inverzní prvek.

Důkaz: $v\circ n_1 = z$, tj. $v n_1 = kn_1n_2+z$, tj. $z =
n_1\,(v-kn_2)$, takže $z$ musí být násobek $n_1$ a nemůže tedy být roven jedné.

{\bf Tvrzení}: je-li $m$ prvočíslo, pak množina $\{1,2,\ldots,m-1\}$ s
operací~$\circ$ je grupa.

Dokážeme\char`\*, že každý nenulový prvek $a$ má inverzi. Platí totiž, že 
$\{a, 2\circ a,\ldots, (m-1)\circ a\} = \{1,\cdots,m-1\}$. Důvod: pro
$k_1\not=k_2$ je $a\circ k_1\not= a\circ k_2$, protože
z $a\,(k_1-k_2) = km$ plyne $k_1-k_2=k'm$ (je $a$ nesoudělné s $m$).
Protože $0\le k_1-k_2<m$, musí $k'=0$, takže $k_1=k_2$.


\n -----------------------------------------------------------

\g Malá Fermatova věta

Nechť $p$ je prvočíslo, nechť $a$ je přirozené číslo, $a<p$. Pak
$$
  a^{\,p-1} = 1 \quad (\hbox{modulo}\ p).
$$
Důkaz: stačí si uvědomit, že grupa $\{1,2,\ldots,p-1\}$ s operací
\uv{krát modulo $p$} má $p-1$ prvků a použít větu ze stránky [8].


\n -----------------------------------------------------------

\g Množina se dvěma operacemi: okruh, těleso

{\bf Definice}: {\em Okruh} je množina $T$ s operacemi $+$ a
$\cdot$, pro které platí:

(1) $T$ s operací $+$ je komutativní grupa (neutrální prvek značíme~0),

(2) $T$ s operací $\cdot$ je pologrupa,

(3) $\forall\, x,y,z\in T$ platí $x\cdot(y+z) = (x\cdot y) + (x\cdot z)$, \
    $(y+z)\cdot x = (y\cdot x) + (z\cdot x)$.
    \dots\ (distributivní zákon).

{\bf Definice}: {\em Těleso} je množina $T$ s operacemi $+$ a
$\cdot$, pro které platí:

(1) $T$ s operací $+$ je komutativní grupa (neutrální prvek značíme~0),

(2) $T\setminus \{0\}$ s operací $\cdot$ je grupa (jednotkový prvek značíme~1),

(3) $\forall\, x,y,z\in T$ platí $x\cdot(y+z) = (x\cdot y) + (x\cdot z)$, \
    $(y+z)\cdot x = (y\cdot x) + (z\cdot x)$.
    \dots\ (distributivní zákon).

{\bf Pozorování}: Každé těleso musí mít aspoň dva prvky: 0 a 1.


\n ---------------------------------------------------------

\g Varianty okruhů a těles

Předpokládejme množinu $T$ s vlastnostmi (1) a (3).

* Je-li $T$ s operací $\cdot$ komutativní pologrupa,
  pak $T$ se nazývá {\em komutativní okruh}.

* Je-li $T$ s operací $\cdot$ pologrupa a má-li
  jednotkový prvek, pak $T$ se nazývá {\em okruh s jednotkou}.

* Je-li $T$ s operací $\cdot$ komutativní pologrupa a má-li
  jednotkový prvek, pak $T$ se nazývá {\em komutativní okruh s jednotkou}.

* Je-li $T\setminus \{0\}$ s operací $\cdot$ komutativní grupa,
  pak $T$ se nazývá {\em komutativní těleso}.

{\bf Poznámčička}: příklad nekomutativního tělesa (kvaterniony) pro nedostatek
místa vynecháme. Všechna ostatní tělesa, o~kterých budeme
mluvit, jsou komutativní tělesa. Takže slovo \uv{komutativní}
nebudeme v případě těles nadále zdůrazňovat.

\n ----------------------------------------------------------

\g Příklady

* Množina reálných čísel s operacemi $+$ a $\cdot$ tvoří těleso.

* Množiny $\Q$ a $\C$ s operacemi $+$ a $\cdot$ jsou také tělesa.

* Množina $\Z$ s operacemi $+$ a $\cdot$ 
  je to komutativní okruh s jednotkou.

* Množina sudých celých čísel s $+$ a $\cdot$ je komutativní okruh.

* Množina regulárních matic s operacemi $+$ a $\cdot$ není těleso ani okruh,
  protože součet dvou reg. matic nemusí být regulární.

* Množina čtvercových matic (stejného typu) s operacemi $+$ a $\cdot$
  je nekomutativní okruh s~jednotkou. Není to těleso.

* Množina $\{0,1\}$ s operacemi $0+0 = 0$, $0+1 = 1+0 = 1$, $1+1=0$,
  $0\cdot a = a\cdot 0 = 0$, $1\cdot a = a\cdot 1 = a$, tvoří těleso.

* Množina $\{0,1,\ldots,p-1\}$ s operacemi
  \uv{$+$ modulo $p$} a \uv{krát modulo~$p$} tvoří těleso, právě když 
  je $p$ prvočíslo. Jinak je to okruh.

\n --------------------------------------------------------

\g Konečná (Galoisova) tělesa

Dá se ukázat, že pokud je těleso $T$ konečné, 
pak nastává jen jedna z následujících možností:

* $T = \{0,1,2,\ldots,p-1\}$ s operací \uv{$+$ modulo $p$}
  a \uv{krát modulo $p$}, kde $p$ je prvočíslo.
  Toto těleso se značí $\Z_p$ a má $p$ prvků.

* $T$ je množina všech polynomů nad $\Z_p$ stupně menšího než $n$ 
  s~operacemi \uv{plus a krát modulo ireducibilní polynom 
  stupně $n$}. Toto těleso má $p^n$ 
  prvků, podrobněji se k němu vrátíme za chvíli.

Jiné konečné těleso (až na izomorfismus) neexistuje.
Konečná tělesa se někdy značí GF$(p^n)$, kde argument informuje o
počtu prvků tělesa a GF je zkratka pro \uv{Galois field}.

{\bf Příklady}: neexistuje těleso, které má 6 prvků.
Existuje ale těleso, které má 8 prvků: GF($2^3$) nebo 9 prvků: GF($3^2$).

$\Z_5$ je těleso, ale $\Z_8$ není těleso (je to jen okruh).

\n -------------------------------------------------------------

\g Základní vlastnosti tělesa

* Pro libovolné $a, b\in T$ je: \ $a\cdot b=0$, právě když $a=0$ nebo $b=0$.\hb
  Důkaz: Nechť $a\not=0$ a $b\not=0$. Pak $a\cdot b\not=0$ z
  vlastnosti (2) definice tělesa. Obráceně: BÚNO $a=0$, ukážeme, že
  $0\cdot b=0$. Platí:
  $$
    0\cdot b = (0+0)\cdot b = 0\cdot b + 0\cdot b.
  $$
  Přičtením $-\,(0\cdot b)$ k oběma stranám rovnosti máme
  $0 = 0\cdot b$. 

* Jestliže existuje konečný počet jedniček, které v součtu dají nulu,
  je nejmenší takový počet prvočíslo.\hb
  Důkaz: Nejmenší počet jedniček, které dají v součtu nulu, označím $\lambda$.
  Pro spor budiž $\lambda=m\cdot n$, $m<\lambda$, $n<\lambda$. Pak
  $$
    \left(\sum_1^m 1\right)\cdot\left(\sum_1^n 1\right) = 
    \sum_1^{m\,n} 1 = \sum_1^\lambda 1 = 0
  $$
  takže (dle předchozí vlastnosti) musí být aspoň jedna závorka nulová.
  Tj. existuje menší počet jedniček, které mají součet nula.

\n -------------------------------------------------------

\g Charakteristika tělesa

{\bf Definice}: Charakteristika tělesa $\lambda$ je nejmenší počet jedniček,
které dají v součtu nulu. Pokud konečný počet jedniček s touto
vlastností neexistuje, klademe $\lambda=0$.

{\bf Příklady}:

* Tělesa $\Q$, $\R$, $\C$ mají charakteristiku $\lambda=0$.

* Těleso $\Z_p$ ($p$ prvočíslo) má charakteristku $\lambda=p$.

{\bf Pozorování}: z předchozí stránky víme, že charakteristika tělesa
je rovna prvočíslu (je-li konečná).

{\bf Tvrzení}: 
* Je-li $p$ charakteristika tělesa, pak 
  $(a+b)^p = a^p + b^p$.

* V tělese $\Z_p$ dokonce platí: $a^p = a$ \ (díky malé Fermatově větě).

* V obecném tělese s charakteristikou $p$ ovšem neplatí $a^p=a$.


\n --------------------------------------------------------


\g Znovu definice lineárního prostoru

{\bf Definice}: {\em Lineární prostor nad tělesem T\/} je neprázdná
množina $L$ s operacemi $+: L\times L\to L$ a $\cdot: T\times L\to L$,
které splňují vlastnosti:

(+) \ $L$ s operací $+$ je komutativní grupa, nulový prvek značíme~$\vec o$,

(A) \ $\alpha\cdot(\beta\cdot\vec x) = (\alpha\cdot\beta)\cdot \vec x$
    pro všechna $\vec x\in L$, $\alpha,\beta\in T$,

(B) \ $\alpha\cdot(\vec x+\vec y) = \alpha\cdot\vec x + \alpha\cdot\vec y$
    pro všechna $\vec x, \vec y\in L$, $\alpha\in T$, 

(C) \ $(\alpha+\beta)\cdot \vec x = \alpha\cdot\vec x+\beta\cdot \vec x$
    pro všechna $\vec x\in L$, $\alpha,\beta\in T$,

(D) \ $1\cdot \vec x = \vec x$ pro všechna $\vec x\in L$.

{\bf Pozorování}: Pro $T=\R$ se definice shoduje s původní definicí lin. prostoru.
Stačí ověřit, že platí (7): $0\cdot\vec x = \vec o$ pro všechny $\vec
x\in L$:
$$
  0\cdot\vec x = (0+0)\cdot\vec x = 0\cdot\vec x+0\cdot\vec x,
$$
k této rovnosti přičteme $-\,(0\cdot\vec x)$ a dostáváme
$\vec o =0\cdot\vec x$. 

\n ----------------------------------------------------------

\g Aritmetický lineární prostor $\setmath[//]T^n$

je analogií lineárního prostoru $\R^n$. Množina $T^n$ je množinou
všech uspořádaných $n$-tic prvků z tělesa $T$ s operacemi sčítání
$n$-tic a
násobení $n$-tice skalárem z $T$, které jsou definovány takto:

(1) \ $(a_1,a_2,\ldots,a_n) + (b_1,b_2,\ldots,b_n) =
       (a_1+b_1,a_2+b_2,\ldots,a_n+b_n)$,

(2) \ $\alpha\cdot (a_1,a_2,\ldots,a_n) =
      (\alpha\cdot a_1,\alpha\cdot a_2,\ldots,\alpha\cdot a_n)$.

{\bf Pozorování}: Tento lineární prostor má bázi
$$
  (1,0,\ldots,0),\ (0,1,\ldots,0),\ \ldots,\ (0,0,\ldots,1),
$$ takže má
dimenzi $n$.

Je-li $T$ konečné těleso, které má $m$ prvků, pak celkový počet
vektorů v $T^n$ je $m^n$.

Každý podprostor prostoru $T^n$ dimenze $k$ má $m^k$ prvků,
protože existuje $m^k$ různých lineárních kombinací báze.


\n -----------------------------------------------------

\g Příklad: lineární prostor $\setmath[//]\Z_2^n$

je lineární prostor uspořádaných $n$-tic jedniček a nul nad tělesem~$\Z_2$. 
Prvky tělesa $\Z_2=\{0,1\}$ sčítáme podle pravidla 
$$0+0=0,\quad 0+1=1+0=1,\quad 1+1=0$$ 
a vektory (uspořádané $n$-tice) sčítáme a násobíme po složkách, jako na
předchozí stránce. Jmenovitě pro libovolný $\vec u\in\Z_2^n$ je
$1\cdot\vec u=\vec u$ a $0\cdot\vec u =\vec o$. S jinými skaláry 
nepracujeme.


\n -------------------------------------------------------

\g Příklad: soustava lineárních rovnic v $\setmath[//]\Z_5$

Vyřešíme soustavu lineárních rovnic v $\Z_5$ s následující rozšířenou
maticí. V první eliminační úpravě jsem sečetl první řádek s~druhým a
dále od třetího odečetl dvojnásobek prvního.
$$
  \def\|{\hfill\kern8pt\vrule height1.1em depth.3em\kern-5pt}
  \def\c{\cr\noalign{\vskip-2pt}}
  \pmatrix {2&3&1&1\|&4\c3&1&2&2\|&2\c4&3&3&1\|&1} \sim
  \pmatrix {2&3&1&1\|&4\c0&4&3&3\|&1\c0&2&1&4\|&3} \sim
  \pmatrix {2&3&1&1\|&4\c0&2&1&4\|&3\c0&0&1&0\|&0}
$$
Množina řešení přidružené homogenní soustavy $M_0 = \lob<(0,3,0,1)>$
a partikulární řešení je např. $(1,4,0,0)$. Všechny principy lineární
algebry (o dimenzích, lineárních obalech, bázích) zůstávají 
v~platnosti. Rozdíl proti lin. prostoru nad $\R$ je jen ten, že zde jsou
(pod)prostory konečné. Např. $M_0$ zde má pět prvků (vektor je
možné násobit jen čísly $0,1,2,3,4,$), takže množinu řešení můžeme
zapsat výčtem prvků:
$$
  M = \{(1,4,0,0),\ (1,2,0,1),\ (1,0,0,2),\ (1,3,0,3),\ (1,1,0,4)\}
$$


\n --------------------------------------------------------

\g Polynom nad komutativním tělesem $\setmath[//]T$

je vzorec
$$
  a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0
$$
kde $a_i\in T$. Tento vzorec vymezuje předpis pro hodnoty
zobrazení z $T$ do $T$ (za $x$ dosazujeme prvky z tělesa $T$ a
dostáváme hodnoty polynomu: prvky z tělesa $T$).

{\bf Rovnost polynomů}: dva polynomy se rovnají, když se rovnají
jejich odpovídající koeficienty (až na případné přebytečné 
nulové koeficienty s nejvyššími indexy).

{\bf Pozor}: rovnost není zaručena rovností zobrazení $T\to\nobreak T$.

{\bf Příklad}: Polynom $x^2 + 1$ nad $\Z_2$ odpovídá zobrazení $0\to 1$,
$1\to 0$. Polynom $x^3 + 1$ odpovídá stejnému zobrazení, ale není to
stejný polynom.


\n ---------------------------------------------------------

\g Operace s polynomy nad tělesem

Součet, rozdíl nebo součin polynomů nad $T$ provedeme jako součet, rozdíl nebo
součin příslušných vzorců. Přitom provádíme výpočty s~jednotlivými
koeficienty polynomů za použití operací v tělese $T$.

{\bf Příklad}:
Sečteme polynomy nad $\Z_5$:
$$
  (2x^3 + 4x^2 + 2x + 1) + (3x^2 + 2x) = 2x^3 + (4+3)x^2 + (2+2)x + 1 =
  2x^3 + 2x^2 + 4x + 1.\kern-7pt
$$

{\bf Příklad}:
Vynásobíme polynomy nad $\Z_5$:
$$
  \displaylines{
  (2x^3 + 4x^2 + 2x + 1) \cdot (3x^2 + 2x) =\cr =
  (2\cdot3)x^5 + (4\cdot3)x^4 + (2\cdot3)x^3 + 3x^2 + (2\cdot2)x^4 + 
  (4\cdot2)x^3 + (2\cdot2)x^2 + 2x =\cr =
  x^5 + 2x^4 + x^3 + 3x^2 + 4x^4 + 3x^3 + 4 x^2 + 2x =\cr =
  x^5 + (2+4)x^4 + (1+3)x^3 + (3+4)x^2 + 2x =\cr = 
  x^5 + x^4 + 4x^3 + 2x^2 + 2x
}
$$  

\n ----------------------------------------------------------

\g Částečný podíl polynomů

{\bf Věta}: pro každé dva polynomy $p$, $q$ ($q$ nenulový) existují
jednoznačně polynomy $r$, $z$ tak, že \hb
1) $p = r\cdot q + z$,\hb 
2) stupeň $z$ je menší než stupeň $q$.

Algoritmus částečného dělení polynomu polynomem lze použít stejně nad
libovolným tělesem. Naučili jsme se ho používat pro polynomy nad $\R$
a nyní jej budeme používat pro polynomy nad libovolným tělesem.
Zaskočit nás může jen úkon dělení koeficientu $a$ koeficientem $b$, 
což je ale v každém komutativním tělese proveditelné jako $a\cdot b^{-1}$. 

\n ----------------------------------------------------------

\g Příklad: algoritmus částečného podílu

Vydělíme polynomy nad $\Z_5$. V tomto případě si uvědomíme, že
$3^{-1}=2$, protože $3\cdot2 = 1$ modulo 5. Takže například první krok algoritmu
obsahuje výpočet $2x^3 : 3x^2 = (2\cdot 3^{-1})\,x = (2\cdot 2)\,x = 4x$

$\quad(2x^3 + 4x^2 + 2x + 1) : (3x^2 + 2x) = 4 x + 2$\hb
$\null\kern1pt -(2x^3 + 3x^2)$

$\kern 75pt x^2 + 2x + 1$\hb
$\null\kern55pt -(x^2+4x)$

$\kern 105pt -2x + 1$

Podíl daných polynomů roven $4 x + 2$ a
zbytek je $-2x+1 = 3x+1$. 

\n ---------------------------------------------------------

\g Operace modulo polynom

Srovnejme dvě tvrzení: 

* Pro každé dvě celá čísla $a$, $b$ ($b$ nenulové) existují celá čísla
  $r$, $z$ tak, že $a = rb + z$, přitom $0\le z<b$. Číslo $z$ je zbytek po dělení $a$
  číslem $b$.

* Pro každé dva polynomy $p$, $q$ ($q$ nenulový) existují polynomy
  $r$, $z$ tak, že $p = r\cdot q + z$, přitom st$\,z<{}$ st$\,q$. Polynom
  $z$ je zbytek po dělení $p$ polynomem $q$.

Tak jako můžeme pro dvě čísla najít zbytek po dělení, můžeme pro dva
polynomy najít zbytek po dělení. Je-li dán nenulový polynom, modul
$q$, pak každý polynom $p$ můžeme ztotožnit se zbytkem po dělení $p$
polynomem $q$. Označíme-li $z$ tento zbytek, pak říkáme:
$$
  p = z \quad \hbox{modulo $q$}.
$$

\n -------------------------------------------------------

\g Okruh polynomů modulo polynom

Zvolme nenulový polynom $q$ stupně $n$ jako modul a prvočíslo $p$. Symbolem
$\Z_p[x]/q$ označíme množinu všech polynomů nad tělesem $\Z_p$, která
má stupeň menší než $n$. Zavedeme tyto operace:

* {\bf Sčítání} prvků z $\Z_p[x]/q$: provedeme jako obvyklé sčítání
polynomů nad $\Z_p$. Stupeň součtu je jistě menší než $n$, takže leží
v~$\Z_p[x]/q$. Množina $\Z_p[x]/q$ s tímto sčítáním zjevně tvoří
komutativní grupu.

* {\bf Násobení} prvků a $\Z_p[x]/q$: provedeme obvyklé násobení
polynomů nad $\Z_p$. Pokud stupeň výsledku je větší nebo roven $n$,
provedeme navíc na výsledek operaci \uv{modulo polynom $q$}. Množina $\Z_p[x]/q$
s tímto násobením je pologrupa.

Platí distributivní zákony: tj. množina $\Z_p[x]/q$ s uvedenými
operacemi je okruh.

\n --------------------------------------------------------

\g Ireducibilní polynom

Polynom $q$ je {\em ireducibilní}, právě když jej nelze rozložit na
součin dvou polynomů nižších stupňů.

{\bf Příklad}: Polynom $x^2+x+1$ nad $\Z_2$ je ireducibilní, protože
kdyby šel rozložit na součin polynomů nižších stupňů, pak je to součin  
kořenových činitelů, ale tento polynom v $\Z_2$ nemá kořeny
(vyzkoušejte postupným dosazením čísel 0 a 1).

{\bf Příklad}: Polynom $x^3+x+1$ nad $\Z_2$ je ireducibilní (ze stejných důvodů).

{\bf Příklad}: Polynom $x^5+x^4+1$ nad $\Z_2$ je reducibilní, protože
$$
  x^5+x^4+1 = (x^3+x+1)\cdot(x^2+x+1).
$$
V případě polynomu stupně 4. a více nám test existence kořenů 
k~rozhodnutí o ireducibilitě nepomůže.

\n -------------------------------------------------------

\g Polynomy modulo ireducibilní polynom

Dá se ukázat, že pokud je polynom $q$ ireducibilní, pak okruh
$\Z_p[x]/q$ je těleso, tj. každý polynom z množiny $\Z_p[x]/q$ 
má při operaci násobení inverzní polynom.

Důkaz\char`\*\ se dá provést anoalogicky, jako s čísly. Povšimneme si této
podobnosti:

* $p$ je prvočíslo, tj. nelze rozložit na součin menších čísel.

* $q$ je ireducibilní, tj. nelze rozložit na součin polynomů menších stupňů. 

Je možné přečíst důkaz tvrzení ze stránky [10] znovu, jen slovo
číslo nahradíme slovem polynom, slovo prvočíslo slovem ireducibilní
polynom a výrok \uv{číslo $a$ je menší než $b$} výrokem \uv{stupeň
polynomu $p$ je menší než stupeň $q$}.

\n -------------------------------------------------

\g Příklad: těleso $\setmath[//]\Z_2[x]/(x^3+x+1)$

Modul $(x^3+x+1)$ je ireducibilní. Toto těleso obsahuje:
$$
  \Z_2[x]/x^3+x+1 \ = \ \{0,\ 1,\ x,\ x+1,\ x^2,\ x^2+1,\ x^2+x,\ x^2+x+1\}
$$
Sčítání prvků provádíme jako sčítání polynomů nad $\Z_2$, například:
$$
  (x+1) + (x^2+x) = x^2 + 1
$$
Násobení prvků provádíme jako násobení polynomů nad $\Z_2$ s případnou
dodatečnou operací \uv{modulo $x^3+x+1$}. Například:
$$
  (x+1)\cdot (x^2+x) = x^3 + x = 1 \quad \hbox{modulo $(x^3+x+1)$}
$$
Vidíme, že prvky $x+1$ a $x^2+x$ jsou si vzájemně inverzní.

Toto je příklad tělesa, který obsahuje 8 prvků, je to tedy GF$(2^3)$.

* Má-li ireducibilní modul $q$ stupeň $n$, je $\Z_p[x]/q = {\rm GF}(p^n)$.

\n ---------------------------------------------------------

\g Příklad: komplexní čísla 

Polynom $x^2+1$ je nad $\R$ ireducibilní. Označme symbolem $\R[x]$
všechny polynomy nad $\R$ a dále $\R[x]/(x^2+1)$ bude značit množinu všech
polynomů nejvýše prvního stupně s obvyklou operací $+$ a s operací
\uv{krát modulo polynom $x^2+1$}. Takže
$$
  \R[x]/(x^2+1) = \{a + bx;\ a,b\in\R\}
$$
Dva polynomy v $\R[x]/(x^2+1)$ sčítáme podle pravidla:
$$
  (a + bx) + (c + dx) = (a+c) + (b+d)x.
$$
Dva polynomy v $\R[x]/(x^2+1)$ násobíme podle pravidla:
$$
  \eqalign {
  (a + bx) \cdot (c + dx) &= bdx^2 + (ad+bc)x + ac = \cr &= (ac-bd) + (ad+bc)x \quad 
  \hbox{modulo } x^2+1
}
$$
Nahrazením symbolu $x$ symbolem $i$ shledáváme, že\hb
těleso $\R[x]/(x^2+1)$ je izomorfní s tělesem komplexních čísel.

\end