Aktuální verze z 17. 2. 2012, 14:24

Zdrojový kód

%\wikiskriptum{01ALG}
 
\xxx{Konečná tělesa}
 
\xxxx{Konečná tělesa}
 
\theorem(Wedderburn)
Libovolné konečné těleso je komutativní.
 
\theorem
Libovolné konečné těleso $T$ má řád $p^n$, kde $p\in\bbP$ a $n\in\N$,
přičemž $p=\ch T$ a $n=\dim_{Z_p}T$.
 
\proof
$T$ je vektorový prostor nad tělesem $Z_p$ (až na izomorfie) a $\dim_{Z_p}T=n$, a tedy
$T\owns\alpha=\sum_{i=1}^n\alpha_iu_i$, kde $\alpha_i\in Z_p$ a $(u_i)_{i=1}^n$ je báze $T$.
Počet $n$-tic $(\alpha_1\cldc\alpha_n)$ je $p^n$ a z~jednoznačnosti vyjádření prvku v bázi dostáváme,
 že prvků $T$ je také $p^n$.
\QED
 
\lemma(binomická věta)
Nechť $R$ je asociativní a komutativní okruh s~jednotkou, nechť $a,b\in R\supdot$ a $n\in\N$.
Pak platí:
$$(a+b)^n=a^n+\sum_{i=1}^{n-1}\qlb{n\atop i}a^ib^{n-i}+b^n.$$
 
\lemma
V tělese charakteristiky $p\in\bbP$ platí: $$(a\pm b)^{p^m}=a^{p^m}\pm b^{p^m}.$$
 
\proof
Nechť nejprve $m=1$.
Důkaz provedeme matematickou indukcí podle $m$.
 
\begin{description}
\ditem{$m=1$, $a+b$}
Chceme ukázat, že $\sum_{i=1}^{p-1}\qlb{p\atop i}a^ib^{p-i}=0$.
Zjevně platí, že $p\divides p!=\qlb{p\atop i}i!(p-i)!$.
Neboť $p$ je prvočíslo, musí dělit alespoň jeden z~činitelů.
Neboť pro $0<i<p$ je $i<p$ a $p-i<p$, platí $p\divides\qlb{p\atop i}$,
 tedy $\qlb{p\atop i}$ je násobkem charakteristiky, a tedy $\qlb{p\atop i}a^ib^{p-i}=0$.
 
\ditem{$m=1$, $a-b$}
Pro $p=2$ je $(a-b)^2=a^2-2ab+b^2=a^2-b^2=a^2-b^2+2b^2=a^2+b^2$
Pro $p$ liché je $(a-b)^p=(a+(-b))^p=a^p+(-b)^p=a^p-b^p$.
 
\ditem{$m\rightarrow m+1$}
$\qlb{a\pm b}^{p^{m+1}}=\qlb{\qlb{a\pm b}^{p^m}}^p=
\qlb{a^{p^m}\pm b^{p^m}}^p=\qlb{a^{p^m}}^p\pm\qlb{b^{p^m}}^p=a^{p^{m+1}}\pm b^{p^{m+1}}$.
\end{description}
\QED
 
\lemma
V konečném tělese řádu $q$ platí pro všechny prvky $a^q=a$.
 
\proof
Nechť $\abs U=q$, lib. $a\in U$, $a\neq 0$.
Pak $a\in U\subast$, $\abs{U\subast}=q-1$ a podle Lagrangeovy věty řád $a$ dělí $q-1$, a tedy $a^{q-1}=1$.
Potom též $a^q=a$, což platí i pro $a=0$, tedy pro všechny prvky.
\QED
 
\theorem
K~libovolným číslu $p\in\bbP$ a $n\in\N$ existuje až na izomorfismus právě jedno těleso řádu $p^n$.
Takové těleso značíme $\GF(p^n)$ (\defined[těleso!Galoisovo]{Galoisova tělesa}).
 
