requirements.tex

%% -*- coding:utf-8 -*-
\begin{appendices}
  
\chapter{Course prerequisites}
There are several prerequisites for the course there. They consists of
definitions, theorems and examples mostly taken from Wikipedia. 

\section{Sets}

\begin{definition}[Class]
  A class is a collection of sets (or sometimes other mathematical
  objects) that can be unambiguously defined by a property that all
  its members share. 
  \label{def:class}
\end{definition}

\begin{definition}[Disjoint union]
  Let \cite{wiki:disjointunion} $\{A_i: i \in I\}$ be a family of sets
  indexed by $I$. The 
  disjoint union of this family is the set
  \[
  \sqcup_{i \in I} A_i = \cup_{i \in I}\left\{
  \left(x, i\right): x \in A_i
  \right\}.
  \]
  The elements of the disjoint union are ordered pairs $(x, i)$. Here $i$
  serves as an auxiliary index that indicates which $A_i$ the element $x$
  came from.
  \label{def:disjointunion}
\end{definition}

\begin{example}[Disjoint union]
  Let \cite{wiki:disjointunion} we have 2 sets $A_0 = \{1,2,3\}$ and
  $A_1 = \{1,2\}$. 
  We can construct the following sets of pairs
  \begin{eqnarray}
  A_0^\ast = \left\{
  \left(1,0\right),
  \left(2,0\right),
  \left(3,0\right)
  \right\},
  \nonumber \\
  A_1^\ast = \left\{
  \left(1,1\right),
  \left(2,1\right)
  \right\}  
  \nonumber
  \end{eqnarray}
  so
  \[
  A_0 \sqcup A_1 = A_0^\ast \cup A_1^\ast =
  \left\{
  \left(1,0\right),
  \left(2,0\right),
  \left(3,0\right),
  \left(1,1\right),
  \left(2,1\right)
  \right\}
  \]
  \label{ex:disjointunion}
\end{example}


\section{Groups}

\begin{definition}[Monoid]
  \label{def:monoid}
  The set of elements $M$ with defined binary operation $\circ$ we will call
  as a monoid if the following conditions are satisfied.
  \begin{enumerate}
  \item Closure: $\forall a, b \in M$: $a \circ b \in M$
  \item Associativity: $\forall a, b, c \in M$:
    $a \circ \left( b \circ c \right) =
    \left( a \circ b \right) \circ c$
  \item Identity element: $\exists e \in M$ such that
    $\forall a \in M$: $e \circ a = a \circ e = a$
  \end{enumerate}
\end{definition}

\begin{definition}[Group]
  \label{def:group}
  Let we have a set of elements $G$ with a defined binary operation
  $\circ$ that satisfied the following properties.
  \begin{enumerate}
  \item Closure: $\forall a, b \in G$: $a \circ b \in G$
  \item Associativity: $\forall a, b, c \in G$:
    $a \circ \left( b \circ c \right) =
    \left( a \circ b \right) \circ c$
  \item Identity element: $\exists e \in G$ such that
    $\forall a \in G$: $e \circ a = a \circ e = a$
  \item Inverse element: $\forall a \in G$ $\exists a^{-1} \in G$ such that
    $a \circ a^{-1} = e$
  \end{enumerate}
  In this case $\left(G, \circ\right)$ is called as group.
\end{definition}
Therefore the group is a \mynameref{def:monoid} with inverse element
property. 

\begin{example}[Group $\mathbb{Z}/2\mathbb{Z}$]
  Consider a set of 2 elements: $G = \left\{0, 1\right\}$ with the
  operation $\circ$ defined by the table \ref{tab:CayleyZ2Z}.
  \begin{table}
    \centering
    \caption{Cayley table for $\mathbb{Z}/2\mathbb{Z}$}
    \label{tab:CayleyZ2Z}
    \begin{tabular}{l|ll}
      \toprule
      $\circ$ & 0 & 1 \\
      \midrule
      0 & 0 & 1 \\
      1 & 1 & 0 \\
      \bottomrule
    \end{tabular}
  \end{table}

  The identity element is $0$ i.e. $e = 0$.
  Inverse element is the element itself
  because $\forall a \in G$: $a \circ a = 0 = e$.

  See also example \ref{ex:quotientgroup}
  \label{ex:groupZ2}
\end{example}

\begin{definition}[Order of element in group]
  Order, sometimes period, of an element a of a group is the smallest
  positive integer $m$ such that $a^m = e$ (where $e$ denotes the identity
  element of the group, and am denotes the product of $m$ copies of
  $a$). If no such m exists, a is said to have infinite order.
  \label{def:grouporder}
\end{definition}

\begin{theorem}[Lagrange]
  For any finite group $G$, the order (number of elements) of every
  subgroup $H$ of $G$ divides the order of $G$. 
  \label{thm:lagrange}
\end{theorem}

\begin{theorem}[Finite group of prime order]
  Let $G$ is a finite group of prime order i.e.
  $\left|G\right| = p$, where $p$ is prime number. Then $G$ is a
  \mynameref{def:cyclicgroup}. 
  \label{thm:finite_group_of_prime_order}
  \begin{proof}
    Let $g \in G$ such that $g \ne e$ then, by theorem
    \ref{thm:lagrange},
    we have 
    $\left|\left<g\right>\right| \mid \left|G\right|$. Thus
    $\left|\left<g\right>\right| = p$ because 
    $\left|G\right| = p$ and $p$ is a prime number. As result we have
    $G = \left<g\right>$ and therefore $G$ is a cyclic group.
  \end{proof}
\end{theorem}

\begin{definition}[Subgroup]
  Let we have a \mynameref{def:group} $\left(G, \circ\right)$. The
  subset $S \subset G$ is called as subgroup if $\left(S,
  \circ\right)$ is a \mynameref{def:group}.
  \label{def:subgroup}
\end{definition}

\begin{definition}[Proper subgroup]
  A proper subgroup of a group $G$ is a \mynameref{def:subgroup} $H$
  which is a proper subset of $G$ (i.e. $H \ne G$) \cite{wiki:group}
  \label{def:propersubgroup}
\end{definition}

\begin{definition}[Coset]
  If $G$ is a group, and $H$ is a subgroup of $G$, and $g$ is an
  element of $G$, then
  \[
  gH = \left\{ gh \vert h \in H\right\}
  \]
  is the left coset of $H$ in $G$ with respect to $g$, and
  \[
  Hg = \left\{ hg \vert h \in H\right\}
  \]
  is the right coset of $H$ in $G$ with respect to $g$.
  \label{def:coset}
\end{definition}

\begin{definition}[Normal subgroup]
  A subgroup, $N$, of a group $G$, is called a normal subgroup if it
  is invariant under conjugation i.e. 
  \[
  N \triangleleft G \Leftrightarrow
  \forall n \in N, \forall g \in G, g n g^{-1} \in N
  \]  
  The definition taken from \cite{wiki:normalsubgroup}

  We also can write normality in the \mynameref{def:coset} notation as
  follows.
  $N \triangleleft G$ if $\forall g \in G: gN = Ng$.
  \label{def:normalsubgroup}
\end{definition}

\begin{definition}[Simple group]
   A simple group is a nontrivial group whose only
   \mynameref{def:normalsubgroup}s are the trivial group and the group
   itself.

   The definition taken from \cite{wiki:simplegroup}
   \label{def:simplegroup}
\end{definition}

\begin{definition}[Quotient group]
  A quotient group or factor group is a mathematical group obtained by
  aggregating similar elements of a larger group using an equivalence
  relation that preserves the group structure. For example, the
  \mynameref{def:cyclicgroup} of addition modulo n can be obtained from
  the integers by 
  identifying elements that differ by a multiple of n and defining a
  group structure that operates on each such class (known as a
  congruence class) as a single entity. It is part of the mathematical
  field known as group theory \cite{wiki:quotientgroup}. 

  In a quotient of a group, the equivalence class of the identity
  element is always a normal subgroup of the original group, and the
  other equivalence classes are precisely the cosets of that normal
  subgroup. The resulting quotient is written $G / N$, where $G$ is the
  original group and $N$ is the normal subgroup.

  In other words the quotient group can be defined as a set of all
  left \mynameref{def:coset}s (they also equal to the right cosets as
  soon as $N$ is a \mynameref{def:normalsubgroup}):
  \[
  G/N = \left\{a N: a \in G\right\}
  \]

  See also example \mynameref{ex:s3a3quotientgroup}.
  \label{def:quotientgroup}
\end{definition}

\begin{theorem}[Quotient group]
  If $G$ is a group and $H \triangleleft G$ then the operation $aH
  \cdot bH = a \cdot H$ makes $G/H$ a group with identity $H$ and
  inverse element $\left(a H\right)^{-1} = a^{-1} H$.
  \begin{proof}
    See \cite{book:kostrikin} p. 33.
  \end{proof}
  \label{thm:quotientgroup}
\end{theorem}

\begin{example}[Quotient group]
  Consider \cite{wiki:quotientgroup} a group of integers $\mathbb{Z}$
  (under addition) and the 
  subgroup $2\mathbb{Z}$ of all even integers. This is a normal
  subgroup, because $\mathbb{Z}$ is \mynameref{def:abeliangroup}. There
  are only two \mynameref{def:coset}s: the set 
  of even integers and the set of odd integers; therefore, the
  quotient group $\mathbb{Z}/2\mathbb{Z}$ is the
  \mynameref{def:cyclicgroup} with two 
  elements. This 
  quotient group is isomorphic with the set $\left\{ 0, 1 \right\}$
  with addition modulo 2; informally, it is sometimes said that
  $\mathbb{Z}/2\mathbb{Z}$
  equals the set $\left\{ 0, 1 \right\}$ with addition modulo 2.

  See also example \ref{ex:groupZ2}.
  \label{ex:quotientgroup}
