Koło matematyczne I LO w Białymstoku

Na kółku rozwiązywane były zadania z rubryki "zastosowania".

 
Skrypt teoretyczny bez dowodów PDF.

Źródło zadań w texu.

 
%        File: skrypt2.tex
%     Created: Thu Jul 01 01:00 PM 2010 C
% Last Change: Thu Jul 01 01:00 PM 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}[1][Dowód. ]{\noindent\textsc{#1}}
{\nolinebreak[4]\hfill$\blacksquare$\\\par}
\newenvironment{sol}[1][Rozwiązanie. ]{
\noindent\textsc{#1}}
{\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\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}: \\}
 
    \subimport{../}{style}
 
    \begin{document}
    \renewcommand{\thethm}{}
 
    \section{The $\mathbb{Z}$ is not enough.}
 
    \subsection{Pierścień ilorazowy}
 
    \emph{Uwaga: Formalizmy / Watch out: formalisms ahead.}
 
    Załóżmy, że mamy pierścień $R$ i ideał $I \ideal R$.
 
    Podzielmy pierścień $R$ na zbiory reszt z dzielenia przez $I$ tj.\ zgodnie
    z zasadą, że $a$ i $b$ są w jednym zbiorze wtedy i tylko wtedy, gdy
    $$a \equiv b \mod I$$
    \emph{Bardzo formalnie: Tak można podzielić, gdyż $a\equiv a$ dla każdego elementu,
    $a\equiv b$ jest równoważne $b \equiv a$ oraz $a \equiv b \equiv c$
    implikuje $a \equiv c$.}
 
    Dla danego $a\in R$ resztą $a$ modulo $I$ będę nazywać zbiór
    wszystkich elementów $R$, które przystają do elementu $a$ modulo $I$. Będę
    ten zbiór oznaczać jako $a \mod I$.
 
    Twierdzę, że zbiór wszystkich reszt to pierścień z działaniami
    $$(a\mod I) + (b\mod I) = (a+b \mod I)$$
    $$-(a\mod I) = (-a \mod I)$$
    $$(a\mod I) \cdot (b\mod I) = (ab \mod I)$$
    tworzy pierścień, który nazywam \emph{pierścieniem ilorazowym $R$ przez
    $I$} i oznaczam $R/I$ albo $\frac{R}{I}$.
 
 
    \subsection{Epimorfizmy i izomorfizmy}
 
    \emph{Na poprzednim kółku potykaliśmy się o takie nienazywalne kulturalnie
    rzeczy jak ``widać, że to działanie jest na pierwszej współrzędnej, ale
    jak to uzasadnić formalnie?''. Do uzasadniania takich rzeczy służy pojęcie
    izomorfizmu.}
 
    \emph{Intuicyjnie epimorfizm jest sensowną funkcją na, innymi słowy
    funkcją, która zachowuje wszystkie algebraiczne własności.}
 
    \begin{defn}[Epimorfizm]
        Niech $R$ i $R'$ będą pierścieniami. Epimorfizmem pomiędzy
        pierścieniami $R$ i $R'$ nazywamy każdą funkcję $f: R  \rightarrow S$,
        przyjmującą każdą możliwą wartość z $S$ oraz taką, że
        $$f(x + y) = f(x) + f(y)$$
        $$f(x \cdot y) = f(x) \cdot f(y)$$
 
        \emph{Uwaga: $+,\cdot$ z lewej strony wykonywane są w pierścieniu
        $R$, a te z prawej strony -- w pierścieniu $S$.}
    \end{defn}
 
    \begin{lem}
        Jeżeli $f$ jest epimorfizmem to $f(0)$ jest równe zeru pierścienia
        $S$, a $f(1)$ jest równe jedynce pierścienia $S$, krócej $f(0)=0,
        f(1)=1$.
    \end{lem}
    \begin{proof}
 
        $f(0) = f(0+0) = f(0) + f(0)$, stąd (odejmujemy od prawej strony lewą)
        $f(0) = 0$.
 
        W pierścieniu $S$ istnieje $1$. Funkcja
        $f$ przyjmuje wszystkie wartości, zatem istnieje takie $b\in R$, że
        $f(b) = 1$.
 
        Obliczam $f(1) = f(1)\cdot 1 = f(1)\cdot f(b) = f(1\cdot b) = f(b) = 1$.
    \end{proof}
 
    \begin{defn}[Jądro]
        Dla danego epimorfizmu $f: R  \rightarrow S$ definiujemy
        \emph{jądro} $f$ jako
        $$\ker f := \left\{ r\in R\ |\ f(r)=0 \right\}$$
    \end{defn}
 
    \begin{lem}
        Jeżeli $f:R  \rightarrow S$ jest epimorfizmem to $\ker f \ideal R$.
    \end{lem}
 
    \begin{defn}[Izomorfizm]
        Funkcję $f:R \rightarrow R'$ nazywamy izomorfizmem, jeżeli $f$ jest
        różnowartościowa.
 
        Jak wiemy istnieje wtedy funkcja $f^{-1}: R'  \rightarrow  R$.
        Dodatkowo $f^{-1}$ zachowuje dodawanie i mnożenie, więc $f^{-1}$ jest
        również izomorfizmem.
 
        Mówimy, że pierścienie $R, R'$ są izomorficzne jeżeli istnieje
        pomiędzy nimi izomorfizm. Zapisujemy to jako $R \simeq R'$.
 
        \emph{Dla algebraika pierścienie izomorficzne są identyczne -- cała
        struktura jest zachowana przez odpowiednie przekształcenia.}
    \end{defn}
 
    \begin{cor}
        Epimorfizm jest izomorfizmem wtedy i tylko wtedy, gdy jego jądro jest
        zerowe.
    \end{cor}
 
    \begin{cor}
        Jeżeli $I$ jest ideałem $R$, to przekształcenie $f: R  \rightarrow
        R/I$ dane wzorem
        $$f(x) = x \mod I$$
        jest epimorfizmem z jądrem $I$.
    \end{cor}
 
    \begin{thm}[* Pierwsze twierdzenie o izomorfizmie]
        Jeżeli $f:R  \rightarrow S$ jest epimorfizmem to
        $$\frac{R}{\ker f} \simeq S$$
    \end{thm}
 
    \subsection{Przykłady ideałów i pierścieni ilorazowych}
    \begin{enumerate}
        \item \emph{Motywacją całej teorii pierścieni (do czasu) był
            $\mathbb{Z}$ zatem:}
 
            Rozważmy $\mathbb{Z}n \ideal \mathbb{Z}$. Pierścień ilorazowy
            $\frac{\mathbb{Z}}{\mathbb{Z}n}$ to $n$-elementowy pierścień reszt
            z dzielenia przez $n$.
        \item Rozważmy pierścień wielomianów $\mathbb{R}[x]$ i wielomiany bez
            wyrazu wolnego: $x\mathbb{R}[x]$.
 
            Wtedy $x\mathbb{R}[x] \ideal \mathbb{R}[x]$ oraz
            $$\frac{\mathbb{R}[x]}{x\mathbb{R}[x]} \simeq \mathbb{R}$$
        \item Rozważmy funkcje z odcinka $[0,1]$ w $\mathbb{R}$, dla dalszego
            użycia oznaczmy zbiór tych funkcji przez $\mathcal{F}$. Funkcje te 
            tworzą pierścień z działaniami po wartościach:
            $$(f+g)(x) := f(x) + g(x)$$
            $$(-f)(x) := -f(x)$$
            $$(f\cdot g)(x) := f(x) \cdot g(x)$$
 
            Podzbiór $I:=\left\{ f \in \mathcal{F}\ |\
            f(0)=0\right\}$ jest ideałem pierścienia $\mathcal{F}$.
 
            * Uzasadnij, że $\frac{\mathcal{F}}{I} \simeq \mathbb{R}$.
    \end{enumerate}
 
    \subsection{Przykłady epimorfizmów i izomorfizmów}
    \begin{enumerate}
        \item Jeżeli $\mathcal{F}$ jest pierścieniem funkcji z $[0,1]$ w
            $\mathbb{R}$ z dodawaniem i mnożeniem po wartościach (jak wyżej) to
            przypisanie funkcji jej wartości w $0$, formalniej $ev:\mathcal{F}
             \rightarrow \mathbb{R}$ dane przez
            $$ev(f) = f(0)$$
            jest epimorfizmem o jądrze $\left\{ f\in \mathcal{F}\ |\ f(0)=0
            \right\}$.
        \item Pierścienie $\mathbb{Z} \times \left\{ 0 \right\}$ oraz
            $\mathbb{Z}$ są izomorficzne przez izomorfizm $(z,0)  \rightarrow
            z$.
    \end{enumerate}
 
    \subsection{Zastosowanie}
 
    \begin{lem}
        Dla dowolnych liczb naturalnych $a,b$ zachodzi równoważność
        $$NWD(a,b) = 1  \Leftrightarrow \hbox{ istnieją }t,u\in \mathbb{Z}: ta
        + ub = 1.$$
    \end{lem}
 
    \begin{thm}[Algebraiczne chińskie twierdzenie o resztach]
        Jeżeli liczby $k_1,\dots,k_m$ są parami względnie pierwsze tj.
        $NWD(k_i,k_j) = 1$ dla wszystkich $i,j$ oraz $n=k_1k_2\dots k_m$, to
        $$\frac{\mathbb{Z}}{\mathbb{Z}n} \simeq
        \frac{\mathbb{Z}}{\mathbb{Z}k_1} \times
        \frac{\mathbb{Z}}{\mathbb{Z}k_2} \times \dots \times
        \frac{\mathbb{Z}}{\mathbb{Z}k_m}$$
    \end{thm}
 
    \begin{cor}[Chińskie twierdzenie o resztach]
        Jeżeli liczby $k_1,\dots,k_m$ są parami względnie pierwsze tj.
        $NWD(k_i,k_j) = 1$ dla wszystkich $i,j$
        liczby $r_1,\dots,r_m$ są całkowite
        oraz $n=k_1k_2\dots k_m$, to
        istnieje dokładnie jedna liczba całkowita $M$ z przedziału $[0,n)$
        spełniająca równania
        $$M \equiv r_1 \mod k_1$$
        $$M \equiv r_2 \mod k_2$$
        $$\dots$$
        $$M \equiv r_m \mod k_m$$
    \end{cor}
 
    \begin{cor}
        Funkcja Eulera $\phi$ jest zdefiniowana dla każdego $n$ naturalnego
        jako ilość liczb naturalnych mniejszych od $n$ i względnie pierwszych
        z $n$.
 
        Jeżeli $k_1,\dots,k_m$ są parami względnie pierwsze, to
        $$\phi(k_1k_2\dots k_m) = \phi(k_1)\cdot \phi(k_2)\cdot \ldots \cdot
        \phi(k_m)$$
 
        Jeżeli $n = p_1^{a_1} \dots p_k^{a_k}$ jest rozkładem $n$ na czynniki
        pierwsze, to $\phi(n) = \phi(p_1^{a_1})\dots\phi(p_k^{a_k}) =
        (p_1^{a_1} - p_1^{a_1 - 1})\cdot \ldots \cdot \left(p_k^{a_k} -
        p_k^{a_k-1}\right)$.
    \end{cor}
 
    \begin{problem}[Tegoroczny Konkurs Matematyczny PB -- klasy pierwsze,
        zadanie 2, uogólnione.]
        Niech $n = p_1^{a_1} \cdot \dots p_k^{a_k}$ będzie rozkładem liczby
        naturalnej $n > 1$ na czynniki pierwsze. Wtedy liczb całkowitych $a$ z
        przedziału $[0,n)$ spełniających równanie
        $$a^2 \equiv a \mod n$$
        jest dokładnie $2^k$.
    \end{problem}
    \end{document}