********************************************************************************
Group Theory
********************************************************************************

Some facts about group theory especially cyclic groups are helpful to give a
theoretic foundation for modulo arithmetic.




Subgroups
================================================================================

Definition:
    A subgroup of a group is a subset of the group which is  a group under the
    group operation restriceted to the subgroup.

E.g. the even integers :math:`2\mathbb{Z} = \{ \ldots,-2, 0, 2, 4, \ldots\}` is
a subgroup of the integers under addition.

Some facts:

- A subgrroup contains the neutral element.

- A subgroup is closed under the group operation and the inverse operation.



The Integers mod n
================================================================================


Definition:
    Two integers :math:`a` and :math:`b` are equivalent mod :math:`n` if
    :math:`n` divides :math:`a - b`. We denote the equivalence classes by
    :math:`\mathbb{Z}_n`.

E.g. the integers mod 3 have 3 equivalence classes:

    [0] := { ..., -6, -3, 0, 3, 6, ... }

    [1] := { ..., -5, -2, 1, 4, 7, ... }

    [2] := { ..., -4, -1, 2, 5, 8, ... }


The set of equivalence classes form a group with the natural embedding
:math:`[n] \mapsto n` and the group operation :math:`[a] + [b] := [a + b\; mod\;
n]`. Furthermore we can define a multiplication :math:`[ab] := [ab \; mod \;
n]`.


Cyclic Subgroups
================================================================================


Definition:
    Let :math:`G` be a group and :math:`a` be an element of the group. Then we
    define
    :math:`\langle a \rangle := \{a^n: n \in \mathbb{Z}\}`
    where :math:`a^0 = e`  with the neutral element :math:`e`, :math:`a^{n+1}
    = a a^n` and :math:`a^{-n} = (a^{n})^{-1}`.


Theorem:
    :math:`\langle a \rangle` is a subgroup of :math:`G`. It is the smallest
    subgroup of :math:`G` containing the element :math:`a`.


Definition:
    :math:`\langle a \rangle` is the cyclic subgroup of :math:`G` generated by
    :math:`a`. If :math:`G = \langle a \rangle` then :math:`G` is a cyclic
    group.

Definition:
    We call the smallest integer :math:`n` such that :math:`a^n = e` the order
    of the group :math:`\langle a \rangle`. The order of :math:`\langle a
    \rangle` is infinite, if no such number exists.


Theorem:
    Every cyclic group is abelian.

Theorem:
    Every subgroup of a cyclic group is cyclic.

The group of integers is cyclic because :math:`\mathbb{Z} = \langle 1 \rangle`.