\end{example}

\begin{theorem}[Correspondence theorem]
  The correspondence theorem, sometimes referred to as the fourth
  isomorphism theorem or the lattice theorem, states that if 
  $N$ is a \mynameref{def:normalsubgroup} of a group  $G$, then there
  exists a bijection from the set of all subgroups $A$ of $G$
  containing $N$, onto the set of all subgroups of the quotient group
  $G/N$. The structure of the subgroups of $G/N$ is exactly the same
  as the structure of the subgroups of $G$ containing $N$, with 
  $N$ collapsed to the identity element \cite{wiki:correspondence}.
  \label{thm:correspondence}
\end{theorem}

\begin{definition}[Commutator]
  The commutator of two elements, $g$ and $h$, of a group $G$, is the
  element \cite{wiki:commutator}
  \[
  \left[g, h\right] = g^{-1} h^{-1} g h
  \]
  \label{def:commutator}
\end{definition}

\begin{definition}[Commutator subgroup]
  The commutator subgroup or derived subgroup of a group is the
  subgroup generated by all the \mynameref{def:commutator}s of the group 
  \cite{wiki:commutatorsubgroup}.
  \label{def:commutatorsubgroup}
\end{definition}

\begin{theorem}[About quotient group and commutator subgroup]
  Given a group $G$ a \mynameref{def:quotientgroup} $G/N$ is an
  \mynameref{def:abeliangroup} if and only if $N \supseteq \left[G,
    G\right]$
  \cite{wiki:commutatorsubgroup}
  \label{thm:about_quotient_group_and_commutatorsubgroup}
\end{theorem}

\begin{definition}[Abelianization]
  The quotient $G/[G,G]$ is an abelian group
  (as it follows from theorem \ref{thm:about_quotient_group_and_commutatorsubgroup})
  called the abelianization of $G$ or $G$ made abelian.
  \cite{wiki:commutatorsubgroup}
  \label{def:abelianization}
\end{definition}

\subsection{Cyclic group}

\begin{definition}[Cyclic group]
  A cyclic group or monogenous group is a group that is generated by a
  single element.
  Note that \mynameref{ex:groupZ2} is a cyclic group.
  See example \ref{ex:multiplicativegroup}.
  \label{def:cyclicgroup}
\end{definition}

\begin{theorem}[Fundamental theorem of cyclic groups]
  In abstract algebra, every subgroup of a \mynameref{def:cyclicgroup} is
  cyclic. Moreover, for a finite cyclic group of order $n$, every
  \mynameref{def:subgroup}'s order is a divisor of $n$, and there is
  exactly one subgroup for each divisor.This result has been called the
  fundamental theorem of cyclic groups
  \cite{wiki:subgroups_of_cyclic_groups}
  \label{thm:fundamentaltheoremofcyclicgroup}
\end{theorem}

\begin{theorem}[About subgroups of a cyclic group]
  Let \cite{mathstackexchange:cyclicgroupssubgroup}
    $G=\left<a\right>$ be a cyclic group. 
  \begin{enumerate}
  \item Every subgroup $S$ of $G$ is cyclic
  \item If $\left|G\right| = n$, then $G$ has a unique subgroup of
    order $d$ for each divisor $d$ of $n$
  \end{enumerate}
  See example \ref{ex:multiplicativegroup}
  \label{thm:subgroupofcyclicgroup}
\end{theorem}


\subsection{Group action}

\begin{definition}[Action]
  An action of a group is a way of
  interpreting the elements of the 
  group as "acting" on some space in a way that preserves the structure
  of that space. See also \cite{wiki:groupaction}.
  \label{def:action}
\end{definition}

\begin{definition}[Orbit]
  Consider \cite{wiki:groupaction} a group $G$ acting on a set
  $X$. The orbit of an element $x \in X$ 
  is the set of elements in $X$ to which $x$ can be moved by the elements
  of $G$:
  \[
  Orb\left(x\right) = \left\{y \in X: \exists g \in G: y = g \cdot x \right\}
  \]
  The orbit of element $x$  is also denoted as $G\left(x\right)$.
  \label{def:orbit}
\end{definition}

\begin{definition}[Fixed point]
  The set of points of $X$ fixed by a group action are called the
  group's set of fixed points, defined by
  \[
  \left\{
  x: g x = x, \forall g \in G
  \right\}.
  \]
  see also \cite{mathworld:groupfixedpoint}. 
  \label{def:fixedpoint}
\end{definition}

\begin{definition}[Stabilizer subgroup]
  For every $x$ in $X$, we define \cite{wiki:groupaction} the
  stabilizer subgroup of $G$ with 
  respect to $x$ (also called the isotropy group) as the set of all
  elements in $G$ that fix $x$: 
  \[
  G_{x}=\{g\in G\mid g\cdot x=x\}
  \]
  \label{def:stabilizersubgroup}
\end{definition}

\begin{theorem}[Orbit-stabilizer theorem]
  If group $G$ and the set the group acting $X$ are finite then

  \[
  \left|G\right| = \left|Orb\left(x\right)\right|\left|G_x\right|
  \]
  where $x \in X$, $G\left(x\right)$ - is the \mynameref{def:orbit},
  $G_x$ - \mynameref{def:stabilizersubgroup}.
  
  Note: the result was got from \cite{wiki:groupaction} as
  orbit-stabilizer theorem + \mynameref{thm:lagrange}
  \label{thm:orbitstabilizertheorem}
\end{theorem}

\begin{definition}[Transitive group action]
  The action of $G$ on $X$ is called \cite{wiki:groupaction}
  transitive if $X$ is non-empty and if for each pair $x, y \in X$ there
  exists a $g \in G$ such that $gx = y$.
  \label{def:transitive}
\end{definition}

\begin{definition}[Free group action]
  The action of $G$ on $X$ is called \cite{wiki:groupaction}
  free if, given $g, h \in G$, the existence of an $x \in X$ with $g(x)
  = h(x)$ implies $g = h$.
  \label{def:freeaction}
\end{definition}

\begin{definition}[Quotient of the group action]
  Consider \cite{wiki:groupaction} a group $G$ acting on a set
  $X$. The set of all \mynameref{def:orbit}s of $X$ under the action of
  $G$ is written as $X/G$, and is called the quotient of the action.
  \label{def:quotientofgroupaction}
\end{definition}

\subsection{Direct product}

\begin{definition}[Direct product]
  Given groups $G$ and $H$, the direct product $G \times H$ is defined as follows:

  The underlying set is the Cartesian product, $G \times H$. That is, the
  ordered pairs $\left(g,h\right)$, where $g \in G$ and $h \in H$. 
  The binary operation on $G \times H$ is defined component-wise:
  \[
  \left(g_1,h_1\right)\left(g_2,h_2\right) =
  \left(g_1 \cdot g_2, h_1 \circ h_2\right)
  \]
  The resulting algebraic object satisfies the axioms for a group.
  See \cite{wiki:directproduct}.

  The direct product of 2 \mynameref{def:abeliangroup}s is also called
  \mynameref{def:directsum} 
  
  \label{def:directproduct}
\end{definition}

\begin{property}[Direct product of groups]
  Let $G_1$, $G_2$ - \mynameref{def:group}s and $G = G_1 \times G_2$ -
  \mynameref{def:directproduct} of the groups. Then
  \begin{enumerate}
  \item $G_1 \cong \left(G_1, 1_{G_2}\right)$ and
    $G_2 \cong \left(1_{G_1}, G_2\right)$
  \item $G_1$ and $G_2$ are \mynameref{def:normalsubgroup}s in $G$
  \end{enumerate}
  See \cite{wiki:directproduct}.
  \label{property:directproduct}
\end{property}

\begin{property}[Quotient of direct product]
  Let $G_1$, $G_2$ - \mynameref{def:group}s and $G = G_1 \times G_2$ -
  \mynameref{def:directproduct} of the groups.
  Then
  \[
  G/G_1 \cong G_2
  \]
  and
  \[
  G/G_2 \cong G_1
  \]
  \label{property:directproductquotient}
  \begin{proof}
    Lets prove the first claim:
    $G/G_1 \cong G_2$ (the second one is analogous).
    Consider projection
    $\pi: G \xrightarrow[(g_1, g_2) \to (1_{G_1}, g_2)]{} G_2$. The
    $\pi$ is \mynameref{def:homomorphism}. Really
    let $a = (a_1, a_2), b = (b_1, b_2) \in G$ where
    $a_{1}, b_1 \in G_1$, $a_2, b_{2} \in G_2$:
    \begin{eqnarray}
      \pi\left(a \cdot b\right) = \pi\left(
      (a_1, a_2) \cdot (b_1, b_2)
      \right) =
      \nonumber \\
      = \pi\left(
      (a_1 b_1, a_2 b_2)
      \right) = a_2 b_2 =
      \pi\left(a\right) \pi\left(b\right)
      \nonumber
    \end{eqnarray}
    As result $\pi$ is a \mynameref{def:homomorphism}.
    
    The $\pi$ is also a \mynameref{def:surjection} because $\forall a_2
    \in G_2$ $\exists a \in G$ such that $\pi(a) = a_2$. Really we can
    use $a = (1_{G_1}, a_2)$.
    
    Therefore by \mynameref{thm:firstisomorphism} one can get
    \[
    G/\ker{\pi} \cong G_2,
    \]
    but $\forall g_1 \in G_1$ we have $(g_1, 1_{G_2}) \in \ker{\pi}$.
    And conversely $\forall k \in \ker \pi$ we have $k = (k_1, k_2)$
    where $k_1 \in G_1$ and $k_2 = 1_{G_2}$.
    As result (see property \ref{property:directproduct})
    \[
    \ker \pi = \left(G_1, 1_{G_2}\right) \cong G_1.
    \]
    Therefore
    \[
    G/G_1 \cong G_2.
    \]
  \end{proof}