\proof
Položme $q:=p^n$ a definujme $P:=x^q-x\in Z_p[x]$.
Nechť $U$ je rozkladové těleso polynomu $P$ a nechť
 $U_0=\set{\alpha\in U}{P(\alpha)=0}=\set{\alpha\in U}{\alpha^q=\alpha}$.
Dále $P'=qx^{q-1}-1x^0=pp^{n-1}x^{q-1}-1x^0=-1x^0$, tedy derivace nemá kořen, a tedy všechny kořeny $P$ jsou 1násobné.
 
Ukážeme, že $U_0$ je těleso, tedy že je uzavřené v tělese $U$.
Mějme $\alpha,\beta\in U_0$.
Pak $\qlb{\alpha-\beta}^q=\qlb{\alpha-\beta}^{p^{\vphantom Xn}}=\alpha^q-\beta^q=\alpha-\beta$,
 tedy $\alpha-\beta\in U_0$.
Nechť navíc $\beta\neq0$, pak $(\alpha\beta^\1)^q=\alpha^q\qlb{\beta^q}^\1=\alpha\beta^\1$, tedy $\alpha\beta^\1\in U_0$.
Tedy jsme nalezli těleso o $p^n$ prvcích.
 
Jednoznačnost nedokazujeme.
\QED
 
\lemma
Buď $G=(M,\cdot)$ grupa a nechť $a,b\in M$ komutují, tj. $ab=ba$,
 a označme $m=\abs a$, $n=\abs b$ a $r=\abs{ab}$ řády prvků $a$, $b$ a $ab$.
Pak $r\divides mn$, a tedy $r\leq mn$.
A jsou-li $m,n$ nesoudělná, je $r=mn$.
 
\proof
Platí $(ab)^{mn}=\qlb{a^m}^n\qlb{b^n}^m=1^n1^m=1$, tedy $r\divides mn$.
 
Pro nesoudělná $m,n$ je
$1=(ab)^{mr}=(a^m)^rb^{mr}=b^{mr} \Limpl n\divides mr \Limpl n\divides r$.
Podobně také $m\divides r$, tedy $mn\divides r$.
\QED
 
\theorem
Buď $G=(M,\cdot)$ grupa a nechť $a,b\in M$ komutují, tj. $ab=ba$,
 a označme $m=\abs a$, $n=\abs b$ řády prvků $a$ a $b$.
Potom $(\EE c\in M)(\abs c=\lcm(m,n))$.
 
\proof
Položme $m=p_1^{k_1}\cdots p_r^{k_r}\,p_{r+1}^{k_{r+1}}\cdots p_{r+s}^{k_{r+s}}$
 a $n=p_1^{\ell_1}\cdots p_r^{\ell_r}\,p_{r+1}^{\ell_r+1}\cdots p_{r+s}^{\ell_r+s}$,
přičemž $k_i\geq\ell_i$ pro $i\in\hatn r$ a $k_i<\ell_i$ jinak.
 
Dále označme $\bar m=p_1^{k_1}\cdots p_r^{k_r}$ a $\bar n=p_{r+1}^{\ell_r+1}\cdots p_{r+s}^{\ell_r+s}$.
Zjevně $\gcd(\bar m, \bar n)=1$.
Označme $\bar a=a^{\frac m{\bar m}}$ a $\bar b=b^{\frac n{\bar n}}$.
Pak $\abs{\bar a}=\bar m$ a $\abs{\bar b}=\bar n$.
Dále $\bar a$ a $\bar b$ komutují a mají nesoudělné řády, označme $c=\bar a\bar b$,
 pak $\abs c=\bar m\bar n=\lcm(m,n)$.
\QED
 
\theorem
Multiplikativní grupa libovolného konečného tělesa $T$ je cyklická.
 
\proof
Označme $q=p^n=\abs T$ počet prvků tělesa $T$, tedy $T=\GF(q)$
Víme, že $\abs{T\subast}=q-1$.
Vezměme libovolné $a\in T\subast\supdot$
 
