Użytkownicy online
Naszą witrynę przegląda teraz 2 gości| Fibonacci, macierze i pierścienie |
 |
 |
 |
| Zadania II |
| Wpisany przez Joachim Jelisiejew |
| niedziela, 14 marca 2010 13:49 |
|
Źródło zadań w texu. % File: zadania.tex % Created: wto mar 09 06:00 2010 C % Last Change: wto mar 09 06: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{import} %\usepackage{MnSymbol} % ---------------------------------------------------------------- \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]{} \newtheorem{problem}[thm]{Zadanie} \newenvironment{proof}{\noindent\textsc{Dowód.}} {\nolinebreak[4]\hfill$\blacksquare$\\\par} \newenvironment{sol}{\noindent\textsc{Rozwiązanie. }} {\par} \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\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\deg{^{\circ}} \def\source#1{\\Źródło: #1} \subimport{../}{style} \begin{document} \renewcommand{\thethm}{} \section{Ciąg Fibonacciego} \paragraph{Pierścienie} \begin{enumerate} \item \begin{defn} Pierścieniem (z jedynką) będę nazywać zbiór $R$, z określonymi działaniami $+$ i $\cdot$ takimi, że \begin{enumerate} \item $R$ jest grupą \textbf{przemienną} ze względu na $+$, której element neutralny oznaczam $0$. \item Dla wszystkich $a,b\in R$ mamy $a\cdot b\in R$. \item Działanie $\cdot$ jest łączne, tj. $a\cdot(b\cdot c) = (a\cdot b)\cdot c$ dla wszystkich $a,b,c\in R$. \item Istnieje element neutralny mnożenia $e\in R$: $$ea = ae = a$$ dla wszystkich $a\in R$. Element ten jest jedyny (dowód jak w grupach, patrz poprzednie kółko), oznaczamy go $1$ i nazywamy jedynką. \item Działanie $\cdot$ jest rozdzielne względem $+$: $$(a+b)c = ac + bc$$ $$c(a+b) = ca + cb$$ dla wszystkich $a,b,c\in R$. \end{enumerate} \end{defn} Dla każdego $a\in R$ zachodzi $$a\cdot 0 = a\cdot (0 + 0) = a\cdot 0 + a\cdot 0$$ odejmujemy $a\cdot 0$ stronami i otrzymujemy $0 = a\cdot 0$.\\ Dla każdych $a,b\in R$ zachodzi $$-ab = (-a)b = a(-b)$$ Dowód: $ab - ab = 0 = a0 = a(b + (-b)) = ab + a(-b)$, stąd $-ab = a(-b)$. Analogicznie $ab - ab = 0 = (a + (-a))b = ab + (-a)b$, więc $-ab = (-a)b$. \item Tak naprawdę warunki na bycie pierścieniem są bardzo słabe i większość zbiorów z działaniami, jakie znane są w liceum jest pierścieniami: liczby rzeczywiste, wymierne, całkowite, wielomiany o współczynnikach np. rzeczywistych itd. \item \begin{defn} Niech $R$ będzie pierścieniem. Jeżeli dla elementu $a\in R$ istnieje $b\in R$ takie, że $$a\cdot b = b\cdot a = 1$$ to powiemy, że element $a$ jest odwracalny. \item \begin{defn} Niech $R$ będzie pierścieniem. Powiemy, że $R$ jest przemienny, jeżeli $$a\cdot b= b\cdot a$$ dla wszystkich $a,b\in R$. \end{defn} \end{defn} \end{enumerate} \paragraph{Teoria macierzy} \begin{enumerate} \item \begin{defn} Macierzą o wymiarach $2\times 2$ o elementach ze pierścienia $R$ nazywamy układ $2\cdot 2=4$ liczb $a,b,c,d\in R$ zapisany w postaci $$\mattwo{a}{b}{c}{d}$$ Zbiór wszystkich macierzy oznaczamy $\mathbb{M}_2(R)$.\\ \emph{Na początku, jeżeli wygląda to zbyt okropnie weź $R = \mathbb{R}$, czyli macierze o wyrazach rzeczywistych.} \end{defn} \item Macierze z danego zbioru możemy dodawać: $$\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} + \mattwo{b_{11}}{b_{12}}{b_{21}}{b_{22}} = \mattwo{a_{11}+b_{11}}{a_{12}+b_{12}}{a_{21}+b_{21}}{a_{22}+b_{22}}$$ i mnożyć, nieco bardziej skomplikowanie (polecam http://pl.wikipedia.org/wiki/Mnożenie\_macierzy): $$\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}}\cdot \mattwo{b_{11}}{b_{12}}{b_{21}}{b_{22}} = \mattwo{a_{11}b_{11} + a_{12}b_{21}}{a_{11}b_{12}+a_{12}b_{22}}{a_{21}b_{11}+a_{22}b_{21}}{a_{21}b_{12}+a_{22}b_{22}}$$ dodatkowo możemy na macierzach zdefiniować mnożenie przez stałą $r\in R$. $$r\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} := \mattwo{r}{0}{0}{r}\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} = \mattwo{ra_{11}}{ra_{12}}{ra_{21}}{ra_{22}}$$ \item \begin{thm} Dla dowolnego pierścienia $R$ macierze $\mathbb{M}_2(R)$ tworzą pierścień z działaniami $+$ i $\cdot$. Elementem neutralnym tego pierścienia jest macierz $$I:=\mattwo{1}{0}{0}{1}.$$ Jeżeli ponadto pierścień $R$ jest przemienny, to zachodzi $$\mattwo{r}{0}{0}{r}A = A\mattwo{r}{0}{0}{r}A$$ dla wszystkich macierzy $A\in \mathbb{M}_2(R)$. \end{thm} \begin{proof} Aby udowodnić, że macierze są pierścieniem wystarczy przeliczyć wszystkie własności pierścienia. Podobnie można policzyć, że $I$ jest jedynką.\\ Przeliczę tylko ostatnie stwierdzenie. Niech $A = \mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} \in \mathbb{M}_2(R)$ oraz $r\in R$ wtedy $$\mattwo{r}{0}{0}{r}\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} = \mattwo{ra_{11}}{ra_{12}}{ra_{21}}{ra_{22}} = \mattwo{a_{11}r}{a_{12}r}{a_{21}r}{a_{22}r} = \mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}}\mattwo{r}{0}{0}{r}$$ \end{proof} \item Aby uprościć robotę nieinteresujące mnie elementy macierzy będę oznaczać $*$. Nigdy nie będę ich wyliczać, \textbf{ich wartość nie będzie miała wpływu na przekształcenia}. Przykład: $$\mattwo{1}{*}{0}{*} = I = \dots$$ elementy $*$ należy rozumieć jako elementy macierzy sąsiedniej (tutaj $I$). \end{enumerate} \paragraph{Teoria ciągu Fibonacciego} \begin{enumerate} \item \begin{defn} Ciągiem \textbf{Fibonacciego} nazywamy ciąg rekurencyjny $(F_n)$ dany równaniami: $$F_0 = 0,\ F_1=1,\ F_n = F_{n-1} + F_{n-2}\hbox{ dla }n\geq 2$$ Kolejne wyrazy ciągu Fibonacciego to: \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|} \hline $n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$\\ \hline $F_n$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ & $21$\\ \hline \end{tabular} Dla wygody zdefiniujemy również wyrazy o indeksach ujemnych, tak, żeby zachowana była własność $F_n = F_{n-1} + F_{n-2}$. W tym celu należy wziąć $F_{-n} = (-1)^{n+1}F_n$.\\ \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline $n$ & $-5$ & $-4$ & $-3$ & $-2$ & $-1$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ &$8$\\ \hline $F_n$ & $5$ & $-3$ & $2$ & $-1$ & $1$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ &$21$\\ \hline \end{tabular} \end{defn} Macierzą ciągu Fibonacciego nazywamy macierz $$\mathbb{F} := \mattwo{1}{1}{1}{0}. \hbox{ Jest ona odwracalna w }\mathbb{M}_2(\mathbb{Z})\hbox{, jej odwrotnością jest } \mathbb{F}^{-1} = \mattwo{0}{1}{1}{-1}$$ \textbf{Równanie:} Bezpośrednio przeliczamy, że $$\mathbb{F}^2 - \mathbb{F} - I = 0\hbox{ stąd wynika po podzieleniu } \mathbb{F} = \frac{1}{\mathbb{F} - I}$$ \textbf{Ważna uwaga/metatwierdzenie}: Jeżeli rozpatrujemy tylko wyrażenia zawierające $\mathbb{F}$ oraz $rI$, gdzie $r\in \mathbb{R}$, to każde dwa takie wyrażenia będą przemienne ze sobą. \item \begin{lem}[Postać macierzowa ciągu] Dla każdego $n$ całkowitego $$\mathbb{F}^n = \mattwo{1}{1}{1}{0}^n = \mattwo{F_{n+1}}{F_n}{F_n}{F_{n-1}}$$ \end{lem} \begin{proof} Bezpośrednio przeliczamy, że dla $n=0$ i $n=1$ równość jest prawdziwa. Przeprowadzamy indukcję po $n$ rosnącym i malejącym. Przykładowo -- krok indukcyjny w indukcji po $n$ rosnącym $$\mathbb{F}^{n+2} = \mathbb{F}^n\mathbb{F}^2 = \mathbb{F}^n(\mathbb{F} + I) = \mathbb{F}^{n+1} + \mathbb{F}^n = \mattwo{F_{n+2}}{F_{n+1}}{F_{n+1}}{F_n} + \mattwo{F_{n+1}}{F_n}{F_n}{F_{n-1}} = $$ $$\mattwo{F_{n+2} + F_{n+1}}{F_{n+1}+F_n}{F_{n+1} + F_n}{F_n + F_{n-1}} = \mattwo{F_{n+3}}{F_{n+2}}{F_{n+2}}{F_{n+1}}$$ co było do udowodnienia. Ten dowód korzysta bardzo mocno ze struktury algebraicznej macierzy. \end{proof} \end{enumerate} \paragraph{Własności ciągu Fibonacciego -- zadania prostsze} \begin{enumerate} \item Uzasadnić (elementarnie jest prościej :), że każde dwa kolejne wyrazy ciągu Fibonacciego są są względnie pierwsze. \item Uzasadnić, że dla wszystkich liczb naturalnych $n,m$ zachodzi $$F_{n+1}F_m + F_nF_{m-1} = F_{m+n}$$ \item W szczególności dla wszystkich liczb naturalnych $n$ zachodzi $$F_n^2 + F_{n+1}^2 = F_{2n+1}$$ \item Niech $n$ będzie liczbą naturalną. Uzasadnić, że $$F_0 + F_1 + \dots + F_n = F_{n+2} - 1$$ \item Niech $n$ będzie liczbą naturalną. Uzasadnić, że $$F_1 + F_3 + F_5 + \dots + F_{2n-1} = F_{2n}$$ \item Niech $n$ będzie liczbą naturalną. Udowodnić, że $$\sum_{i=1}^n iF_i = nF_{n+2} - F_{n+3} + 2$$ \item Uzasadnić, że dla wszystkich $n$ naturalnych zachodzi $$F_{n+1}F_{n-1} - F_n^2 = (-1)^n$$ \end{enumerate} \paragraph{Dalsze własności pierścieni} \begin{enumerate} \item \begin{defn} Niech $R$ będzie pierścieniem. Podzbiór $J$ pierścienia $R$ nazywamy ideałem jeżeli: \begin{enumerate} \item $I$ jest podgrupą przemienną ze względu na $+$. \item Dla dowolnego $r\in R, i\in I$ zachodzi $$r\cdot i\in I\hbox{ oraz }i\cdot r\in I$$ \end{enumerate} \end{defn} $J$ jest ideałem $R$ oznaczamy przez $J\ideal R$. \item Pojęcie ideału rozszerza pojęcie kongruencji:\\ Piszemy $a \equiv b \mod I$ jeżeli $b-a\in I$. Załóżmy, że $$a\equiv b \mod I,\ \ c\equiv d\mod I$$ Wtedy (m. in.) $$b\equiv a\mod I$$ $$a + c \equiv b + d \mod I$$ $$a - c \equiv b - d \mod I$$ $$ac \equiv bd \mod I$$ Udowodnię dla przykładu ostatnią (najtrudniejszą) własność.\\ $$a \equiv b\mod I \Rightarrow a-b\in I \Rightarrow (a-b)c\in I$$ $$c \equiv d\mod I \Rightarrow d-c\in I \Rightarrow b(d-c)\in I$$ $$(a-b)c\in I,\ b(d-c)\in I \Rightarrow ac - bd = (a-b)c - b(d-c)\in I \Rightarrow ac \equiv bd \mod I$$ \item Naturalne w tym kontekście jest zauważenie, że dla ustalonego $n\in \mathbb{Z}$ zbiór postaci $$I_n:=\left\{ kn\ |\ k\in \mathbb{Z}\right\}$$ jest ideałem w $\mathbb{Z}$. Kongruencje $\mod I_n$ to znane nam kongruencje $\mod n$. \item \begin{lem} Rozważmy macierze $\mathbb{M}_2(R)$ i niech $I\ideal R$. Zdefiniujmy $$\mathbb{M}_2(I):=\left\{ \mattwo{a}{b}{c}{d}\in R\ |\ a,b,c,d\in I\right\}$$ Wtedy $\mathbb{M}_2(I)$ jest ideałem w $\mathbb{M}_2(R)$. \end{lem} \begin{proof} Na początku udowodnimy, że $\mathbb{M}_2(I)$ jest podgrupą przemienną. Wystarczy (patrz kółko o grupach) udowodnić, że $$A,B\in \mathbb{M}_2(I) \Rightarrow A+B\in \mathbb{M}_2(I)\hbox{ oraz }-A\in \mathbb{M}_2(I)$$ Rozważmy $A:=\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}}, B:=\mattwo{b_{11}}{b_{12}}{b_{21}}{b_{22}}$. Z definicji $\mathbb{M}_2(I)$ wynika, że $a_i,b_i\in I$. W związku z tym również (z własności ideału $I$): $$a_{11} - b_{11}\in I,a_{12} - b_{12}\in I\dots$$ a stąd $$A-B = \mattwo{a_{11}-b_{11}}{a_{12}-b_{12}}{a_{21}-b_{21}}{a_{22}-b_{22}} \in \mathbb{M}_2(I)$$ z definicji $\mathbb{M}_2(I)$. $-A\in \mathbb{M}_2(I)$ udowadniamy analogicznie.\\$ $\\ Pozostaje udowodnić drugą własność ideałów. Rozważmy dowolną $C = \mattwo{c_{11}}{c_{12}}{c_{21}}{c_{22}}\in \mathbb{M}_2(R)$ i dowolną $\mattwo{i_{11}}{i_{12}}{i_{21}}{i_{22}}\in \mathbb{M}_2(R)$: $$\mattwo{c_{11}}{c_{12}}{c_{21}}{c_{22}}\mattwo{i_{11}}{i_{12}}{i_{21}}{i_{22}} = \mattwo{c_{11}i_{11} + c_{12}i_{21}}{c_{11}i_{12}+c_{12}i_{22}}{c_{21}i_{11}+c_{22}i_{21}} {c_{21}i_{12}+c_{22}i_{22}}$$ Widać, że np. w pierwszej komórce $i_{11}\in I$ stąd $c_{11}i_{11}\in I$, analogicznie $c_{12}i_{21}\in I$, więc $c_{11}i_{11} + c_{12}i_{21}\in I$. Pozostałe wartości również należą do $I$, więc cała macierz należy do $\mathbb{M}_2(I)$ (z definicji $\mathbb{M}_2(I)$).\\ Drugą część drugiej własności udowadniamy analogicznie. \end{proof} \end{enumerate} \paragraph{Własności ciągu Fibonacciego -- zadania trudniejsze} \begin{enumerate} \item Uwaga: poniższe dwa zadania można zrobić elementarnie, korzystając z tożsamości $F_{n+1}F_m + F_nF_{m-1} = F_{m+n}$ oraz z lematu w zadaniu drugim, ale dowody są (moim zdaniem) \emph{trudniejsze} do wymyślenia i \emph{mniej naturalne}, oczywiście z dokładnością do pewnego zrozumienia pojęć abstrakcyjnych. \item \begin{thm}[*] Jeżeli liczby $n,m\in \mathbb{Z}_+$ oraz $n\ |\ m$ to $$F_n\ |\ F_m$$ \end{thm} \item \begin{thm}[*] Dla wszystkich liczb naturalnych $n,m$ zachodzi równość $$NWD(F_n, F_m) = F_{NWD(n,m)}$$ \end{thm} \item \begin{thm}[**Wzór Bineta] Niech $\phi_1 := \dfrac{1 + \sqrt{5}}{2}, \ \phi_2 := \dfrac{1 - \sqrt{5}}{2}$, innymi słowy, niech będą to pierwiastki równania $x^2 - x - 1 = 0$. Wtedy $$F_n = \frac{1}{\sqrt{5}}(\phi_1^n - \phi_2^n)$$ dla wszystkich liczb całkowitych $n$. \end{thm} \end{enumerate} \end{document}
Źródło rozwiązań w texu. % File: zadania.tex % Created: wto mar 09 06:00 2010 C % Last Change: wto mar 09 06: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{import} %\usepackage{MnSymbol} % ---------------------------------------------------------------- \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]{} \newtheorem{problem}[thm]{Zadanie} \newenvironment{proof}{\noindent\textsc{Dowód.}} {\nolinebreak[4]\hfill$\blacksquare$\\\par} \newenvironment{sol}{\noindent\textsc{Rozwiązanie. }} {\par} \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\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\deg{^{\circ}} \def\source#1{\\Źródło: #1} \subimport{../}{style} \begin{document} \renewcommand{\thethm}{} \section{Ciąg Fibonacciego} \paragraph{Pierścienie} \begin{enumerate} \item \begin{defn} Pierścieniem (z jedynką) będę nazywać zbiór $R$, z określonymi działaniami $+$ i $\cdot$ takimi, że \begin{enumerate} \item $R$ jest grupą \textbf{przemienną} ze względu na $+$, której element neutralny oznaczam $0$. \item Dla wszystkich $a,b\in R$ mamy $a\cdot b\in R$. \item Działanie $\cdot$ jest łączne, tj. $a\cdot(b\cdot c) = (a\cdot b)\cdot c$ dla wszystkich $a,b,c\in R$. \item Istnieje element neutralny mnożenia $e\in R$: $$ea = ae = a$$ dla wszystkich $a\in R$. Element ten jest jedyny (dowód jak w grupach, patrz poprzednie kółko), oznaczamy go $1$ i nazywamy jedynką. \item Działanie $\cdot$ jest rozdzielne względem $+$: $$(a+b)c = ac + bc$$ $$c(a+b) = ca + cb$$ dla wszystkich $a,b,c\in R$. \end{enumerate} \end{defn} Dla każdego $a\in R$ zachodzi $$a\cdot 0 = a\cdot (0 + 0) = a\cdot 0 + a\cdot 0$$ odejmujemy $a\cdot 0$ stronami i otrzymujemy $0 = a\cdot 0$.\\ Dla każdych $a,b\in R$ zachodzi $$-ab = (-a)b = a(-b)$$ Dowód: $ab - ab = 0 = a0 = a(b + (-b)) = ab + a(-b)$, stąd $-ab = a(-b)$. Analogicznie $ab - ab = 0 = (a + (-a))b = ab + (-a)b$, więc $-ab = (-a)b$. \item Tak naprawdę warunki na bycie pierścieniem są bardzo słabe i większość zbiorów z działaniami, jakie znane są w liceum jest pierścieniami: liczby rzeczywiste, wymierne, całkowite, wielomiany o współczynnikach np. rzeczywistych itd. \item \begin{defn} Niech $R$ będzie pierścieniem. Jeżeli dla elementu $a\in R$ istnieje $b\in R$ takie, że $$a\cdot b = b\cdot a = 1$$ to powiemy, że element $a$ jest odwracalny. Odwrotność elementu $a$ oznaczamy wtedy $a^{-1}$.\\ \end{defn} \emph{Uwaga: Jeżeli pierścień nie jest przemienny, to odwrotności nie piszemy jako $\frac{1}{a}$, żeby nie popełnić błędu: $b\frac{1}{a} = \frac{b}{a} = \frac{1}{a}b$. Błąd polega na tym, że środkowy obiekt $b/a$ nie jest zdefiniowany.} \item \begin{defn} Niech $R$ będzie pierścieniem. Powiemy, że $R$ jest przemienny, jeżeli $$a\cdot b= b\cdot a$$ dla wszystkich $a,b\in R$. \end{defn} \item \begin{lem}[Suma ciągu geometrycznego] Niech $a\in R$. Załóżmy, że element $1-a$ pierścienia $R$ jest odwracalny. Zachodzi wtedy $$1 + a + \dots + a^{n-1} = (a^n - 1)(a-1)^{-1}$$ \end{lem} \begin{proof} Mamy $$(1 + a + \dots + a^{n-1})(a-1) = a^n - 1$$ domnażamy z prawej strony przez $(a-1)^{-1}$: $$1 + a + \dots + a^{n-1} = (1 + a + \dots + a^{n-1})(a-1)(a-1)^{-1} = (a^n - 1)(a-1)^{-1}$$ \end{proof} \end{enumerate} \paragraph{Teoria macierzy} \begin{enumerate} \item \begin{defn} Macierzą o wymiarach $2\times 2$ o elementach ze pierścienia $R$ nazywamy układ $2\cdot 2=4$ liczb $a,b,c,d\in R$ zapisany w postaci $$\mattwo{a}{b}{c}{d}$$ Zbiór wszystkich macierzy oznaczamy $\mathbb{M}_2(R)$.\\ \emph{Na początku, jeżeli wygląda to zbyt okropnie weź $R = \mathbb{R}$, czyli macierze o wyrazach rzeczywistych.} \end{defn} \item Macierze z danego zbioru możemy dodawać: $$\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} + \mattwo{b_{11}}{b_{12}}{b_{21}}{b_{22}} = \mattwo{a_{11}+b_{11}}{a_{12}+b_{12}}{a_{21}+b_{21}}{a_{22}+b_{22}}$$ i mnożyć, nieco bardziej skomplikowanie (polecam http://pl.wikipedia.org/wiki/Mnożenie\_macierzy): $$\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}}\cdot \mattwo{b_{11}}{b_{12}}{b_{21}}{b_{22}} = \mattwo{a_{11}b_{11} + a_{12}b_{21}}{a_{11}b_{12}+a_{12}b_{22}}{a_{21}b_{11}+a_{22}b_{21}}{a_{21}b_{12}+a_{22}b_{22}}$$ dodatkowo możemy na macierzach zdefiniować mnożenie przez stałą $r\in R$. $$r\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} := \mattwo{r}{0}{0}{r}\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} = \mattwo{ra_{11}}{ra_{12}}{ra_{21}}{ra_{22}}$$ \item \begin{thm} Dla dowolnego pierścienia $R$ macierze $\mathbb{M}_2(R)$ tworzą pierścień z działaniami $+$ i $\cdot$. Elementem neutralnym tego pierścienia jest macierz $$I:=\mattwo{1}{0}{0}{1}.$$ Jeżeli ponadto pierścień $R$ jest przemienny, to zachodzi $$\mattwo{r}{0}{0}{r}A = A\mattwo{r}{0}{0}{r}A$$ dla wszystkich macierzy $A\in \mathbb{M}_2(R)$. \end{thm} \begin{proof} Aby udowodnić, że macierze są pierścieniem wystarczy przeliczyć wszystkie własności pierścienia. Podobnie można policzyć, że $I$ jest jedynką.\\ Przeliczę tylko ostatnie stwierdzenie. Niech $A = \mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} \in \mathbb{M}_2(R)$ oraz $r\in R$ wtedy $$\mattwo{r}{0}{0}{r}\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}} = \mattwo{ra_{11}}{ra_{12}}{ra_{21}}{ra_{22}} = \mattwo{a_{11}r}{a_{12}r}{a_{21}r}{a_{22}r} = \mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}}\mattwo{r}{0}{0}{r}$$ \end{proof} \item Aby uprościć robotę nieinteresujące mnie elementy macierzy będę oznaczać $*$. Nigdy nie będę ich wyliczać, \textbf{ich wartość nie będzie miała wpływu na przekształcenia}. Przykład: $$\mattwo{1}{*}{0}{*} = I = \dots$$ elementy $*$ należy rozumieć jako elementy macierzy sąsiedniej (tutaj $I$). \end{enumerate} \paragraph{Teoria ciągu Fibonacciego} \begin{enumerate} \item \begin{defn} Ciągiem \textbf{Fibonacciego} nazywamy ciąg rekurencyjny $(F_n)$ dany równaniami: $$F_0 = 0,\ F_1=1,\ F_n = F_{n-1} + F_{n-2}\hbox{ dla }n\geq 2$$ Kolejne wyrazy ciągu Fibonacciego to: \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|} \hline $n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$\\ \hline $F_n$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ & $21$\\ \hline \end{tabular} Dla wygody zdefiniujemy również wyrazy o indeksach ujemnych, tak, żeby zachowana była własność $F_n = F_{n-1} + F_{n-2}$. W tym celu należy wziąć $F_{-n} = (-1)^{n+1}F_n$.\\ \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline $n$ & $-5$ & $-4$ & $-3$ & $-2$ & $-1$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ &$8$\\ \hline $F_n$ & $5$ & $-3$ & $2$ & $-1$ & $1$ & $0$ & $1$ & $1$ & $2$ & $3$ & $5$ & $8$ & $13$ &$21$\\ \hline \end{tabular} \end{defn} Macierzą ciągu Fibonacciego nazywamy macierz $$\mathbb{F} := \mattwo{1}{1}{1}{0}. \hbox{ Jest ona odwracalna w }\mathbb{M}_2(\mathbb{Z})\hbox{, jej odwrotnością jest } \mathbb{F}^{-1} = \mattwo{0}{1}{1}{-1}$$ \textbf{Równanie:} Bezpośrednio przeliczamy, że $$\mathbb{F}^2 - \mathbb{F} - I = 0\hbox{ stąd wynika po podzieleniu } \mathbb{F} = \frac{1}{\mathbb{F} - I}\hbox{ a więc }(\mathbb{F}-I)^{-1} = \mathbb{F}$$ \textbf{Ważna uwaga/metatwierdzenie}: Jeżeli rozpatrujemy tylko wyrażenia zawierające $\mathbb{F}$ oraz $rI$, gdzie $r\in \mathbb{R}$, to każde dwa takie wyrażenia będą przemienne ze sobą, w szczególności możemy pisać odwrotności w normalnej postaci ułamka. \item \begin{lem}[Postać macierzowa ciągu] Dla każdego $n$ całkowitego $$\mathbb{F}^n = \mattwo{1}{1}{1}{0}^n = \mattwo{F_{n+1}}{F_n}{F_n}{F_{n-1}}$$ \end{lem} \begin{proof} Zauważmy, że $F^0 = I = \mattwo{1}{0}{0}{1} = \mattwo{F_1}{F_0}{F_0}{F_{-1}}$, a więc dla $n=0$ równość jest prawdziwa. Równość udowodnimy najpierw dla $n\geq 0$, przez indukcję, której bazę właśnie udowodniliśmy. Krok indukcyjny wygląda następująco: $$\mathbb{F}^{n+1} = \mathbb{F}^n\cdot \mathbb{F} = \mattwo{F_{n+1}}{F_n}{F_n}{F_{n-1}}\mattwo{1}{1}{1}{0}= \mattwo{F_{n+1} + F_n}{F_{n+1}}{F_n + F_{n-1}}{F_{n}} = \mattwo{F_{n+2}}{F_{n+1}}{F_{n+1}}{F_n}$$ Pozostaje udowodnić tę równość także dla $n < 0$. Dowód przebiega przez indukcję względem malejącego $n$, której rdzeniem jest równość $$\mathbb{F}^{-(n+1)} = \mathbb{F}^{-n}\mathbb{F}^{-1} = \mattwo{F_{-n+1}}{F_{-n}}{F_{-n}}{F_{-n-1}}\mattwo{0}{1}{1}{-1} = \mattwo{F_{-n}}{F_{-n + 1} - F_{-n}}{F_{-n-1}}{F_{-n} - F_{-n-1}} = \mattwo{F_{-n}}{F_{-n-1}}{F_{-n-1}}{F_{-n-2}}.$$ \end{proof} Ten dowód przeprowadzony jest wprost, gdyż wydaje mi się pouczający. Poniżej szkic (prostszego) dowodu alternatywnego korzystającego z $\mathbb{F}^2 = \mathbb{F} + I$:\\ \begin{proof} Bezpośrednio przeliczamy, że dla $n=0$ i $n=1$ równość jest prawdziwa. Przeprowadzamy, jak wyżej, indukcję po $n$ rosnącym i malejącym. Przykładowo -- krok indukcyjny w indukcji po $n$ rosnącym $$\mathbb{F}^{n+2} = \mathbb{F}^n\mathbb{F}^2 = \mathbb{F}^n(\mathbb{F} + I) = \mathbb{F}^{n+1} + \mathbb{F}^n = \mattwo{F_{n+2}}{F_{n+1}}{F_{n+1}}{F_n} + \mattwo{F_{n+1}}{F_n}{F_n}{F_{n-1}} = $$ $$\mattwo{F_{n+2} + F_{n+1}}{F_{n+1}+F_n}{F_{n+1} + F_n}{F_n + F_{n-1}} = \mattwo{F_{n+3}}{F_{n+2}}{F_{n+2}}{F_{n+1}}$$ co było do udowodnienia. Ten dowód korzysta bardzo mocno ze struktury algebraicznej macierzy. \end{proof} \end{enumerate} \paragraph{Własności ciągu Fibonacciego -- zadania prostsze} \begin{enumerate} \item Uzasadnić (elementarnie jest prościej :), że każde dwa kolejne wyrazy ciągu Fibonacciego są są względnie pierwsze.\\ \begin{sol} Niech $n,d\in \mathbb{Z}_+$ będą takie, że, że $d|F_n,\ d|F_{n+1}$. Wtedy $d|F_{n+1} - F_n = F_{n-1}$. Analogicznie wnioskując $d|F_n - F_{n-1} = F_{n-2}$, itd. Dochodzimy do $d|F_1 = 1$. Tym samym $d=1$. \end{sol} \item Uzasadnić, że dla wszystkich liczb naturalnych $n,m$ zachodzi $$F_{n+1}F_m + F_nF_{m-1} = F_{m+n}$$ \sol $$\mattwo{*}{F_{n+m}}{*}{*} = \mathbb{F}^{n+m} = \mathbb{F}^n\mathbb{F}^m = \mattwo{F_{n+1}}{F_n}{*}{*}\mattwo{*}{F_m}{*}{F_{m-1}} = \mattwo{*}{F_{n+1}F_m + F_nF_{m-1}}{*}{*}$$ \item W szczególności dla wszystkich liczb naturalnych $n$ zachodzi $$F_n^2 + F_{n+1}^2 = F_{2n+1}$$ \sol Równość z poprzedniego zadania dla $m:=n+1$. \item Niech $n$ będzie liczbą naturalną. Uzasadnić, że $$F_0 + F_1 + \dots + F_n = F_{n+2} - 1$$ \sol Zastosujemy wzór na sumę ciągu geometrycznego $$\mattwo{*}{F_0 + F_1 + \dots + F_n}{*}{*} = \mathbb{F}^0 + \mathbb{F}^1 + \dots + \mathbb{F}^n = \frac{\mathbb{F}^{n+1} - I}{\mathbb{F} - I} = \mathbb{F}^{n+2} - \mathbb{F} = \mattwo{*}{F_{n+2} - 1}{*}{*}$$ Z równości macierzy wynika teza. \item Niech $n$ będzie liczbą naturalną. Uzasadnić, że $$F_1 + F_3 + F_5 + \dots + F_{2n-1} = F_{2n}$$ \sol Jak w poprzednim przykładzie stosujemy ciąg geometryczny $$\mattwo{*}{F_1 + F_3 + F_5 + \dots + F_{2n-1}}{*}{*} = \mathbb{F} + \mathbb{F}^3 + \dots + \mathbb{F}^{2n-1} = \mathbb{F}(\mathbb{F}^0 + \mathbb{F}^2 + \dots + \mathbb{F}^{2n-2}) = $$ $$\mathbb{F}\frac{\mathbb{F}^{2n} - I}{\mathbb{F}^2 - I} = \mathbb{F}\frac{\mathbb{F}^{2n} - I}{\mathbb{F}} = \mathbb{F}^{2n} - I = \mattwo{*}{F_{2n}}{*}{*}$$ \item Niech $n$ będzie liczbą naturalną. Udowodnić, że $$\sum_{i=1}^n iF_i = nF_{n+2} - F_{n+3} + 2$$ \begin{sol} $$\sum_{i=1}^n i\mathbb{F}^i = \sum_{i=1}^n(\mathbb{F}^i + \mathbb{F}^{i+1} + \dots + \mathbb{F}^n) = \sum_{i=1}^n \mathbb{F}^i\frac{\mathbb{F}^{n+1-i} - I}{\mathbb{F} - I} = \sum_{i=1}^n \mathbb{F}^i(\mathbb{F}^{n+1-i} - I)\mathbb{F} = \sum_{i=1}^n \mathbb{F}^{n+2} - \mathbb{F}^{i+1} = $$ $$n\mathbb{F}^{n+2} - \sum_{i=1}^n \mathbb{F}^{i+1} = n\mathbb{F}^{n+2} - \mathbb{F}^2\frac{\mathbb{F}^{n} - I}{\mathbb{F} - I} = n\mathbb{F}^{n+2} - \mathbb{F}^2(\mathbb{F}^{n} - I)\mathbb{F} = n\mathbb{F}^{n+2} - \mathbb{F}^{n+3} + \mathbb{F}^3$$ jak zwykle porównujemy współczynniki w prawym górnym rogu, uzyskując tezę (z ostatniej macierzy uzyskamy $F_3 = 2$). \end{sol} \item Uzasadnić, że dla wszystkich $n$ naturalnych zachodzi $$F_{n+1}F_{n-1} - F_n^2 = (-1)^n$$ \begin{sol} Trik. Wiemy, że $\mathbb{F}^n \mathbb{F}^{-n} = I$. Ale można to spróbować policzyć bezpośrednio: $$\mattwo{1}{0}{0}{1} = I = \mathbb{F}^n \mathbb{F}^{-n} = \mattwo{F_{n+1}}{F_n}{*}{*}\mattwo{F_{-n+1}}{*}{F_{-n}}{*} = \mattwo{F_{n+1}F_{-n+1} + F_nF_{-n}}{*}{*}{*}$$ wynika stąd $1 = F_{n+1}F_{-n+1} + F_nF_{-n}$. Podstawiamy, korzystając z definicji, $F_{-n+1} = (-1)^nF_{n-1},\ F_{-n} = (-1)^{n+1}F_n$ i uzyskujemy $$1 = (-1)^nF_{n+1}F_{n-1} + (-1)^{n+1}F_n^2$$ mnożymy obie strony przez $(-1)^n$: $$(-1)^n = (-1)^{2n}F_{n+1}F_{n-1} + (-1)^{2n+1}F_n^2 = F_{n+1}F_{n-1} - F_n^2$$ \end{sol} \end{enumerate} \paragraph{Dalsze własności pierścieni} \begin{enumerate} \item \begin{defn} Niech $R$ będzie pierścieniem. Podzbiór $J$ pierścienia $R$ nazywamy ideałem jeżeli: \begin{enumerate} \item $I$ jest podgrupą przemienną ze względu na $+$. \item Dla dowolnego $r\in R, i\in I$ zachodzi $$r\cdot i\in I\hbox{ oraz }i\cdot r\in I$$ \end{enumerate} \end{defn} $J$ jest ideałem $R$ oznaczamy przez $J\ideal R$. \item Pojęcie ideału rozszerza pojęcie kongruencji:\\ Piszemy $a \equiv b \mod I$ jeżeli $b-a\in I$. Załóżmy, że $$a\equiv b \mod I,\ \ c\equiv d\mod I$$ Wtedy (m. in.) $$b\equiv a\mod I$$ $$a + c \equiv b + d \mod I$$ $$a - c \equiv b - d \mod I$$ $$ac \equiv bd \mod I$$ Udowodnię dla przykładu ostatnią (najtrudniejszą) własność.\\ $$a \equiv b\mod I \Rightarrow a-b\in I \Rightarrow (a-b)c\in I$$ $$c \equiv d\mod I \Rightarrow d-c\in I \Rightarrow b(d-c)\in I$$ $$(a-b)c\in I,\ b(d-c)\in I \Rightarrow ac - bd = (a-b)c - b(d-c)\in I \Rightarrow ac \equiv bd \mod I$$ \item Naturalne w tym kontekście jest zauważenie, że dla ustalonego $n\in \mathbb{Z}$ zbiór postaci $$I_n:=\left\{ kn\ |\ k\in \mathbb{Z}\right\}$$ jest ideałem w $\mathbb{Z}$. Kongruencje $\mod I_n$ to znane nam kongruencje $\mod n$. \item \begin{lem} Rozważmy macierze $\mathbb{M}_2(R)$ i niech $I\ideal R$. Zdefiniujmy $$\mathbb{M}_2(I):=\left\{ \mattwo{a}{b}{c}{d}\in R\ |\ a,b,c,d\in I\right\}$$ Wtedy $\mathbb{M}_2(I)$ jest ideałem w $\mathbb{M}_2(R)$. \end{lem} \begin{proof} Na początku udowodnimy, że $\mathbb{M}_2(I)$ jest podgrupą przemienną. Wystarczy (patrz kółko o grupach) udowodnić, że $$A,B\in \mathbb{M}_2(I) \Rightarrow A+B\in \mathbb{M}_2(I)\hbox{ oraz }-A\in \mathbb{M}_2(I)$$ Rozważmy $A:=\mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}}, B:=\mattwo{b_{11}}{b_{12}}{b_{21}}{b_{22}}$. Z definicji $\mathbb{M}_2(I)$ wynika, że $a_i,b_i\in I$. W związku z tym również (z własności ideału $I$): $$a_{11} - b_{11}\in I,a_{12} - b_{12}\in I\dots$$ a stąd $$A-B = \mattwo{a_{11}-b_{11}}{a_{12}-b_{12}}{a_{21}-b_{21}}{a_{22}-b_{22}} \in \mathbb{M}_2(I)$$ z definicji $\mathbb{M}_2(I)$. $-A\in \mathbb{M}_2(I)$ udowadniamy analogicznie.\\$ $\\ Pozostaje udowodnić drugą własność ideałów. Rozważmy dowolną $C = \mattwo{c_{11}}{c_{12}}{c_{21}}{c_{22}}\in \mathbb{M}_2(R)$ i dowolną $\mattwo{i_{11}}{i_{12}}{i_{21}}{i_{22}}\in \mathbb{M}_2(R)$: $$\mattwo{c_{11}}{c_{12}}{c_{21}}{c_{22}}\mattwo{i_{11}}{i_{12}}{i_{21}}{i_{22}} = \mattwo{c_{11}i_{11} + c_{12}i_{21}}{c_{11}i_{12}+c_{12}i_{22}}{c_{21}i_{11}+c_{22}i_{21}} {c_{21}i_{12}+c_{22}i_{22}}$$ Widać, że np. w pierwszej komórce $i_{11}\in I$ stąd $c_{11}i_{11}\in I$, analogicznie $c_{12}i_{21}\in I$, więc $c_{11}i_{11} + c_{12}i_{21}\in I$. Pozostałe wartości również należą do $I$, więc cała macierz należy do $\mathbb{M}_2(I)$ (z definicji $\mathbb{M}_2(I)$).\\ Drugą część drugiej własności udowadniamy analogicznie. \end{proof} \end{enumerate} \paragraph{Własności ciągu Fibonacciego -- zadania trudniejsze} \begin{enumerate} \item Uwaga: poniższe dwa zadania można zrobić elementarnie, korzystając z tożsamości $F_{n+1}F_m + F_nF_{m-1} = F_{m+n}$ oraz z lematu w zadaniu drugim, ale dowody są (moim zdaniem) \emph{trudniejsze} do wymyślenia i \emph{mniej naturalne}, oczywiście z dokładnością do pewnego zrozumienia pojęć abstrakcyjnych. \item \begin{thm}[*] Jeżeli liczby $n,m\in \mathbb{Z}_+$ oraz $n\ |\ m$ to $$F_n\ |\ F_m$$ \end{thm} \begin{proof} Niech $m = nk$.\\ Wiemy (patrz część teoretyczna), że zbiór $$J:= \mathbb{M}_2(I_{F_n})$$ jest ideałem w $\mathbb{M}_2(\mathbb{Z})$. Rozpatrzmy kongruencje $\mod J$. $$\mathbb{F}^n = \mattwo{F_{n+1}}{F_n}{F_n}{F_{n-1}} \equiv \mattwo{F_{n+1}}{0}{0}{F_{n-1}} \mod J$$ Tym samym $$\mattwo{F_{m+1}}{F_m}{F_m}{F_{m-1}} = \mathbb{F}^m = (\mathbb{F}^n)^k \equiv \mattwo{F_{n+1}}{0}{0}{F_{n-1}}^k = \mattwo{F_{n+1}^k}{0}{0}{F_{n-1}^k} \mod J$$ Tak więc (wyrazy nieprzydatne w rozumowaniu oznaczam $*$): $$J \ni \mattwo{F_{m+1}}{F_m}{F_m}{F_{m-1}} - \mattwo{F_{n+1}^k}{0}{0}{F_{n-1}^k} = \mattwo{*}{F_m}{F_m}{*}$$ Z definicji $J$ znaczy to, że $F_m = bF_n$ dla pewnego $b\in \mathbb{Z}$, $F_n\ |\ F_m$. \end{proof} \item \begin{thm}[*] Dla wszystkich liczb naturalnych $n,m$ zachodzi równość $$NWD(F_n, F_m) = F_{NWD(n,m)}$$ \end{thm} \begin{proof} \begin{lem} Jeżeli $a,b\in \mathbb{Z}_+$, $d = NWD(a,b)$, to istnieją takie $k,l\in \mathbb{Z}$, $k, l > 0$, że $$ak - bl = d$$ \end{lem} \begin{proof} Liczby $a/d,b/d$ są całkowite i względnie pierwsze, tj. $NWD(a/d, b/d) = 1$. Niech $a':=a/d,b':=b/d$.\\ Rozważmy wszystkie liczby względnie pierwsze z $b'$ ze zbioru $\left\{ 1,2,\dots, n \right\}$. Niech będą to liczby $c_1,\dots,c_s$. Liczby $c_1a' \mod b',\dots, c_sa' \mod b'$ należą do tego zbioru (bo są względnie pierwsze z $b'$), ponadto $$c_ia' \equiv c_ja' \mod b' \Rightarrow (c_i - c_j)a' \equiv 0 \mod b' \hbox{ a skoro }NWD(a', b') = 1\hbox{, to }c_i \equiv c_j \mod b, c_i = c_j$$ tym samym liczby $c_1a' \mod b',\dots, c_sa' \mod b'$ są parami różne.\\ Zachodzi $\left\{ c_1a'\mod b',\dots, c_sa'\mod b' \right\} \subseteq \left\{ c_1,\dots,c_s \right\}$ i $|\{ c_1a'\mod b',\dots, c_sa'\mod b'\}| = |\{ c_1,\dots,c_s \}|$, a więc $\left\{ c_1a'\mod b',\dots, c_sa'\mod b' \right\} = \left\{ c_1,\dots,c_s \right\} \ni 1$, w szczególności istnieje $c_i$: $c_ia' \equiv 1 \mod b'$, czyli istnieje takie $t \in \mathbb{Z}$, że $$c_ia' + tb' = 1$$ $$c_ia/d + tb/d = 1$$ $$c_ia - (-t)b = d$$ Wiemy, że $c_i > 0$. Pozostaje doprowadzić do stanu, gdy $-t > 0\hbox{ czyli gdy }t<0$. Robimy to następująco: $d = c_ia + tb = (c_i + sb)a + (t-sa)b$. Wybieramy na tyle duże $s > 0$, że $t - sa < 0$. \emph{Tak tak, ten cały dowód to jeszcze raz przeliczenie, że coś jest grupą -- stale to robię\dots}. \end{proof} Z poprzedniego twierdzenia wnioskujemy, że $$F_{NWD(n,m)}\ |\ F_n\hbox{ i }F_{NWD(n,m)}\ |\ F_m\hbox{ a więc }F_{NWD(n,m)}\ |\ NWD(F_n,F_m)$$ pozostaje wykazać, że $$NWD(F_n,F_m)\ |\ F_{NWD(n,m)}.$$ Niech dla zwięzłości $d:=NWD(n,m)$ oraz $D:=NWD(F_n, F_m)$.\\ Korzystamy z lematu i wybieramy takie $k,l\in \mathbb{Z}$, że $nk - ml = d$.\\ Rozważmy ideał $\mathbb{M}_2(I_D) \ideal \mathbb{M}_2(\mathbb{Z})$. Przypominam, jest to ideał $$\mathbb{M}_2(I_D) = \left\{ \mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}}\ :\ a_{11},a_{12},a_{21},a_{22} \in I_D\right\} = \left\{ \mattwo{a_{11}}{a_{12}}{a_{21}}{a_{22}}\ :\ D\ |\ a_{11},a_{12},a_{21},a_{22}\right\}$$ $$\mattwo{F_{d+1}}{F_d}{F_d}{F_{d-1}} = \mathbb{F}^d = \mathbb{F}^{nk}\mathbb{F}^{-ml} = \mattwo{F_{nk+1}}{F_{nk}}{F_{nk}}{F_{nk-1}}\mattwo{F_{-ml+1}}{F_{-ml}}{F_{-ml}}{F_{-ml-1}} \equiv$$ $$\mattwo{F_{nk+1}}{0}{0}{F_{nk-1}}\mattwo{F_{-ml+1}}{0}{0}{F_{-ml-1}} = \mattwo{F_{nk+1}F_{-ml+1}}{0}{0}{F_{nk-1}F_{-ml-1}} \mod \mathbb{M}_2(I_D)$$ Wykorzystujemy tutaj fakt, że $D|F_m|F_{-ml}$ oraz $D|F_n|F_{nk}$. Z definicji $\mathbb{M}_2(I_D)$ jest $F_d \equiv 0 \mod D$, $D\ |\ F_d$, a jeżeli przypomnimy definicje $d, D$, otrzymujemy $NWD(F_n,F_m)\ |\ F_{NWD(n, m)}$.\\ \end{proof} \item \begin{thm}[**Wzór Bineta] Niech $\phi_1 := \dfrac{1 + \sqrt{5}}{2}, \ \phi_2 := \dfrac{1 - \sqrt{5}}{2}$, innymi słowy, niech będą to pierwiastki równania $x^2 - x - 1 = 0$. Wtedy $$F_n = \frac{1}{\sqrt{5}}(\phi_1^n - \phi_2^n)$$ dla wszystkich liczb całkowitych $n$. \end{thm} \begin{proof} \textbf{Uwaga: } W tym zadaniu, w przeciwieństwie do pozostałych, rozważamy macierze o wyrazach rzeczywistych, a nie całkowitych.\\ Rozważmy macierz $$S:=\mattwo{\phi_1}{\phi_2}{1}{1},\hbox{ wtedy }S^{-1} = \frac{1}{\sqrt{5}}\mattwo{1}{-\phi_2}{-1}{\phi_1}$$ Obliczamy $$S^{-1}\mathbb{F}S = \mattwo{\phi_1}{0}{0}{\phi_2}$$ \emph{cała operacja nie jest przypadkowa i nazywa się diagonalizacją macierzy}. Obliczamy $$S^{-1}\mathbb{F}^nS = S^{-1}\mathbb{F}\mathbb{F}\dots \mathbb{F}S = S^{-1}\mathbb{F}SS^{-1}\mathbb{F}S\dots \mathbb{F}S = (S^{-1}\mathbb{F}S)^n = \mattwo{\phi_1}{0}{0}{\phi_2}^n = \mattwo{\phi_1^n}{0}{0}{\phi_2^n}$$ Wyliczamy (w końcowej fazie obliczam tylko potrzebną mi część, pozostałe wyrazy oznaczam $*$): $$\mattwo{F_{n+1}}{F_n}{F_n}{F_{n-1}} = \mathbb{F}^n = S(S^{-1}\mathbb{F}^nS)S^{-1} = S\mattwo{\phi_1^n}{0}{0}{\phi_2^n}S^{-1} = $$ $$\mattwo{\phi_1}{\phi_2}{1}{1} \mattwo{\phi_1^n}{0}{0}{\phi_2^n} \frac{1}{\sqrt{5}}\mattwo{1}{-\phi_2}{-1}{\phi_1} = \mattwo{\phi_1^{n+1}}{\phi_2^{n+1}}{*}{*}\frac{1}{\sqrt{5}}\mattwo{1}{-\phi_2}{-1}{\phi_1} = \frac{1}{\sqrt{5}}\mattwo{\phi_1^{n+1} - \phi_2^{n+1}}{*}{*}{*}$$ Stąd $F_{n+1} = \frac{1}{\sqrt{5}}(\phi_1^{n+1} - \phi_2^{n+1})$, z czego wynika teza. \end{proof} \end{enumerate} \end{document} |
| Poprawiony: wtorek, 23 marca 2010 08:59 |