\end{property}

\subsection{Sylow theorems}

\begin{corollary}[Sylow]
  Given a finite group $G$ and a prime number $p$ dividing the order of $G$,
  then there exists an element (and hence a subgroup) of order $p$ in
  $G$ \cite{wiki:sylow}
  \label{cor:sylow}
\end{corollary}

\subsection{Abelian group}

\begin{definition}[Abelian group]
  Let we have a \mynameref{def:group} $\left(G, \circ\right)$.
  The group is called an Abelian or commutative if
  $\forall a, b \in G$ it holds $a \circ b = b \circ a$.
  \label{def:abeliangroup}
\end{definition}

\begin{theorem}[About order of element of an Abelian group]
  If $G$ is a finite \mynameref{def:abeliangroup} and $m$ is the maximal
  order of the elements of $G$ then the order of every element of $G$
  divides $m$ 
  \label{thm:abelianelementorder}
\end{theorem}

\begin{theorem}
  Let $G$ is an \mynameref{def:abeliangroup} and $n = \left|G\right|$
  the group order (number of elements) then $\forall g \in G$ the
  following statement holds
  \[
  g^n = e,
  \]
  there $e$ is the group identity.
  \begin{proof}
    Let $m$ is the maximal order of group $G$. In this case by
    \mynameref{thm:lagrange} $m \mid n$ i. e. $n = k_1 m$ where $k_1 \in
    \mathbb{Z}$. Let $l$ is the order of $g$ i.e. $g^l = e$. By the
    theorem \ref{thm:abelianelementorder} $l \mid m$ i.e.
    $m = k_2 l$. Thus
    \[
    g^n = \left(g^m\right)^{k_1} = 
    \left(g^l\right)^{k_2 k_1} = e.
    \]
  \end{proof}
  \label{thm:abelianelement}
\end{theorem}

\begin{theorem}[Cyclic Group is Abelian]
  Let $G$ be a \mynameref{def:cyclicgroup} then $G$ is
  \mynameref{def:abeliangroup} 
  \label{thm:cyclic_group_is_abelian}
  \begin{proof}
    As soon as $G = \left<g\right>$ then
    $\forall x,y \in G, \exists n,m \in \mathbb{N}$ such that
    $x = g^n, y = g^m$. In the case
    \[
    xy = g^n g^m = g^{n+m} = g^m g^n = yx,
    \]
    i.e. $G$ is abelian. 
  \end{proof}
\end{theorem}

\begin{remark}[Not every Abelian group is cyclic]
  The theorem statement cannot be reversed i.e. there exist abelian
  group that are not cyclic. For example well known \mynameref{def:v4}
  $V_4$  that is an
  \mynameref{def:abeliangroup} but not \mynameref{def:cyclicgroup}
\end{remark}

\begin{definition}[Klein four group]
  \label{def:v4}
  The Klein four group $V_4$ is a group of order 4
  \footnote{there are only 2 groups of order 4: $V_4$ and
    $\mathbb{Z}/4\mathbb{Z}$ (the only cyclic group of order 4)}
  The Cayley table for the group is on the table \ref{tab:CayleyV4}
  \cite{wiki:klein4group}. 
  \begin{table}
    \centering
    \caption{Cayley table for $V_4$}
    \label{tab:CayleyV4}
    \begin{tabular}{l|llll}
      \toprule
      $\circ$ & $e$ & $a$ & $b$ & $c$\\
      \midrule
      $e$ & $e$ & $a$ & $b$ & $c$ \\
      $a$ & $a$ & $e$ & $c$ & $b$ \\
      $b$ & $b$ & $c$ & $e$ & $a$ \\
      $c$ & $c$ & $b$ & $a$ & $e$ \\    
      \bottomrule
    \end{tabular}
    \end{table}  
\end{definition}

\begin{example}[Klein four group]
  There are several examples of $V_4$:
  \begin{itemize}
  \item $V_4 \cong \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z}/2\mathbb{Z}$
  \item $V_4 \cong \left(\mathbb{Z}/8\mathbb{Z}\right)^\times \cong \left(\mathbb{Z}/12\mathbb{Z}\right)^\times$
  \end{itemize}
\end{example}

\begin{definition}[Direct sum]
  The direct sum of two abelian groups $A$ and
  $B$ is another abelian group $A \oplus B$ consisting of the ordered
  pairs
  $\left(a, b\right)$ where $a \in A$ and $b \in B$.
  \cite{wiki:directsum}
  See also \mynameref{def:directproduct}.
  
  \label{def:directsum}
\end{definition}

\begin{definition}[Finitely generated abelian group]
  An \mynameref{def:abeliangroup} $(G, +)$ is called finitely generated
  \cite{wiki:fgagroup} 
  if there exist finitely many elements $x_1, \dots, x_s$ in $G$ such that
  $\forall x \in G$:
  \begin{equation}
    x = n_1 x_1 + \dots + n_s x_s
    \label{eq:fgagroup}
  \end{equation}
  with $n_i \in \mathbb{Z}$. In this case we say that $\{x_1, \dots,
  x_s\}$ is a generating set of $G$.

  In the (\ref{eq:fgagroup}) we have the following:
  \[
  n_i x_i = \underbrace{x_i + \dots x_i}_{n_i \text{ times}}
  \]
  \label{def:fgagroup}
\end{definition}

\begin{theorem}[The fundamental theorem of finitely generated abelian
    groups]
  Every \mynameref{def:fgagroup} $G$ is isomorphic to a
  \mynameref{def:directsum} of primary cyclic groups and infinite cyclic
  groups. A primary cyclic group is one whose order is a power of a
  prime. That is, every finitely generated abelian group is isomorphic
  to a group of the form
  \[
  \mathbb{Z}^n \oplus \mathbb{Z}_{q_1} \oplus
  \dots \oplus \mathbb{Z}_{q_t}
  \]
  where the rank $n \ge 0$, and the numbers $q_1, \dots , q_t$ are
  powers of (not 
  necessarily distinct) prime numbers. In particular, $G$ is finite if
  and only if $n = 0$. The values of $n, q_1, \dots , q_t$ are (up to
  rearranging the indices) uniquely determined by $G$. 
  The statement was took from \cite{wiki:fgagroup}.
  \label{thm:fgagroup}
\end{theorem}

\begin{theorem}[Simple subgroup of an abelian group]
  Every non-simple abelian group has a simple normal subgroup.
  ??? add link ???
  \label{thm:simple_subgroup_of_abelian}
\end{theorem}
  
\section{Permutations}

\begin{example}[Permutation]
  The following permutation
  \[ \pi = 
  \begin{array}{c}
    1 \to 2 \\
    2 \to 5 \\
    3 \to 4 \\
    4 \to 3 \\
    5 \to 1 
  \end{array}
  \]
  can be also written in different forms. The most common one is the following:
  \[
  \pi = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    2 & 5 & 4 & 3 & 1
  \end{pmatrix}.
  \]
  In the permutation we can see 2 cycles:
  $1 \to 2 \to 5 \to 1$ and $3 \to 4 \to 3$. The first cycle can be
  written as $(1,2,5)$ (or $(5,1,2)$ or $(2,5,1)$) and the second
  one as $(3,4)$ (or $(4,3)$). The cycles gives us the shortest form
  of writing the permutation:
  \[
  \pi = (1,2,5)(3,4) = (3,4)(5,1,2).
  \]
  
  If we have 2 permutations
  \[
  \pi_1 = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    3 & 1 & 5 & 2 & 4
  \end{pmatrix}.
  \]
  and
  \[
  \pi_2 = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    2 & 5 & 4 & 3 & 1
  \end{pmatrix}.
  \]
  then we can combine them into the new one (via a multiplication)
  \[ \pi = \pi_1 \pi_2 = 
  \begin{array}{c}
    1 \to 2 \to 1 \\
    2 \to 5 \to 4\\
    3 \to 4 \to 2\\
    4 \to 3 \to 5\\
    5 \to 1 \to 3 
  \end{array} =
  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    1 & 4 & 2 & 5 & 3
  \end{pmatrix} = (1)(2,4,5,3) = (2,4,5,3)
  \]

  We have identity element
  \[
  e =  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    1 & 2 & 3 & 4 & 5
  \end{pmatrix}
  \]
  such that $\forall \pi: \pi e = e \pi = \pi$.
  
  For every $\pi$ we can define $\pi^{-1}$ such that
  $\pi \pi^{-1} = \pi^{-1} \pi = e$.

  For our example
  \[
  \pi = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    2 & 5 & 4 & 3 & 1
  \end{pmatrix} = (1,2,5)(3,4)
  \]
  we have
  \[
  \pi^{-1} = \begin{pmatrix}   
    2 & 5 & 4 & 3 & 1 \\
    1 & 2 & 3 & 4 & 5 
  \end{pmatrix} =
  \begin{pmatrix}   
    1 & 2 & 3 & 4 & 5 \\
    5 & 1 & 4 & 3 & 2 
  \end{pmatrix} = (1,5,2)(3,4)
  \]

  As result we have a \mynameref{def:group} of permutations.
  \label{ex:permutation}
\end{example}

