\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