Nechť $\abs a=q-1$, pak $\anglevector a=T\subast$ a jsme hotovi.
Nechť tedy $m=\abs a<q-1$.
Mějme libovolné $b$ takové, že pro $n=\abs b$ platí $n\divides m$.
Tedy víme, že $b^m=1$, a tedy $b$ je kořenem polynomu $x^n-1\in Z_p[x]$, který má nejvýše $m$ kořenů.
A neboť $m<q-1$, existuje alespoň jeden prvek $b$ takový, že pro $n=\abs b$ platí $n\nmid m$.
Víme, že $T\subast$ je komutativní, tedy $(\EE c)(\abs c=\lcm(m,n))$ a neboť $n\nmid m$, je $\lcm(m,n)>m$.
 
Po konečně mnoha krocích musíme nezbytně dojít k číslu $q-1$.
\QED
 
\define
\defined[prvek (těleso)!primitivní]{Primitivním prvkem} konečného tělesa $T$
 je libovolný generátor jeho multiplikativní grupy.
 
\consequence
Libovolné konečné těleso má primitivní prvek.
 
\remark
Mějme $Z_p[x]$ a $P\in Z_p[x]$ ireducibilní stupně $n$.
Pak $Z_p[x]\factorset{I_P}$ je těleso o $p^n$ prvcích a v následující větě ukážeme,
 že takto lze zkonstruovat všechna konečná tělesa.
 
\example
Prozkoumejme $\GF(9)$.
 
$9=3^2$, tedy $Z_3=\{0,1,2\}$ a $P=x^2+x+2$, $P$ nemá v $Z_3$ kořen, tedy je ireducibilní.
 
Platí $x^2+x+2\EH P\Pz$, tedy $x^2\EH P -x-2\EH P 2x+1$ a $2x^2=x+2$.
 
Prvky jsou $\{0,
x^0\equiv1,\;
x^1\equiv x,\;
x^2\equiv2x+1,\;
x^3\equiv2x^2+x\equiv2x+2,\;
x^4\equiv2,\;
x^5\equiv2x,\;
x^6\equiv x+2,\;
x^7\equiv x^2+2x\equiv x+1\}$. Pro kontrolu spočítáme, že $x^8\equiv x^2+x\equiv1=x^0$.
 
Tedy $\ol x$ je primitivním prvkem $\GF(9)$.
Vždy existuje $P$, aby $\ol x$ bylo primitivním prvkem příslušného konečného tělesa.
Takové $P$ nazýváme \defined[polynom!primitivní]{primitivní polynom}.
 
\theorem
K libovolným $p\in\bbP$ a $n\in\N$ existuje $P\in Z_p[x]$ takový, že $\st P=n$ a $P$ je ireducibilní nad $Z_p$.
 
\proof
Už víme, že existuje $U=\GF\qlb{p^n}$, platí $\ch U=p$ a $Z_p$ je prvotěleso $U$.
Nechť $\alpha$ je primitivní prvek $U$.
Ukážeme, že $U=Z_p(\alpha)$.
 
\begin{description}
\ditem{$\sse$} Pokud $x=0$, je $x\in Z_p(\alpha)$, pokud $x\neq0$, je $x=\alpha^k$, tedy $x\in Z_p(\alpha)$.
\ditem{$\supseteq$} Platí $Z_p\cup\{\alpha\}\sse U$ a $Z_p(\alpha)$ je nejmenší takové, tedy $Z_p(\alpha)\sse U$.
\end{description}
 
Nutně $\alpha\neq0$, tedy $\alpha\in U\subast$ a $\alpha^{q-1}=1$, kde $q=p^n$.
Tedy $\alpha$ je kořenem polynomu $x^{q-1}-1\in Z_p[x]$ a $\alpha$ je algebraický nad $Z_p$.
Nechť $M_\alpha$ je minimální polynom prvku $\alpha$ nad $Z_p$.
Pak $M_\alpha$ je ireducibilní a je $\st M_\alpha=\st\alpha=\dim_{Z_p} Z_p(\alpha)=\dim_{Z_p} U=n$.
 