\begin{definition}[Parity of a permutation]
  When $X$ is a finite set of at least two elements, the permutations of
  X (i.e. the bijective functions from $X$ to $X$) fall into two classes
  of equal size: the even permutations and the odd permutations. If
  any total ordering of $X$ is fixed, the parity (oddness or evenness)
  of a permutation $\sigma$ of $X$ can be defined as the
  parity of the number of inversions for $\sigma$, i.e., of pairs of elements
  $x, y$ of $X$ such that $x < y$ and $\sigma (x) > \sigma (y)$
  \cite{wiki:paritypermutation}.  
  \label{def:paritypermutation}
\end{definition}

\begin{example}[Parity of a permutation]
  For the following permutation $(2,5,4,1,3)$ we have the following
  inversions
  \begin{eqnarray}
    (2,5,4,1,3) \to_{(1,2)}
    (1,5,4,2,3) \to_{(5,2)}
    \nonumber \\
    (1,2,4,5,3) \to_{(3,4)}
    (1,2,3,5,4) \to_{(5,4)}
    (1,2,3,4,5)
    \nonumber
  \end{eqnarray}
  We have made 4 inversions and as result the permutation is even.

  The same result can be got if we use the following equation $l - 1$
  where $l$ is the circle length (5 in our case) 
  \label{ex:paritypermutation}
\end{example}

\begin{definition}[Alternating group]
  Alternating group \cite{wiki:alteringgroup} is the group of even
  permutations (see definition \ref{def:paritypermutation}) of a finite 
  set. The alternating group on a set of $n$ elements is called the
  alternating group of degree n, or the alternating group on n letters
  and denoted by $A_n$.
  \label{def:alternatinggroup}
\end{definition}

\begin{example}[$S_n$ group]
  If we a have a permutation of $n$ elements then it's possible to do
  by means of $n!$ ways.
  \label{ex:sngroup}
\end{example}

\begin{example}[$S_1$ group]
  $S_1$ permutation of 1 element consists of only one element $e$ -
  the simplest possible group
  \label{ex:s1group}
\end{example}

\begin{example}[$S_2$ group]
  $S_2$ permutation consists of 2 elements:
  \begin{enumerate}
  \item identity:
    \(
    e = \begin{pmatrix}
      1 & 2 \\
      1 & 2
    \end{pmatrix}
    \) 
  \item transposition:
    \(
    \tau = \begin{pmatrix}
      1 & 2 \\
      2 & 1
    \end{pmatrix}
    \) 
  \end{enumerate}
  It's easy to see that the Cayley table has the form \ref{tab:CayleyS2}
    \begin{table}
    \centering
    \caption{Cayley table for $S_2$}
    \label{tab:CayleyS2}
    \begin{tabular}{l|ll}
      \toprule
      $\circ$ & $e$ & $\tau$ \\
      \midrule
      $e$ & $e$ & $\tau$ \\
      $\tau$ & $\tau$ & $e$ \\
      \bottomrule
    \end{tabular}
    \end{table}
  \label{ex:s2group}
\end{example}

\begin{example}[$S_3$ group]
    $S_3$ permutation consists of 6 elements: $e, \tau, \tau_1, \tau_2,
    \sigma, \sigma_1$. The most important are $e, \tau$ and $\sigma$
    and all others can be obtained from this ones (see table
    \ref{tab:CayleyS3}).
  \begin{enumerate}
  \item identity
    \(
    e = \begin{pmatrix}
      1 & 2 & 3\\
      1 & 2 & 3
    \end{pmatrix}
    \) 
  \item transposition:
    \(
    \tau = \begin{pmatrix}
      1 & 2 & 3\\
      2 & 1 & 3
    \end{pmatrix}
    \) 
  \item circle:
    \(
    \sigma = \begin{pmatrix}
      1 & 2 & 3\\
      2 & 3 & 1
    \end{pmatrix}
    \) 
  \end{enumerate}

  Another elements of $S_3$:
  \(
  \tau_1 = \begin{pmatrix}
    1 & 2 & 3\\
    1 & 3 & 2
  \end{pmatrix}
  \),
  \(
  \tau_2 = \begin{pmatrix}
    1 & 2 & 3\\
    2 & 1 & 3
  \end{pmatrix}
  \) and
  \(
  \sigma_1 = \begin{pmatrix}
    1 & 2 & 3\\
    3 & 1 & 2
  \end{pmatrix}
  \).    

  \begin{table}
    \centering
    \caption{Cayley table for $S_3$ \cite{wiki:permutationgroups}}
    \label{tab:CayleyS3}
    \begin{tabular}{l|llllll}
      \toprule
      $\circ$ & $e$ & $\sigma$ & $\sigma_1$ & $\tau$ & $\tau_1$ & $\tau_2$\\
      \midrule
      $e$ & $e$ & $\sigma$ & $\sigma_1$ & $\tau$ & $\tau_1$ & $\tau_2$\\
      $\sigma$ & $\sigma$ & $\sigma_1$ & $e$ & $\tau_2$ & $\tau$ & $\tau_1$\\
      $\sigma_1$ & $\sigma_1$ & $e$ & $\sigma$ & $\tau_1$ & $\tau_2$ & $\tau$\\
      $\tau$ & $\tau$ & $\tau_1$ & $\tau_2$ & $e$ & $\sigma_1$ & $\sigma$\\
      $\tau_1$ & $\tau_1$ & $\tau_2$ & $\tau$ & $\sigma$ & $e$ & $\sigma_1$\\
      $\tau_2$ & $\tau_2$ & $\tau$ & $\tau_1$ & $\sigma_1$ & $\sigma$ & $e$\\
      \bottomrule
    \end{tabular}
  \end{table}
  As we can see from the table \ref{tab:CayleyS3} the elements $e,
  \sigma, \sigma_1$ forms a subgroup of $S_3$ moreover all the
  permutation (see definition \ref{def:paritypermutation}). I.e. there
  we will have \mynameref{def:alternatinggroup} $A_3$.
  \label{ex:s3group}
\end{example}

\begin{example}[$S_3/A_3$ quotient group]
  Lets consider the following \mynameref{def:quotientgroup}
  $S_3/A_3$. As we can see all elements of $S_3$ can be divided into 2
  classes each of them with size $3 = \left|A_3\right|$: $E= A_3 =
  \left\{e, \sigma, \sigma_1\right\}$ 
  and $G = \left\{\tau, \tau_1, \tau_2\right\}$. If we take an element
  $x_1 \in E$ and multiply it on another element of $x_2 \in E$ we
  will get $x_1 x_2 \in E$ (see table \ref{tab:CayleyS3}) i.e. $E
  \cdot E =
  E$. For $G$ we can get $G \cdot G = E$ and $E \cdot G = G \cdot E =
  G$. Therefore $S_3/A_3 = \{E, G\}$ forms a group of order 2. Thus
  \[
  S_3/A_3 \cong \mathbb{Z}/2\mathbb{Z}
  \]
  \label{ex:s3a3quotientgroup}
\end{example}

\begin{definition}[Cycle]
  A cyclic permutation (or cycle) is a permutation of the elements of
  some set $X$ which maps the elements of some subset $S$ of $X$ to each
  other in a cyclic fashion, while fixing (that is, mapping to
  themselves) all other elements of $X$. If $S$ has $k$ elements, the cycle
  is called a $k$-cycle \cite{wiki:cyclicpermutation}.
  \label{def:cycle}
\end{definition}

\begin{example}[Cycle]
  The following permutation is a 3-cycle:
  \[
  (1,2,3) = \begin{array}{c}
                1 \to 2 \\
                2 \to 3 \\
                3 \to 1 
              \end{array}
  \]
  \label{ex:cycle}
\end{example}

\begin{definition}[Transposition]
  A cycle with only two elements is called a transposition.
  \cite{wiki:cyclicpermutation}
  \label{def:transposition}
\end{definition}

\begin{example}[Transposition]
  The following permutation is a transposition:
  \[
  (1,2) = \begin{array}{c}
                1 \to 2 \\
                2 \to 1 
              \end{array}
  \]
  \label{ex:transposition}
  See also example \ref{ex:transposition_product}
\end{example}

\begin{example}[Transposition product]
  \label{ex:transposition_product}
  The example shows a product of 2 \mynameref{def:transposition}s with a
  same element:
  \begin{eqnarray}
    (a,c)(a,b) = 
    \begin{array}{c}
      a \to b \\
      b \to a \to c\\
      c \to a 
    \end{array} = (a,b,c)
    \nonumber
  \end{eqnarray}
\end{example}


\begin{theorem}
  Every permutation can be represented as a product of
  \mynameref{def:transposition}s
  \begin{proof}
    This is because any cycle $(a_1, a_2, a_3, \dots, a_{n-1}, a_n)$
    can be represented as a product of transpositions as follows
    \[
    (a_1, a_2, a_3, \dots, a_{n-1}, a_n) =
    (a_1, a_n)(a_1, a_{n-1}) \dots (a_1, a_3) (a_1, a_2)
    \]
  \end{proof}
  \label{thm:permutationrepresent}
\end{theorem}

\begin{corollary}
  $S_n$ is generated by any combination of a \mynameref{def:transposition} and
  $n$-cycle if and only if $n$ is prime
  \label{cor:sn}
  \begin{proof}
    See \cite{mathstackexchange:sn}
  \end{proof}
\end{corollary}

\section{Rings and Fields}

\subsection{Rings}

