Użytkownicy online
Naszą witrynę przegląda teraz 2 gości| Grupy |
 |
 |
 |
| Zadania II |
| Wpisany przez Joachim Jelisiejew |
| wtorek, 02 marca 2010 18:23 |
|
Źródło skryptu w texu. % File: grupy.tex % Created: nie lut 28 08:00 2010 C % Last Change: nie lut 28 08:00 2010 C % \documentclass[10pt]{article} \usepackage{amssymb} \usepackage{amsmath} \textwidth 16cm \textheight 24cm \oddsidemargin 0cm \topmargin 0pt \headheight 0pt \headsep 0pt \usepackage[polish]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{MnSymbol} \usepackage{import} % ---------------------------------------------------------------- \vfuzz4pt % Don't report over-full v-boxes if over-edge is small \hfuzz4pt % Don't report over-full h-boxes if over-edge is small % THEOREMS ------------------------------------------------------- \newtheorem{thm}{Twierdzenie}[section] \newtheorem{cor}[thm]{Wniosek} \newtheorem{lem}[thm]{Lemat} \newtheorem{defn}[thm]{Definicja} \newtheorem{tozs}[thm]{Tożsamość} \newtheorem{hyp}[thm]{Hipoteza} \newtheorem{useless}[thm]{} %\newenvironment{proof}{\noindent\textsc{Proof.}} {\nolinebreak[4]\hfill$\blacksquare$\\\par} % \font\sf=cmss10 \overfullrule0pt \def\Vrule{\smash{\vrule height7pt depth\baselineskip}} \def\Varule{\smash{\vrule height7pt depth3pt}} \def\Hrule #1{\Squeeze\multispan#1\hrulefill} \def\CompressMatrices{\ifmmode \def\quad{\hskip.5em\relax}\fi} \def\Squeeze{\noalign{\vskip-.5\baselineskip}} \def\rk{\operatorname {rank}} \def\lin{\operatorname {lin}} \def\dim{\operatorname{dim}} \def\ker{\operatorname{ker}} \def\det{\operatorname{det}} \def\im{\operatorname{im}} \def\id{\operatorname{id}} \def\Re{\operatorname{Re}} \def\Im{\operatorname{Im}} \def\dist{\operatorname{dist}} \def\Abs #1{\left\vert #1\right\vert} \def\Norm #1{\left\Vert #1\right\Vert} \def\cc #1{\overline{#1}} \def\ip#1#2{\langle #1,#2 \rangle} \def\dist{\operatorname{dist}} \def\ideal{\lhd} \def\lideal{<_l} \def\rideal{<_r} \def\gen#1{\langle #1 \rangle} \def\rann#1#2{\operatorname{r{.}ann}_{#1}(#2)} \def\lann#1#2{\operatorname{l{.}ann}_{#1}(#2)} \def\ann#1#2{\operatorname{ann}_{#1}(#2)} \def\mattwo#1#2#3#4{\left[\begin{array}{c c}#1 & #2 \\ #3 & #4\\\end{array}\right]} \def\tensor{\otimes} \def\rozw{$ $\\\textbf{Rozwiązanie}: \\} \def\dowod{$ $\\\textbf{Dowód}: \\} \def\deg{^{\circ}} \def\o{\operatorname{ord}} \subimport{../}{style} %\include{style} \def\source#1{\\Źródło: #1} \begin{document} \renewcommand{\thethm}{} \section{Grupą, mości panowie} \paragraph{Teoria} \begin{defn}Zbiór $G$ z określonym działaniem $\ast$ nazywamy \textbf{grupą} jeżeli \begin{enumerate} \item Dla wszystkich $a,b\in G$ jest $a\ast b\in G$, \item Dla wszystkich $a,b,c\in G$ jest $(a\ast b)\ast c = a\ast (b\ast c)$ -- kolejność wykonywania działań nie ma znaczenia \item Istnieje \textbf{``jedynka''} -- \textbf{element neutralny} działania, innymi słowy istnieje pewne $e\in G$ takie, że $$\hbox{ dla każdego } x\in G\ \ x\ast e = x \hbox{ i } e\ast x = x$$ \item Dla każdego elementu $a\in G$ istnieje taki element $b\in G$, że $$a\ast b = e \hbox { oraz } b\ast a = e$$ przypominam $e$ to element neutralny grupy. \end{enumerate} \end{defn} \paragraph{Podstawowe własności} wynikające wprost z definicji. Można je wrzucić do definicji, ale wtedy sprawdzanie, czy dany zbiór jest podgrupą byłoby trudniejsze. \begin{enumerate} \item Z grupie jest dokładnie jeden element neutralny\\ jeżeli $e,f\in G$ są elementami neutralnymi grupy $G$, to $e=f$. \dowod Niech $e,f$ będą elementami neutralnymi grupy $G$. Wtedy $$e = ef = f$$ \item W danej grupie $G$ dany element $a\in G$ ma dokładnie jedną odwrotność.\\ Innymi słowy, jeżeli elementy $b,c\in G$ są oba odwrotnościami $a$, to $b=c$. \dowod Niech $b,c$ będą odwrotnościami $a$, zaś $e$ będzie elementem neutralnym. Wtedy $$b = be = b(ac) = (ba)c = ec = c$$ \end{enumerate} \paragraph{Konwencje zapisu} -- jak pisać krócej.\\ Z pierwszej własności grup wynika, że w działaniu $\ast$ nie musimy używać nawiasów. Stosuje się konwencję \begin{itemize} \item $ab$ jako zapis $a\ast b$, \item $abc$ jako zapis $a\ast b \ast c$, \item $1$ jako zapis elementu neutralnego grupy $G$, \item $a^{-1}$ jako zapis elementu odwrotnego do elementu $a$. \item $ab^{-1}$ jako zapis $a\ast (b^{-1})$. \item Tożsamość $aa^{-1} = 1$ już wygląda zwyczajnie prawda? \end{itemize} \paragraph{Alternatywna konwencja} Zwłaszcza dla grup przemiennych często stosuje się zapis alternatywny ``dodawanie'' zamiast ``mnożenia''. \begin{itemize} \item $a + b$ jako zapis $a\ast b$, \item $0$ jako zapis elementu neutralnego grupy $G$, \item $-a$ jako zapis elementu odwrotnego do $a$. \item $a-b$ jako zapis $a + (-b)$. \item Tożsamość (przykładowa) $a - a = 0$. \end{itemize} \paragraph{Przykładowe grupy} \begin{enumerate} \item Dla danego zbioru $X$ bijekcje $X \rightarrow X$ (bijekcja to funkcja różnowartościowa i przyjmująca wszystkie możliwe wartości) -- działanie to składanie funkcji. \item Dla danego zbioru $X$ bijekcje $X \rightarrow X$, zachowujące dany punkt/zbiór punktów (Bijekcja $f:X \rightarrow X$ zachowuje podzbiór $Y \subset X$, jeżeli $f(Y) = Y$) -- działanie to składanie funkcji. \item Przekształcenia płaszczyzny zachowujące dany punkt. \item Przekształcenia płaszczyzny zachowujące odległości pomiędzy punktami (\emph{izometrie płaszczyzny}): w tym obroty, translacje, symetrie. . . (działanie = składanie przekształceń). \item Izometrie płaszczyzny zachowujące dany trójkąt/czworokąt. . . (działanie = składanie przekształceń). \item Zbiór liczb rzeczywistych/wymiernych/całkowitych z dodawaniem. \item Zbiór liczb rzeczywistych/wymiernych/całkowitych bez zera z mnożeniem. \item Zbiór $\left\{ 0, 1, \dots, n-1 \right\}$ z działaniem $a\ast b = a+b \mod n$. \item Dla liczby pierwszej $p$ zbiór $\left\{ 1, \dots, p-1 \right\}$ z mnożeniem $a\ast b = ab \mod p$. \item Dla dowolnej liczby $n$ zbiór liczb z $\left\{ 1,2,\dots, n \right\}$ które są względnie pierwsze z $n$, z mnożeniem $a\ast b = ab \mod n$. Ilość tych elementów oznacza się $\varphi(n)$. \end{enumerate} \paragraph{Dodatkowe potrzebne definicje} \begin{enumerate} \item \begin{defn} Jeżeli $G$ jest grupą, oraz $H \subset G$ jest grupą ze względu na to samo działanie co $G$, to $H$ nazywamy \textbf{podgrupą} grupy $G$. \end{defn} Np. grupa liczb całkowitych z $+$ jest podgrupą grupy liczb rzeczywistych z $+$. \item \begin{defn} Jeżeli $G$ jest grupą i $G$, jako zbiór jest skończony to mówimy, że grupa $G$ jest \textbf{skończona}. W tym przypadku ilość elementów zbioru $G$ oznaczamy (standardowo) $|G|$. \end{defn} \item Jeżeli dla każdych elementów $a,b$ grupy $G$ zachodzi $a\ast b = b\ast a$, to mówimy, że grupa jest \textbf{przemienna}. \item Dla danego elementu $a$ grupy skończonej $G$ definiujemy \textbf{rząd} $a$ jako najmniejsze $n\in \mathbb{Z}_+$ takie, że $$a^n = 1 \hbox{ w grupie }G$$ Rząd elementu oznaczamy $\o(a,G)$, lub $\o(a)$, albo wręcz $o(a)$. \end{enumerate} \paragraph{Wreszcie jakaś teoria} \begin{enumerate} \item \begin{lem} Jeżeli $G$ jest grupą z działaniem $\ast$ oraz $H \subset G$, przy czym zachodzi $$\forall_{a,b\in H}\ \ a\ast b \in H$$ $$\forall_{a\in H}\ \ a^{-1} \in H$$ to $H$ jest podgrupą $G$. \end{lem} \dowod Własności 1, 2 i 4 grupy są spełnione, pozostaje wykazać własność 3, czyli istnienie elementu neutralnego.\\ Weźmy dowolny element $a\in H$. Wiemy, że $a^{-1}\in H$, a więc także $e = aa^{-1}\in H$. \item \begin{thm}[Lagrange] Jeżeli $G$ jest grupą skończoną, zaś $H$ jest podgrupą grupy $G$, to $$|H|\ \ |\ \ |G|$$ \end{thm} \dowod \begin{enumerate} \item Dla każdego $a\in G$ definiujemy zbiór $$aH := \left\{ ah\ \ |\ \ h\in H \right\}$$ \item Rozważmy $a, b\in G$. Chcemy udowodnić, że $$aH = bH \hbox{ albo } aH \cap bH = \emptyset$$ Załóżmy, że $aH \cap bH \neq \emptyset$, niech $c\in aH \cap bH$. Z definicji istnieją takie $h_1, h_2\in H$, że $$ah_1 = c = bh_2$$ Stąd $ah_1 = bh_2$, więc $a = ah_1h_1^{-1} = bh_2h_1^{-1}\in bH$.\\ Weźmy dowolny element $aH$. Ma on postać $ah$ dla pewnego $h\in H$. Mamy $$ah = (bh_2h_1^{-1})h = b(h_2h_1^{-1}h) \in bH$$ stąd $aH \subseteq bH$, analogicznie $bH \subseteq aH$, a więc $aH = bH$. \item Widzimy, że grupa $G$ rozpada się na skończoną liczbę rozłącznych podzbiorów: $a_1H, \dots, a_nH$. Jeżeli udowodnimy, że każdy z tych podzbiorów ma $|H|$ elementów, to teza będzie dowiedziona, gdyż $$|G| = |a_1H| + \dots + |a_nH| = n|H|$$ \item Weźmy dowolny zbiór $$aH = \left\{ ah\ \ |\ \ h\in H \right\}$$ zbiór ten ma $|H|$, jeżeli elementy $ah_1, ah_2$ są różne dla różnych $h_1, h_2\in H$. Załóżmy, że $$ah_1 = ah_2 \hbox{ stąd } h_1 = a^{-1}ah_1 = a^{-1}ah_2 = h_2$$ dowód jest zakończony. \end{enumerate} \item Dla danej grupy $G$ i $a\in G$ zbiór postaci $\left\{ 1, a, a^2, \dots, a^{\o(a) - 1} \right\}$ jest grupą; nazywamy go grupą generowaną przez $a$ i oznaczamy $\gen{a}$. \dowod \begin{enumerate} \item Uzasadnię na początek, że $\gen{a}$ jest grupą. Korzystając z lematu wystarczy pokazać własności 1 i 4 grupy.\\ Niech $a^k, a^l\in \gen{a}$. Chcę pokazać, że $a^{k+l}$ jest pewnym elementem $\gen{a}$.\\ Podzielmy z resztą; niech $q,r\in \mathbb{Z}$, $0\leq r< \o(a)$ będą takie, że $k+l = q\o(a) + r$. $$a^{k+l} = a^{q\o(a) + r} = (a^{\o(a)})^qa^r = 1^qa^r = a^r \in \gen{a}$$ gdyż $r\in \left\{ 0, 1, \dots, \o(a) -1 \right\}$. \item Pozostaje uzasadnić, że elementy $1,a,\dots,a^{\o(a) -1}$ są parami różne.\\ Niech $a^k = a^l$ dla $\o(a) > l > k$. Wtedy $$1 = a^{-k}a^k = a^{-k}a^l = a^{l-k}$$ sprzeczność z definicją $\o(a)$. \end{enumerate} \item \begin{cor} Jeżeli $a$ jest elementem grupy skończonej $G$, to $$\o(a, G)\ |\ |G|$$ $$a^{|G|} = 1 \hbox{ w grupie G}$$ \end{cor} \dowod \begin{enumerate} \item \emph{Warto przypomnieć definicję rzędu}. \item Wystarczy uzasadnić, że $\o(a, G)\ |\ |G|$, gdyż wtedy $a^{|G|} = (a^{\o(a)})^{\dots} = 1^{\dots} = 1$ w grupie $G$. \item Podzbiór $$\gen{a} = \left\{ 1,a,\dots,a^{\o(a)-1} \right\}$$ jest podgrupą $G$, mającą $\o(a)$ elementów. Podzielność z tezy wniosku wyniknie wprost z tw. Lagrange. \end{enumerate} \item \begin{cor}[Fermat] Jeżeli $p$ jest liczbą pierwszą zaś $a$ jest całkowite dodatnie, to $$p | a^p - a$$ \end{cor} \dowod Przypadek $p|a$ jest banalny. Można uznać, że $a$ względnie pierwsze z $p$. Z powyższego wniosku otrzymujemy $p | a^{p-1} - 1$, a stąd tezę. \item \begin{cor}[Euler] Jeżeli liczby naturalne $n, a$ są względnie pierwsze, to $$n | a^{\varphi(n)} - 1$$ \end{cor} \dowod Zastosowanie wniosku do grupy liczb z $\left\{ 1,2,\dots, n \right\}$ względnie pierwszych z $n$ (trzeba udowodnić, że tworzą one grupę!). $\varphi(n)$ jest zdefiniowane wyżej. \item \begin{cor}[Lemat o rzędzie (słabsza forma)] Jeżeli $p$ jest liczbą pierwszą, zaś $a$ jest liczbą całkowitą względnie pierwszą z $p$ oraz $\o(a, p)$ oznacza rząd $a$ względem $p$ (patrz kółko o rzędzie, definicja jest zgodna z powyższą) to $$\o(a, p)\ |\ p-1$$ \end{cor} \dowod Bezpośrednie skorzystanie z wniosku dla grupy $\left\{ 1,2, \dots, p-1 \right\}$ z mnożeniem $\mod p$. \end{enumerate} \paragraph{Trochę teorii z * (dużo * na tym kółku :)} \begin{enumerate} \item \begin{lem} Jeżeli grupa $G$ jest skończona i przemienna, to dla dowolnych elementów $a, b\in G$ w grupie $G$ istnieje element mający rząd $NWW(\o(a), \o(b))$. \end{lem} \dowod \begin{enumerate} \item Niech $a, c\in G$, niech $d = NWD(\o(a),\o(c))$. Element $c^d$ ma rząd $\frac{o(c)}{d}$ (sprawdź to!), więc $NWD(\o(c^d), \o(a)) = 1$, $NWW(\o(c^d), \o(a)) = NWW(\o(a), \o(c))$.\\ Oznaczam $b:=c^d$. Udowodnię, że element $ab$ ma szukany rząd $NWW(\o(a), \o(b))$. \item Na początek udowodnię, że $$\gen{a} \cap \gen{b} = 1$$ Niech $g\in \gen{a} \cap \gen{b}$. Z wniosku z tw. Lagrange $$\o(g)\ \ |\ \ |\gen{a}| = \o(a)$$ $$\o(g)\ \ |\ \ |\gen{b}| = \o(b)$$ a więc $\o(g)\ \ |\ \ NWD(\o(a), \o(b)) = 1$. Tym samym $g = g^1 = g^{\o(g)} = 1$.\\ Oczywiście $1\in \gen{a} \cap \gen{b}$ (dlaczego?). \item Niech dla zwięzłości $O := \o(ab)$, więc $(ab)^O = 1$. Skoro grupa jest przemienna, to $$1 = (ab)^O = a^Ob^O$$ Popatrzmy na element $a^O$. $a^O\in \gen{a}$ oraz $a^O = (b^{O})^{-1} = b^{-O} \in \gen{b}$. A więc $$a^O\in \gen{a}\cap\gen{b} \hbox{ stąd } a^O = 1 \hbox{ więc } \o(a)\ |\ O$$ Analogicznie $\o(b)\ |\ O$, stąd $$NWW(\o(a), \o(b))\ |\ O$$ \item Obliczam $$(ab)^{NWW(\o(a),\o(b))} = a^{NWW(\o(a),\o(b)}b^{NWW(\o(a),\o(b)} = 1\ast 1 = 1$$ stąd wynika $O = \o(ab)\ |\ NWW(\o(a),\o(b))$, co w połączeniu z $$NWW(\o(a), \o(b))\ |\ O$$ daje $O = NWW(\o(a), \o(b))$, czyli tezę. \end{enumerate} \item \begin{thm}[Istnienie generatora] Jeżeli $p$ jest liczbą pierwszą, to grupa $$\left\{ 1,2,\dots, p-1 \right\}$$ z mnożeniem $\mod p$ jest grupą generowaną przez pewien element $g$, innymi słowy istnieje takie $g$, że liczby $\left\{ g,g^2,\dots, g^{p-1} \right\}$ dają parami różne reszty z dzielenia przez $p$. \end{thm} \dowod \begin{enumerate} \item Grupa $G:=\left\{ 1,2,\dots,p-1 \right\}$ ma skończenie wiele elementów, weźmy element $a$ największego rzędu $M$. Jeżeli udowodnimy, że $M = p-1$, to grupa cykliczna $\gen{a}$ będzie miała $p-1$ elementów, więc będzie równa grupie $G$. \item Weźmy dowolny element $b\in G$. Jeżeli $\o(b)\ \not|\ \o(a)$, to z lematu istnieje takie $g\in G$, że $$\o(g) = NWW(\o(a), \o(b)) > \o(a)$$ sprzeczność z określeniem $a$ jako elementu o największym rzędzie. Tak więc $$\hbox{ dla każdego }b\in G\ \o(b)\ |\ \o(a)=M$$ $$\hbox{ dla każdego }b\in G\ b^M = 1.$$ \item Chciałbym teraz zdefiniować, co to jest wielomian o współczynnikach w $\mathbb{Z}_p := \left\{ 0, 1, \dots, p-1 \right\}$. Niestety do tego potrzeba mi jeszcze trochę definicji.\\ \item \begin{defn} Zbiór $F$ z działaniami $+$ i $\cdot$ taki, że \begin{enumerate} \item $F$ jest grupą przemienną ze względu na działanie $+$. Będziemy oznaczać działanie tej grupy w konwencji dodawania, tj. element neutralny oznaczymy $0$ itd. \item $F\backslash\left\{ 0 \right\}$ jest grupą przemienną ze względu na $\cdot$. \item Zachodzą prawa rozdzielności: $$a(b+c) = ab+ac$$ $$(b+c)a = ba+ca$$ \end{enumerate} nazywamy \textbf{ciałem}. \end{defn} Liczby rzeczywiste są ciałem, liczby wymierne są ciałem. \item \begin{lem} Dla dowolnej liczby pierwszej $p$ zbiór $$\mathbb{Z}_p = \left\{ 0, 1, \dots, p-1 \right\}$$ z działaniami $+ \mod p$ i $\cdot \mod p$ jest ciałem. \end{lem} \dowod Udowodniliśmy, że $\mathbb{Z}_p$ z działaniem $+$ jest grupą, oraz $\mathbb{Z}_p\backslash\left\{ 0 \right\}$ z działaniem $\cdot \mod p$ jest grupą. Pozostaje przeliczyć prawa rozdzielności (a raczej jedno z nich, bo w przypadku przemiennym one są równoważne), czyli ``udowodnić'', że $$a(b+c) \equiv ab + ac \mod p$$ co jest oczywiste. \item Tak jak rozważamy wielomiany o współczynnikach w $\mathbb{R}$ (niektórzy również $\mathbb{C}$), tak samo możemy rozważyć wielomiany o współczynnikach z dowolnego ciała, w szczególności z $\mathbb{Z}_p$. \item \begin{thm}[B\'ezout] Jeżeli wielomian $P(x)$ o współczynnikach z ciała, spełnia równość $P(a) = 0$ dla elementu ciała $a$, to $$P(x) = (x-a)Q(x)$$ dla pewnego wielomianu $Q(x)$ o współczynnikach z ciała. \end{thm} \dowod Identyczny jak w klasycznym twierdzeniu. \item \begin{cor}[Langange] Wielomian $W(x)$ stopnia $n$ może mieć co najwyżej $n$ pierwiastków, licząc z krotnościami. \end{cor} \dowod Jest to wniosek z tw. B\`ezout, dowód analogiczny jak dla wielomianów nad $\mathbb{R}$. \item \textbf{Dokończenie dowodu} Przypominam: $G = \left\{ 1,2,\dots, p-1 \right\}$ i $$\hbox{ dla każdego }b\in G b^M = 1.$$ Wielomian $W(x):=x^M -1$ o współczynnikach z ciała $\mathbb{Z}_p$ ma pierwiastki $1, 2, \dots, p-1$. Z tw. Lagrange wynika, że $$M =\operatorname{deg} W(x) \geq p-1$$ co było do udowodnienia. \end{enumerate} \end{enumerate} \end{document} |
| Poprawiony: czwartek, 04 marca 2010 15:24 |