Hledaným polynomem je tedy minimální polynom primitivního prvku tělesa $\GF(q)$.
\QED
 
\xxxx{Eulerova funkce $\phi$}
 
\define
$\map\phi\N\N$, $\phi(n)$ je počet čísel z $\hatn n$, která jsou s $n$ nesoudělná.
 
\example
$\phi(1)=1$, $\phi(2)=1$, $\phi(3)=2$, $\phi(4)=2$, $\phi(5)=4$.
 
\theorem
Buďte $p,q\in\bbP$, $n,m\in\N$.
Pak
\begin{enumerate}
\item $\phi(p)=p-1$;
\item $\phi(p^n)=p^n-p^{n-1}=p^n\qlb{1-\frac1p}$;
\item $p\neq q$, pak $\phi(pq)=\phi(p)\phi(q)$;
\item $\gcd(m,n)=1$, pak $\phi(mn)=\phi(m)\phi(n)$.
\end{enumerate}
 
\proof
\begin{enumerate}
\item Speciální případ (2).
\item S $p^n$ jsou soudělné právě všechny násobky $p$, kterých je v $\hatn{p^n}$ právě $p^n/p$.
\item S $pq$ jsou nesoudělné právě všechny násobky $p$ a $q$, kterých je v $\hatn{pq}$ právě $q+p-1$.
\item Bez důkazu.
\end{enumerate}
\QED
 
\lemma
Nechť $k,\ell,m\in\N$.
Pak pokud $\gcd(k,m)=\gcd(\ell,m)=1$, platí $\gcd(k\ell,m)=1$.
 
\proof
Existují $u,v_{1,2}\in\Z$ tak, že $u_1k+v_1m=1$ a $u_2\ell+v_2m=1$.
Vynásobením rovností dostaneme $(u_1u_2)kl+(u_1v_2k+v_1u_2\ell+v_1v_2m)m=1$.
\QED
 
\theorem
Mějme $m\in\N$, $m\geq2$. Uvažujme $Z_m$ a definujme $G_m\supdot:=\set{\ol k}{\gcd(k,m)=1}\sse Z_m\supdot$.
Pak $G_m$ s operací násobení tříd je grupa o $\phi(m)$ prvcích.
 
\proof
Součin tříd pomocí předchozího lemmatu zůstane v $G$.
Taktéž $\gcd(1,m)=1$, tedy $G$ má jednotku $\ol 1$.
 
Pokud $\ol k\in G\supdot$, pak $(\EE u,v)(uk+vm=1)$,
 tedy $\ol u\ol k+\ol v\!\underbrace{\ol m}_{\ol 0}\!=\ol u\ol k=\ol 1$ a $\qlb{\ol k}^\1=\ol u$.
A z~definice Eulerovy funkce plyne, že $\abs{G_m}=\phi(m)$.
\QED
 
\theorem(Euler, Fermat)
Buďte $m\in\N$, $m\geq2$ a nechť $k\in\hatn m$ je nesoudělné s~$m$.
Pak $k^{\phi(m)}\EH m1$.
 
\proof
Pro $\ol k\in G_m\supdot$ je $\qlb{\ol k}^{\phi(m)}=\ol 1$, tedy $k^{\phi(m)}\EH m1$.
\QED
 
\theorem(Malá Fermatova věta)
Je-li $p\in\bbP$ a $k\in\hatn{p-1}$, pak $k^{p-1}\EH p1$ 
 
\proof
Speciální případ Eulerovy-Fermatovy věty pro $p\in\bbP$, a tedy $\phi(p)=p-1$.
\QED
 
\theorem(Velká Fermatova věta)
Pro $n\in\N$, $n>2$ neexistují přirozená $a,b,c$ taková, že $a^n+b^n=c^n$.