\begin{definition}[Ring]
  Consider a set $R$ with 2 binary operations defined. The first one
  $\oplus$ (addition) and elements of $R$ forms an
  \mynameref{def:abeliangroup}
  under this operation. The second one is $\odot$ (multiplication) and
  the elements of $R$ forms a \mynameref{def:monoid} under 
  the operation. The two binary operations are connected each other
  via the following distributive law
  \begin{itemize}
  \item Left distributivity:
    $\forall a,b,c \in R$:
    $a \odot \left(b \oplus c\right) =
    a \odot b \oplus a \odot c$
  \item Right distributivity:
    $\forall a,b,c \in R$:
    $\left( a \oplus b \right) \odot c =
    a \odot c \oplus b \odot c$
    
  The identity element for $\left(R, \oplus\right)$ is denoted as $0$
  (additive identity).
  The identity element for $\left(R, \odot\right)$ is denoted as $1$
  (multiplicative identity).

  The inverse element to $a$ in $\left(R, \oplus\right)$ is denoted as $-a$
  \end{itemize}

  In this case $\left(R, \oplus, \odot\right)$ is called as ring.
  \label{def:ring}
\end{definition}

The \mynameref{def:ring} is a generalization of integer numbers conception.
\begin{example}[Ring of integers $\mathbb{Z}$]
  The set of integer numbers $\mathbb{Z}$ forms a \mynameref{def:ring}
  under $+$ and $\cdot$ operations i.e. addition $\oplus$ is
  $+$ and multiplication $\odot$ is $\cdot$. Thus for integer
  numbers we have the following \mynameref{def:ring}:
  $\left(\mathbb{Z}, +, \cdot\right)$
  \label{ex:ring}
\end{example}

\begin{definition}[Multiplicative group]
  If $R$ is a ring then the multiplicative group
  $\left(R\right)^\times$
  is a group of
  invertible elements of $R$ with the defined multiplication operation.
  \label{def:multiplicativegroup}
\end{definition}

\begin{example}[Multiplicative group of integers modulo $n$]
  Lets consider the following group
  $\left(\mathbb{Z}/9\mathbb{Z}\right)^\times =
  \left\{1,2,4,5,7,8\right\}$
  \cite{wiki:multiplicativegroup}

  The group has order 6. The group generator is $2$:
  $2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 7, 2^5 = 5, 2^6 = 1$.
  
  Accordingly theorem
  \ref{thm:subgroupofcyclicgroup}, there are only 2
  \mynameref{def:propersubgroup} not equal to $id$.

  One of them is a cyclic group of order 2: $\left\{1,8\right\} \cong
  \mathbb{Z}/2\mathbb{Z}$.

  Another one is also cyclic and has order 3: $\left\{1, 4, 7\right\}
  \cong 
  \mathbb{Z}/3\mathbb{Z}$.
  
  \label{ex:multiplicativegroup}
\end{example}

\subsection{Ideals}

\begin{definition}[Ideal]
  \label{def:ideal}
  Lets we have the \mynameref{def:ring}
  $\left(R, \oplus, \odot\right)$. Subset $I \subset R$ will be an
  ideal if it satisfied the following conditions
  \begin{enumerate}
  \item $\left(I, \oplus\right)$ is \mynameref{def:subgroup} of
    $\left(R, \oplus\right)$
  \item $\forall i \in I$ and $\forall r \in R$:
    $i \odot r \in I$ and $r \odot i \in I$
  \end{enumerate}
\end{definition}

\begin{example}[Ideal $2 \mathbb{Z}$]
  Consider even numbers. They forms an \mynameref{def:ideal} in
  $\mathbb{Z}$. Because multiplication of any even number to any
  integer is an even. The ideal's symbolic name is $2 \mathbb{Z}$.
  \label{ex:ideal}
\end{example}

\begin{example}[Ring of integers modulo $n$: $\mathbb{Z}/n\mathbb{Z}$]
  Let $n \in \mathbb{Z}$ and $n > 1$. Then $n \mathbb{Z}$ is an
  \mynameref{def:ideal}.

  Two integer $a, b \in \mathbb{Z}$  are said to be congruent modulo
  $n$, written
  \[
  a \equiv b ( \mod n )
  \]
  if their difference $a - b$ is an integer multiple of $n$.

  Thus we have a separation of set $\mathbb{Z}$ into subsets of
  numbers that are congruent. Each subset has the following form
  \[
  \left\{r\right\}_n = r + n \mathbb{Z} =
  \left\{r + n k \mid k \in \mathbb{Z}\right\}
  \],
  thus
  \[
  \mathbb{Z} = \left\{0\right\}_n \cup \left\{1\right\}_n
  \cup \dots \cup \left\{n-1\right\}_n.
  \]

  Very often use the following notation
  \[
  \bar{r} = \left\{r\right\}_n.
  \]

  We can define the following operations
  \begin{eqnarray}
    \bar{k} \oplus \bar{l} = \overline{k + l}
    \nonumber \\
    \bar{k} \odot \bar{l} = \overline{k \cdot l}
    \nonumber
  \end{eqnarray}
  
  The \mynameref{def:ring} where the objects are defined is called as
  $\mathbb{Z}/n\mathbb{Z}$.
  \label{ex:intmodulo}
\end{example}

\begin{definition}[Ideal generated by a set]
  Let $R$ be a \mynameref{def:ring} and $S$ is a sub set of $R$.
  Consider the following set
  \[
  I = \left\{
  r_1 s_1 + \dots + r_n s_n \vert n \in \mathbb{N}, r_i \in R, s_i \in S
  \right\}
  \]
  $I$ is called by an ideal generated by set $S$ if
  $\forall r \in R, i \in I: r \cdot i \in I$.

  The sum in the definition of the ideal should be finite. The ring is
  assumed commutative in the definition.
  \label{def:idealset}
\end{definition}

\begin{definition}[Principal ideal]
  The ideal that is generated by one element $a$ is called as
  principal ideal and is denoted as $\left(a\right)$ i.e.
  left principal ideal:
  $\left(a\right) = \left\{r a \mid \forall r \in R\right\}$ and
  right principal ideal:
  $\left(a\right) = \left\{a r \mid \forall r \in R\right\}$
  \label{def:prinicipalideal}
\end{definition}

\begin{definition}[Integral domain]
In mathematics, and specifically in abstract algebra, an integral
domain is a nonzero commutative \mynameref{def:ring} in which the
product of any two nonzero elements is nonzero.
\label{def:integraldomain}
\end{definition}

\begin{definition}[Principal ideal domain]
  In abstract algebra, a principal ideal domain, or PID, is an
  \mynameref{def:integraldomain} in which every ideal is principal, i.e., can be
  generated by a single element.
  \label{def:pid}
\end{definition}

\begin{definition}[Maximal ideal]
  A maximal ideal is an ideal that is maximal (with respect to set
  inclusion) amongst all \mynameref{def:properideal}s i.e.
  $I$ is a maximal ideal of a ring $R$ if there are no other ideals
  contained between $I$ and $R$ \cite{wiki:maxideal}.
\label{def:maxideal}
\end{definition}

\begin{example}[Maximal ideal]
  If $F$ is a \mynameref{def:field} then the only maximal ideal is
  $\{0\}$ \cite{wiki:maxideal}.
  \label{ex:maxideal}
\end{example}

\begin{definition}[Prime ideal]
  \label {def:primeideal}
  An ideal $I$ of a commutative ring $R$ is prime if it has the
  following 2 properties \cite{wiki:primeideal}
  \footnote{
    There is a generalization of prime numbers in arithmetic
  }
  \begin{enumerate}
  \item If $a,b \in R$ such that $ab \in I$ then $a \in I$ or $b \in I$
  \item$I$ is not equal the whole ring $R$
  \end{enumerate}
\end{definition}

\begin{lemma}[$n\mathbb{Z}$ prime ideal]
  A positive integer $n$ is a prime if and only if $n\mathbb{Z}$ is a
  \mynameref{def:primeideal} in $\mathbb{Z}$ \cite{wiki:primeideal}
  \label{lem:primeideal_in_Z}
\end{lemma}

\begin{lemma}
  All nonzero \mynameref{def:primeideal}s are maximal in a principal
  ideal domain \cite{wiki:maxideal}
  \label{lem:primeideal_is_maximal}
\end{lemma}

\begin{definition}[Proper ideal]
$I$ is a proper ideal of a ring $R$ if $I \subsetneq R$.
\label{def:properideal}
\end{definition}

\begin{theorem}[About proper ideal]
  An ideal $I$ of ring $R$ is proper if and only if $1_R \notin I$.
  \label{thm:properideal}
\end{theorem}

\begin{definition}[Quotient ring]
  Quotient ring is a construction where one
  starts with a ring $R$ and a two-sided ideal $I$ in $R$, and constructs a
  new ring, the quotient ring $R/I$, whose elements are the
  \mynameref{def:coset}s of $I$ 
  in $R$ subject to special $+$ and $\cdot$ operations.

  Given a ring $R$ and a two-sided ideal $I \subset R$, we may define
  an equivalence relation $\sim$ on $R$ as follows: 
  $a \sim b$ if and only if $a - b \in I$.
  The equivalence class of the element $a$ in $R$ is given by
  \[
  \bar{a} = \left\{a\right\} = a + I := \left\{ a + r : r \in I \right\}.
  \]
  This equivalence class is also sometimes written as a mod $I$ and
  called the "residue class of a modulo I" (see also example
  \ref{ex:intmodulo}).

  The special $+$ and $\cdot$ operations are defined as follows
  \[
  \forall \bar{x},\bar{y} \in R/I:
  \bar{x} + \bar{y} = \left(x + I\right) + \left(y + I\right) =
  \left(x+y\right) + I = \overline{x+y}.
  \]
  \[
  \forall \bar{x},\bar{y} \in R/I:
  \bar{x} \cdot \bar{y} = \left(x + I\right) \cdot \left(y + I\right) =
  \left(x \cdot y\right) + I = \overline{x \cdot y}.
  \]

  As result we will get the following ring $\left(R/I, +,
  \cdot\right)$ is called the quotient ring of $R$ by $I$.

  See also \mynameref{def:quotientgroup}
  \label{def:quotientring}
