01ALG:Kapitola10: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(Založena nová stránka: \nothing{ \begin{document} } \xxx{Konečná tělesa} \xxxx{Konečná tělesa} \theorem(Wedderburn) Libovolné konečné těleso je komutativní. \theorem Libovolné kon...)
(Žádný rozdíl)

Verze z 24. 8. 2010, 13:52

\nothing{ \begin{document} }

\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^i.$$

\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(mn))$.

\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$.