\end{definition}

\subsection{Polynomial ring $K\left[X\right]$}

Let we have a commutative \mynameref{def:ring} $K$. Lets create a new
\mynameref{def:ring} $B$ with the following infinite sets as elements:
\begin{equation}
  f = \left(f_0, f_1, \dots \right), \, f_i \in K,
  \label{eq:polynomial}
\end{equation}
such that only finite number of elements of the sets are non zero.

We can define addition and multiplication on $B$ as follows
\begin{eqnarray}
  f + g = \left(f_0 + g_0, f_1 + g_1, \dots \right),
  \nonumber \\
  f \cdot g = h = \left(h_0, h_1, \dots \right),
  \label{eq:polynomialops}
\end{eqnarray}
where
\[
h_k = \sum_{i + j =k} f_i g_j. 
\]

The sequences (\ref{eq:polynomial}) forms a \mynameref{def:ring} with
the following identities:
\begin{itemize}
\item Additive identity: $\left(0, 0, \dots \right)$
\item Multiplicative identity: $\left(1, 0, \dots \right)$
\end{itemize}

The
sequences $k = \left(k, 0, \dots \right)$ added and multiplied as
elements of $K$ this allows say that such elements are elements of
original \mynameref{def:ring} $K$. Thus $K$ is sub-ring of the new ring
$B$.

Let
\begin{eqnarray}
  X = \left(0, 1, 0, \dots \right),
  \nonumber \\
  X^2 = \left(0, 0, 1, \dots \right)
  \nonumber
\end{eqnarray}
thus if we have
\[
f = \left(f_0, f_1, f_2, \dots, f_n, 0, \dots \right),
\]
where $f_n$ is the last non-zero element of (\ref{eq:polynomial}),
when one can get
\[
f = f_0 + f_1 X + f_2 X^2 + \dots + f_n X^n.
\]

\begin{definition}[Polynomial ring]
  The \mynameref{def:ring} of sequences (\ref{eq:polynomial}) with
  operations defined by (\ref{eq:polynomialops}) is called as
  polynomial ring $K\left[X\right]$.
  \label{def:polynomial}
\end{definition}

\begin{lemma}[Bézout]
  Let $a$ and $b$ be nonzero integers and let $d$ be their greatest common
  divisor. Then there exist integers $x$ and $y$ such that 
  \[
  a x + by = d.
  \]
  \label{lem:bezout}
\end{lemma}

\begin{definition}[Monic polynomial]
  Monic polynomial is a univariate polynomial in which the leading
  coefficient (the nonzero coefficient of highest degree) is equal to
  1. Therefore, a monic polynomial has the form
  \[
  x^n + a_{n-1}x^{n-1}+ \dots + a_1 x + a_0
  \]
  \label{def:monicpolynomial}
\end{definition}

\begin{definition}[Irreducible polynomial]
  An irreducible polynomial is, roughly speaking, a non-constant
  polynomial that cannot be factored into the product of two
  non-constant polynomials.
  \label{def:irreducible}
\end{definition}

\begin{example}[Irreducible polynomial]
  The following polynomial is irreducible in
  $\mathbb{R}\left[X\right]$: $X^2 + 1$. The following one is also
  irreducible despite it has a root: $X+1$.
  \label{ex:irreducible}
\end{example}

\begin{theorem}[About irreducible polynomials]
  Let $\pi(X)$ is an \mynameref{def:irreducible} in $K\left[X\right]$ and let
  $\alpha$ be a root of $\pi(X)$ in a some larger field.
  $\forall h(x) \in K\left(X\right)$ if have the following statement:
  $h\left(\alpha\right) = 0$ if and only if $\pi(X) \mid h(X)$ in
  $K\left[X\right]$.
  \begin{proof}
    If $h(X) = \pi(X) g(X)$ then $h(\alpha) = 0$

    From other side let $\pi \nmid h$ in $K\left[X\right]$ this means
    that they are relatively prime in $K\left[X\right]$ and by
    \mynameref{lem:bezout} we can get $Q,R \in K\left[X\right]$ such
    that
    \[
    \pi(X) R(X) + h(X) Q(X) = 1,
    \]
    and especially for $X = \alpha$ we will get that $0 = 1$ that is
    impossible. 
  \end{proof}
  \label{thm:irreduciblediv}
\end{theorem}

\begin{theorem}[About ideal generated by irreducible polynomial]
  Let $P \in K\left[X\right]$ is a polynomial and $I = \left(P\right)$ is
  an \mynameref{def:ideal} generated by the polynomial. The $I$ is
  \mynameref{def:maxideal} if and only if $P$ is irreducible in
  $K\left[X\right]$
  \begin{proof}
    Let $P$ is reducible i.e. $P = G F$. In the case $(P) \subset (G)$
    and $(P) \subset (F)$ i.e. by definition it is not a maximal
    ideal.

    If $P$ is irreducible then $K\left[X\right]/(P)$ is a field (see
     claim \ref{claim:lec1_sec14})
    and by theorem \ref{thm:maxideal} $(P)$
    is a maximal ideal.
  \end{proof}
  \label{thm:irreducibleideal}
\end{theorem}

\subsection{Fields}

\begin{definition}[Field]
  The ring $\left(R, \oplus, \odot\right)$ is called as a field if
  $\left(R \setminus \{0\}, \odot\right)$ is an \mynameref{def:abeliangroup}.

  The inverse element to $a$ in
  $\left(R \setminus\{0\}, \odot\right)$ is denoted as $a^{-1}$
  \label{def:field}
\end{definition}

\begin{example}[Field $\mathbb{Q}$]
  Note that $\mathbb{Z}$ is not a field because not for every integer
  number an inverse exists. But if we consider a set of fractions
  $\mathbb{Q} = \left\{a/b \mid a \in \mathbb{Z}, b \in
  \mathbb{Z}\setminus\{0\}\right\}$ when it will be a field.

  The
  inverse element to $a/b$  in
  $\left(\mathbb{Q}\setminus\{0\}, \cdot\right)$  will be $b/a$.
  \label{ex:field}
\end{example}

\begin{definition}[Unique factorization domain]
   Unique factorization domain (UFD) is a commutative ring, which is
   an \mynameref{def:integraldomain}, and in which every non-zero non-unit element
   can be written as a product of prime elements (or irreducible
   elements), uniquely up to order and units, analogous to the
   fundamental theorem of arithmetic for the integers. 
  \label{def:ufd}
\end{definition}

\begin{theorem}[About Quotient Ring and Maximal Ideal]
  Let $\left(R, +, \cdot\right)$ is a commutative \mynameref{def:ring}
  with additive identity $0_R$ and multiplicative identity $1_R$. Let
  $I$ be an \mynameref{def:ideal} of $R$ then $I$ is
  \mynameref{def:maxideal} if and only if \mynameref{def:quotientring}
  $R/I$ is a \mynameref{def:field}
  \label{thm:maxideal}
  \begin{proof}
    See the end of section \ref{sec:lec2_ideals}.
  \end{proof}
\end{theorem}

\begin{definition}[Fraction field]
  The field of fractions of an integral domain is the smallest field
  in which it can be embedded. The elements of the field of fractions
  of the integral domain $R$ are equivalence classes
  (see the construction below) written as $\frac{a}{b}$ with $a, b \in
  R$ and $b\neq 0$. The field of
  fractions of $R$ is sometimes denoted by
  $\mathrm{Quot} (R)$ or $\mathrm {Frac}(R)$ \cite{wiki:fractionfield}. 
  \label{def:fractionfield}
\end{definition}

\subsection{Characters}

\begin{definition}[Character]
  For an abelian group $G$, finite or infinite, a character of $G$ is
  a group homomorphism $\phi: G \to F^\times$ where $F$ is a field.

  The definition was taken from \cite{bib:KeithConradLinearchar}
  \label{def:character}
\end{definition}

\begin{example}[Character]
  A field homomorphism $K \to F$ is a character by restricting it to the
  non- zero elements of $K$ (that is, using $G = K^\times$) and ignoring the
  additive aspect of a field homomorphism.  

  The example was taken from \cite{bib:KeithConradLinearchar}
  \label{ex:character}
\end{example}

\begin{theorem}[Dedekind]
  If we have $n$ distinct \mynameref{def:character}s $\phi_1, \dots,
  \phi_n: G \to F^\times$ then they are linearly independent i.e. if
  $c_1, \dots, c_n \in F$ satisfy
  \[
  c_1 \phi_1(g) + \dots + c_n \phi_n(g) = 0
  \]
  for all $g \in G$ then $c_1 = \dots = c_n = 0$
  (see also \cite{bib:KeithConradLinearchar}).
  \label{thm:dedekind}
\end{theorem}

\section{Modules and Vector spaces}

\subsection{Modules}

A module over a ring is a generalization of the notion of vector space
over a field, wherein the corresponding scalars are the elements of an
arbitrary given ring (with identity) and a multiplication (on the left
and/or on the right) is defined between elements of the ring and
elements of the module.

\begin{definition}[Module]
  \label{def:module}
  Let $R$ is a \mynameref{def:ring} and $1_R$ is it's multiplicative
  identity. A left R-module $M$ consists of an \mynameref{def:abeliangroup}
  $\left(M, +\right)$ and an operation $\cdot: R \times M \to M$ such
  that $\forall r,s \in R$ and $\forall x,y \in M$ the following
  relations are hold:
  \begin{enumerate}
  \item $r \cdot \left(x+y\right) = r \cdot x + r \cdot y$
  \item $\left(r + s \right) \cdot x = r \cdot x + s \cdot x$
  \item $\left(rs\right) \cdot x = r \cdot \left(s \cdot x\right)$
  \item $1_R \cdot x = x$
  \end{enumerate}
\end{definition}

\begin{example}[Module]
  If $K$ is a \mynameref{def:field} then concepts of
  K-\mynameref{def:vectorspace} and $K$-module are the same
\end{example}

\begin{definition}[Generating set of a module]
  A generating set $G$ of a module $M$ over a ring $R$ is a subset of
  $M$ such that the smallest submodule of $M$ containing $G$ is $M$
  itself \cite{wiki:gsmodule}
  \label{def:gsmodule}
\end{definition}

\begin{definition}[Free module]
  \label{def:freemodule}
  The \mynameref{def:module} that has a basis (i.e. linearly independent
  generating set) 
  is called as free module \cite{wiki:freemodule}.

  For a $R$-module $M$ the set $E \subseteq M$ is a basic for $M$ if
  \begin{enumerate}
  \item $E$ is a generating set (see definition \ref{def:gsmodule})
    for $M$ i.e. $\forall m \in M$ 
    $\exists n < \infty$: $\exists e_i \in E, r_i \in R$:
    $m = \sum_{i = 1}^n r_i e_i$
  \item $E$ is linearly independent, i.e. if $r_1 e_1 + \dots + r_n
    e_n = 0_M$ for distinct elements $e_1, \dots, e_n \in E$ then
    $r_1 = \dots = r_n = 0_R$.
  \end{enumerate}
\end{definition}

\begin{definition}[Rank of free module]
  The cardinality of any (and therefore every) basis is called the
  rank of the free module $M$ \cite{wiki:freemodule}.
  \label{def:rankfreemodule}
\end{definition}

\begin{definition}[Direct sum of modules]
  In abstract algebra, the direct sum is a construction which combines
  several modules into a new, larger module. The direct sum of modules
  is the smallest module which contains the given modules as
  submodules with no "unnecessary" constraints, making it an example
  of a coproduct. Contrast with the direct product, which is the dual
  notion \cite{wiki:directsummodules}.
  \label{def:directsummodules}
\end{definition}

\begin{example}[Direct sum of modules]
  If we have 2 \mynameref{def:freemodule}s $M$ and $N$ with bases $m_1,
  m_2, \dots, m_m$ and $n_1, n_2, \dots, n_n$. Then the
  \mynameref{def:directsummodules} $A = M \oplus N$ will also be a free
  module with composite basis: $m_1, m_2, \dots, m_m, n_1, n_2, \dots, n_n$
  \label{ex:directsummodules}
\end{example}

\begin{definition}[Finitely generated module]
  Finitely generated module is a module that has a finite generating
  set (see also definition \ref{def:gsmodule}) \cite{wiki:fgmodule}.
  \label{def:fgmodule}
\end{definition}

\begin{definition}[Cyclic module]
  A (left) $R$-\mynameref{def:module} $M$ is called cyclic if $M$ can be
  generated by 
  a single element i.e.
  \[
  M = \left<x\right>=R x = \left\{rx \mid r \in R\right\}
  \]
  for some $x \in M$ \cite{wiki:cyclicmodule}.
  \label{def:cyclicmodule}
\end{definition}

\begin{claim}
  $M$ is a cyclic $R$ module if and only if exists left ideal $I
  \subset R$ such that $M \cong R/I$
  \begin{proof}
    See \cite{mathstackexchange:cyclicmodule}. Note that
    \cite{bib:lang} p. 149 has
    the claim as a definition of the \mynameref{def:cyclicmodule}.
  \end{proof}
  \label{claim:cyclicmodule}
\end{claim}

\subsection{Linear algebra}

\begin{definition}[Vector space]
  \label{def:vectorspace}
  Let $F$ is a \mynameref{def:field}. The set $V$ is called as vector
  space under $F$ if the following conditions are satisfied
  \begin{enumerate}
  \item We have a binary operation $V \times V \rightarrow V$
    (addition): $(x,y) \rightarrow x + y$ with the following
    properties:
    \begin{enumerate}
    \item $x + y = y + x$
    \item $(x + y) + z = x + ( y + z )$
    \item $\exists 0 \in V$ such that $\forall x \in V: x + 0 = x$
    \item $\forall x \in V \exists -x \in V$ such that $x + (-x) = x -
      x = 0$ 
    \end{enumerate}    
  \item We have a binary operation $F \times V \rightarrow V$ (scalar
    multiplication) with the following properties
    \begin{enumerate}
    \item $1_F \cdot x = x$
    \item $\forall a,b \in F, x \in V$: $a\cdot\left(b \cdot x\right)
      = \left(a b\right) \cdot x$.
    \item $\forall a,b \in F, x \in V$:
      $(a+b)\cdot x = a \cdot x + b \cdot x$
    \item $\forall a \in F, x, y \in V$:
      $a\cdot(x+y) = a\cdot x + a \cdot y$
    \end{enumerate}        
  \end{enumerate}
\end{definition}

\begin{lemma}[About vector space isomorphism]
  2 vector spaces $L$ and $M$ with same dimension $dim L = dim M$ then
  there exists an \mynameref{def:isomorphism} between them
  \label{lem:vsisomorphism}
\end{lemma}

\begin{definition}[Image]
  The image or range of a linear map $f: V \to W$ is the following
  set \cite{wiki:linearmap}:
  \[
  \Ima f = \left\{
  w \in W: w = f(v), v \in V
  \right\}
  \]
  \label{def:image}
\end{definition}

\begin{definition}[Kernel]
  The kernel of a linear map $f: V \to W$ is the following
  set \cite{wiki:kernel}:
  \[
  \ker f = \left\{
  v \in V: f(v) = 0
  \right\}
  \]
  \label{def:kernel}
\end{definition}


\begin{definition}[Rank]
  The rank of a linear map $f: V \to W$ is dimension of
  \mynameref{def:image}: $rg f = \dim \Ima f$ \cite{wiki:rank}:
  \label{def:rank}
\end{definition}

\begin{definition}[Nullity]
  The nullity of a linear map $f: V \to W$ is dimension of
  \mynameref{def:kernel}: $nul f = \dim \ker f$ \cite{wiki:kernel}:
  \label{def:nullity}
\end{definition}

\begin{theorem}[Rank–nullity theorem]
  Let $V$ and $W$ be vector spaces over some field and let $T: V \to
  W$ be a linear map. Then the \mynameref{def:rank} of $T$ is the
  dimension of the image of $T$ and the \mynameref{def:nullity} of $T$
  is the dimension of the kernel of $T$, so we have
  \[
  \dim\left(\Ima T\right) + \dim\left(\ker T\right) = \dim V
  \]
  or, equivalently
  \[
  rg(T) + nul(T) = \dim(V)
  \]
  \label{thm:ranknullity}
  \begin{proof}
    See \cite{wiki:ranknullity}
  \end{proof}
\end{theorem}

\begin{definition}[General linear group of a vector space]
  If $V$ is a \mynameref{def:vectorspace} over field $K$  the general
  linear group of $V$, written $GL\left(V\right)$ or
  $Aut\left(V\right)$, is the group of all automorphisms of $V$,
  i.e. the set of all bijective linear transformations $V \to V$,
  together with functional composition as group operation \cite{wiki:glg}.  
  \label{def:glv}
\end{definition}

\begin{definition}[Dual space]
  Given any vector space $V$ over a field $F$, the dual space $V^\ast$
  is defined as the set of all linear maps $\phi: V \to F$ (linear
  functionals). The dual space $V^\ast$ itself becomes a vector space
  over $F$ when equipped with an addition and scalar multiplication
  satisfying: 
  \begin{eqnarray}
    (\varphi +\psi )(x)=\varphi (x)+\psi (x)
    \nonumber \\
    (a\varphi )(x)=a\left(\varphi (x)\right)
    \nonumber
  \end{eqnarray}
  for all $\phi, \psi \in V^\ast$, $x \in V$, and $a \in F$.

  This is also named as algebraic dual space at \cite{wiki:dualspace}.
  \label{def:dualspace}
\end{definition}

\begin{definition}[Dual basis]
  If $\{e_i\}$ is a basis of $V$ then exists a basis $\{v_j\}$ of
  \mynameref{def:dualspace} such that $v_j(e_i) = \delta_{ij}$ and is
  called as dual basis. 
  \cite{wiki:dualbasis}
  \label{def:dualbasis}
\end{definition}

\begin{definition}[Degenerate bilinear form]
  A degenerate bilinear form $f(x, y)$ on a vector space $V$ is a
  bilinear form such that the map from $V$ to $V^\ast$ (the
  \mynameref{def:dualspace} 
  of $V$) given by $v \to (x \to f(x, v) )$ is not an isomorphism
  \cite{wiki:dbf}. 

  An equivalent definition when $V$ is finite-dimensional is that it
  has a non-trivial kernel: there exist some non-zero $x \in V$ such
  that 
  \(
  \forall y \in V f(x,y) = 0
  \)
  \label{def:degeneratebf}
\end{definition}

\begin{definition}[Non-degenerate bilinear form]
  A nondegenerate or nonsingular form is one that is not degenerate,
  meaning that the map from $V$ to $V^\ast$ (the \mynameref{def:dualspace}
  of $V$) given by $v \to (x \to f(x, v) )$ is an isomorphism
  \cite{wiki:dbf} or equivalently when $V$ is finite-dimensional if
  and only if
  \(
  \forall y \in V f(x,y) = 0
  \)
  implies $x = 0$, i.e. the map $f$ has a trivial kernel.
  \label{def:nondegeneratebf}
\end{definition}

\begin{definition}[Eigenspace]
  Consider a linear map $T: V \to V$.
  The set of all eigenvectors of $T$ corresponding to the same
  eigenvalue, together with the zero vector, is called an eigenspace
  or characteristic space of $T$ \cite{wiki:eigenvalues}
  \label{def:eigenspace}
\end{definition}

\begin{definition}[Diagonalizable map]
  If $V$ is a finite-dimensional vector space, then a linear map
  $T: V \to V$ is called diagonalizable if there exists an ordered
  basis of $V$ with respect to which $T$ is represented by a diagonal
  matrix.

  A linear map $T: V \to V$ is diagonalizable if and only if the sum
  of the dimensions of its 
  eigenspaces is equal to $n = dim(V)$, which is the case if and only if
  there exists a basis of $V$ consisting of eigenvectors of $T$. With
  respect to such a basis, $T$ will be represented by a diagonal
  matrix. The diagonal entries of this matrix are the eigenvalues of
  $T$ \cite{wiki:diagonalizable_matrix}.
  \label{def:diagonalizable_map}
\end{definition}

\begin{theorem}[About eigenvalues of a diagonalizable linear map]
  A linear map $T: V \to V$ with $n = dim(V)$ is diagonalizable if it
  has $n$ distinct eigenvalues \cite{wiki:diagonalizable_matrix}.
  \label{thm:diagonalizable_map_eigenvalues}
\end{theorem}

\begin{theorem}[About invertible matrix]
  Let $A$ be a matrix over $F$. If $A$ is diagonalizable, then so is
  any power of it. Conversely, if $A$ is invertible, $F$ is
  algebraically closed, and $A^n$ is diagonalizable for some $n$ that
  is not an integer multiple of the characteristic of $F$, then $A$ is
  diagonalizable.
  \begin{proof}
    See \cite{wiki:diagonalizable_matrix}
  \end{proof}
  \label{thm:diagonalizable_matrix}
\end{theorem}



\section{Functions aka maps}

\subsection{Functions}

\begin{definition}[Surjection]
  The function $f: X \rightarrow Y$ is surjective (or onto) if
  $\forall y \in Y$, $\exists x \in X$ such that
  $f\left(x\right) = y$.
  \label{def:surjection}
\end{definition}

\begin{definition}[Injection]
  The function $f: X \rightarrow Y$ is injective (or one-to-one function) if
  $\forall x_1, x_2 \in X$, such that $x_1 \ne x_2$ then
  $f\left(x_1\right) \ne f\left(x_2\right)$.
  \label{def:injection}
\end{definition}

\begin{definition}[Bijection]
  The function $f: X \rightarrow Y$ is bijective (or one-to-one
  correspondence) if it is an \mynameref{def:injection} and a
  \mynameref{def:surjection}. 
  \label{def:bijection}
\end{definition}

\begin{definition}[Homomorphism]
  The homomorphism is a function (map) between two sets that preserves
  its algebraic structure. For the case of groups
  $\left(X, \circ\right)$ and $\left(Y, \odot\right)$ the function
  $\phi: X \rightarrow Y$ is called homomorphism if
  $\forall x_1, x_2 \in X$ it holds
  $\phi\left(x_1 \circ x_2\right) = \phi\left(x_1 \right) \odot
  \phi\left( x_2\right)$. 
  \label{def:homomorphism}
\end{definition}

\begin{definition}[Field homomorphism]
  Let \cite{proofwiki:fieldhomomorphism} $\left(F, +, \times\right)$
  and $\left(K, \oplus, \otimes\right)$ are 
  \mynameref{def:field}s. Let $\phi: F \rightarrow K$ is a mapping
  such that both
  $\left(F, +\right) \rightarrow \left(K, \oplus\right)$
  and
  $\left(F, \times\right) \rightarrow \left(K, \otimes\right)$
  are \mynameref{def:homomorphism}s under $\phi$.

  That is $\forall a, b \in F$:
  \begin{enumerate}
  \item $\phi\left(a + b\right) = \phi\left(a\right) \oplus \phi\left(b\right)$
  \item $\phi\left(a \times b\right) = \phi\left(a\right) \otimes \phi\left(b\right)$
  \end{enumerate}

  Then $\phi: \left(F, +, \times\right) \rightarrow \left(K, \oplus,
  \otimes\right)$ is a field homomorphism.
  \label{def:fieldhomomorphism}

  Note that in the lectures we often refer the Field homomorphism as
  just \mynameref{def:homomorphism}.
\end{definition}


\begin{definition}[Isomorphism]
  If a map is \mynameref{def:bijection} as well as
  \mynameref{def:homomorphism} when it is called as isomorphism.

  We use the following symbolic notation for isomorphism between $X$
  and $Y$: $X \cong Y$.
  \label{def:isomorphism}
\end{definition}

\begin{definition}[Endomorphism]
   An endomorphism is a morphism (or homomorphism) from a mathematical
   object to itself \cite{wiki:endomorphism}
   \label{def:endomorphism}
\end{definition}

\begin{definition}[Automorphism]
  Automorphism is an isomorphism from a mathematical object to itself.
  \label{def:automorphism}
\end{definition}

\begin{definition}[Embedding]
  When some object X is said to be embedded in another object $Y$, the
  embedding is given by some injective and structure-preserving map
  $f : X \to Y$. The precise meaning of "structure-preserving" depends on
  the kind of mathematical structure of which $X$ and $Y$ are
  instances.
  
  The fact that a map $f : X \to Y$ is an embedding is often indicated
  by the use of a "hooked arrow", thus: $f:X\hookrightarrow Y$. On the
  other hand, this notation is sometimes reserved for inclusion maps.
  \label{def:embedding}
\end{definition}

\begin{theorem}[First isomorphism]
  Let $G$ is a group and $\phi: G \to H$ is a
  surjective \mynameref{def:homomorphism}. Then if $N = \ker \phi$ we
  have
  \[
  H \cong G/N
  \]
  \label{thm:firstisomorphism}
\end{theorem}

\begin{theorem}[Isomorphism extension theorem]
  Let $F$ is a \mynameref{def:field} and $E$ is an
  \mynameref{def:algebraicextension} of $F$.
  $F'$ is another \mynameref{def:field} and $E'$ the 
  \mynameref{def:algebraicextension} of $F'$.

  If there exists an \mynameref{def:isomorphism} $\phi: F \to F'$ then
  it can be extended to an isomorphism $\tau: E \to E'$.

  \begin{proof}
    The proof of the isomorphism extension theorem depends on
    \mynameref{lem:zorn}.

    ??? The theorem seems to be very close to the theorem
    \ref{thm:lec2_3}. 
  \end{proof}
  
  \label{thm:isomorphismextension}
\end{theorem}

\begin{theorem}[About group homomorphism]
  A group homomorphism is \mynameref{def:injection} iff the kernel is
  trivial \cite{wiki:grouphomomorphism}
  \label{thm:grouphomomorphsim}
\end{theorem}

\subsection{Category theory}

\begin{definition}[Commutative diagram]
  A commutative diagram is a diagram of objects (also known as
  vertices) and morphisms (also known as arrows or edges) such that
  all directed paths in the diagram with the same start and endpoints
  lead to the same result by composition
  \label{def:commutativediagram}

  The following diagram commutes if $f_{AB} = f_{CB} f_{AC}$ or
  $f_{AB}\left(x\right) = f_{CB} \left(f_{AC}\left(x\right)\right)$.
  \begin{tikzpicture}[description/.style={fill=white,inner sep=2pt}]
    \matrix (m) [matrix of math nodes, row sep=3em,
      column sep=2.5em, text height=1.5ex, text depth=0.25ex]
            { A& & B \\
              & C & \\ };
            %\draw[double,double distance=5pt] (m-1-1) – (m-1-3);
            \path[->]
            (m-1-1) edge node[description] {$ f_{AB} $} (m-1-3)
            edge node[description] {$  f_{AC} $} (m-2-2)
            (m-2-2) edge node[description] {$  f_{CB} $} (m-1-3);
  \end{tikzpicture}

\end{definition}

\section{Number theory}

\begin{definition}[Euler's totient function]
  In number theory, Euler's totient function counts the positive
  integers up to a given integer $n$ that are relatively prime to $n$. It
  is written using the Greek letter phi as $\phi\left(n\right)$, and
  may also be called Euler's phi function. It can be defined more formally as
  the number of integers $k$ in the range $1 \le k \le n$ for which the
  greatest common divisor $gcd\left(n, k\right)$ = 1. The integers $k$ of this
  form are sometimes referred to as totatives of $n$.

  The definition was taken from \cite{wiki:eulerfunction}
  \label{def:eulerfuction}
\end{definition}

\begin{example}[Euler's totient function]
  For example \cite{wiki:eulerfunction}, the totatives of $n = 9$ are
  the six numbers 1, 2, 4, 5, 
  7 and 8. They are all relatively prime to 9, but the other three
  numbers in this range, 3, 6, and 9 are not, because
  $gcd\left(9, 3\right)$ =
  $gcd\left(9, 6\right) = 3$ and $gcd\left(9, 9\right) = 9$.
  Therefore, $\phi\left(9\right) = 6$. As another
  example, $\phi\left(1\right) = 1$ since for $n = 1$ the only integer in the range from
  1 to n is 1 itself, and $gcd\left(1, 1\right) = 1$. 
\end{example}

\end{appendices}