====== - #6 What is a group? ======

In lesson [[01_definitions_and_motivation]], we learned the definitions of ring and field. In the next lesson we'll need one more algebraic concept — //group//. This lesson gives some basic facts about groups.

===== - An introductory example =====

Before giving the definition of group, let us start with an example of a group that will also be useful later in this topic. Let $\mathcal F$ be a field and $a$ a non-zero element of it. Let us consider the field's subset $S = \{ a^k\ |\ k \in \mathbb Z \} = \{\ldots,\ a^{-3}, a^{-2}, a^{-1}, 1, a, a^2, a^3, \ldots \}$, the set of integer powers of $a$, where we define negative powers using the formula $a^{-n} = (a^{-1})^n$, and we define the zeroth power to be the identity element.

<BOOKMARK:subgroup_generated_by_element_of_Zn_star>
For example, if we take $\mathcal F$ to be the residue class field $\mathbb F_7 = \mathbb Z_7$ and $a = 4$, then it turns out that $S = \{ 1,\ 2,\ 4\}$. ++Explanation.|
The inverse of the element $4 \in \mathbb{Z}_7$ is $2$ since $4 \cdot 2 = 8 \equiv 1\ (\operatorname{mod} 7)$. According to the definition of multiplication in $\mathbb{Z}_7$, we have e. g. $4^2 = 4 \cdot 4 = 2$ in $\mathbb{Z}_7$ since $16 \equiv 2\ (\operatorname{mod} 7)$. The set of powers of $a$ in this case is therefore
\begin{align*}
&S = \{\ldots,\ 4^{-4},\ 4^{-3},\ 4^{-2},\ 4^{-1},\ 1,\ 4,\ 4^2,\ 4^3,\ 4^4, \ldots \} =\\
&\qquad\{\ldots,\ 2^4,\ 2^3,\ 2^2,\ 2,\ 1,\ 4,\ 4^2,\ 4^3,\ 4^4, \ldots \} =\\
&\qquad\{\ldots,\ 2,\ 1,\ 4,\ 2,\ 1,\ 4,\ 2,\ 1,\ 4,\ \ldots \}.
\end{align*}
There seems to be a repeating pattern here. Indeed, since $4^3 = 1$ in $\mathbb{Z}_7$, we have in $\mathbb{Z}_7$ the identity $4^{n+3} = 4^n \cdot 4^3 = 4^n$ for all integers $n$. Therefore, the powers repeat with a period $3$ and the set of integer powers of $4$ is the three-element set $\{1, 2, 4\} \subset \mathbb Z_7$.
++

The set $S$ inherits some algebraic structure from the field $\mathcal F$: the set $S$ is closed under multiplication because it can be easily shown that the rule $a^i a^j = a^{i+j}$ holds for all integers $i$ and $j$. However, $S$ is not a field itself since in general it is in general not closed under addition of $\mathcal F$. But we can regard $S$ as an algebraic structure with only one operation: multiplication. This operation has some nice properties: $S$ is closed under taking inverses because $(a^i)^{-1} = a^{-i}$ for all integers $i$, as is easy to see; it contains the identity since $a^0 = 1$ by definition; multiplication is associative and commutative because of the field axioms. Such algebraic structures with only one operation are called //abelian groups//, rigorously defined below.

===== - Definition of group =====

<WRAP def>
A set $S$ together with a binary operation $\cdot$ on it is called a **group** if it satisfies the following properties.
  - The set $S$ is closed under the operation $\cdot$.
  - $\cdot$ is //associative//: $a \cdot (b \cdot c) = (a \cdot b) \cdot c$ for all $a, b, c \in S$.
  - $\cdot$ has an //identity element//, i. e. there exists an element $e \in S$ such that $e \cdot a = a \cdot e = a$ for all $a \in S$.
  - For every $a \in S$ there exists $b \in S$ such that $a \cdot b = b \cdot a = e$; the element $b$ is called the //inverse// of $a$ and denoted by $a^{-1}$.
</WRAP>
<WRAP def>
A group $(S; \cdot)$ is called an **abelian group** if $\cdot$ is //commutative//, i. e. $a \cdot b = b \cdot a$ for all $a, b \in S$.
</WRAP>

===== - More important examples and non-examples of groups =====

  * If $(\mathcal F; +, \cdot)$ is a field and $\mathcal F^*$ denotes the set of its non-zero elements, then $(\mathcal F^*; \cdot)$ is an abelian group, called the **multiplicative group** of $\mathcal F$. The group's identity element $e$ is the multiplicative identity $1$ (which belongs to $\mathcal F^*$ since $0 \neq 1$) and the inverse of an element $a$ in the group is its multiplicative inverse $a^{-1}$ in the field. This is the group we will be most interested in in this topic.++Proof that this is a group |
To verify that $(\mathcal F^*; \cdot)$ is a correctly defined group, we must check that $\mathcal F^*$ is closed under the binary operation $\cdot$, i. e. that $a \cdot b \in \mathcal F^*$ for all $a, b \in \mathcal F^*$. In other words, we have to prove that the product of two non-zero elements is non-zero (or, as algebraists say: a field has no zero divisors). Suppose the contrary. Let $a, b \in \mathcal F^*$ be such that $a \cdot b = 0$. Then on one hand, $a^{-1} \cdot (a \cdot b) = a^{-1} 0 = 0$, but on the other hand, $a^{-1} \cdot (a \cdot b) = (a^{-1} a) b = 1$, so $0 = 1$, which is a contradiction with the definition of field that requires $0 \neq 1$. Therefore $\mathcal F^*$ is indeed closed under multiplication. It is obvious from the definition of field that multiplication satisfies all the axioms of abelian group.++
  * If $(\mathcal F; +, \cdot)$ is a field, then $(\mathcal F; +)$ is a group. In other words, a field is a group if we forget about the multiplication operation of the field and regard addition as the group operation $\cdot$. Indeed, the definition of field guarantees the associativity of addition, the existence of identity element with respect to the $+$ operation (which is $0$, the zero element of the field) and that every element $a \in \mathcal F$ has an additive inverse (which is $-a$, the opposite element of $a$). The group $(\mathcal F; +)$ is called the **additive group** of $\mathcal F$. It is an abelian group.
  * If $(\mathcal F; +, \cdot)$ is a field, then $(\mathcal F; \cdot)$ is //not// a group. This is because the third group axiom fails: $0$ has no multiplicative inverse.
  * Although the concrete groups we will meet in this material will usually be abelian, there are also many important non-abelian groups in mathematics. For example $GL(n, \mathbb R)$, the group of invertible $n \times n$ matrices of real numbers, where the group operation is matrix multiplication, is not abelian for $n > 1$. Another example is $SO(3)$, the group of rotations about the origin in 3-dimensional space, where the group operation is the application of one rotation after another.

===== - Some notes on notation =====

In the definition of group we have used **multiplicative notation**, where the group operation is denoted by $\cdot$ or juxtaposition and called multiplication, and the inverse of an element $a^{-1}$. When talking about additive groups of fields, such notation can create confusion, since the operation of the group is then not the field's multiplication and the inverse element in the group is not what is denoted by $a^{-1}$ in the field. Therefore another common notation in literature is **additive notation**, where the group operation is denoted by $+$ and called addition and inverse element is denoted by $-a$. Sometimes also other notations are used in literature. In this material we will in general stick to the multiplicative notation.

In the multiplicative notation, the product $a \cdot \ldots \cdot a$ where the element $a$ occurs $n$ times is denoted by $a^n$ and called the **$n$th power of $a$**. Negative powers of $a$ are defined as powers of the inverse of $a$ (e. g. $a^{-3} = (a^{-1})^3$), and the zeroth power is defined to be the identity element (i. e. $a^0 := e$).

===== - Subgroups =====

A group can contain a smaller group as a subset. Such a subset is called a //subgroup// of the larger group. For example, consider $\mathbb F_{7}^*$, the multiplicative group of the field $\mathbb F_{7} = \mathbb Z_7$. The set $\{-1, 1\} = \{10, 1\} \subset \mathbb F_{7}^*$ is a group itself with respect to the multiplication in $\mathbb F_{7}^*$ since it is closed under multiplication, every element has an inverse in $S$ since both elements are their own inverses and multiplication of elements of $S$ is associative because multiplication is associative on $\mathbb F_{7}^*$. Another example of subgroup of $\mathbb F_{7}^*$ is the subset $\{1, 2, 4\}$ that we considered in the [[#subgroup_generated_by_element_of_Zn_star | introductory example]].

<WRAP def>
Let $\mathcal G$ be a group. A subset $\mathcal H \subseteq \mathcal G$ is called a **subgroup** of $\mathcal G$ if $\mathcal H$ is a group itself with respect to the group operation of $\mathcal G$.
</WRAP>

**More examples and non-examples of subgroups.**
  * The multiplicative group of real numbers $(\mathbb R^*; \cdot)$ has the set of non-zero rational numbers $\mathbb Q^*$ as a subgroup. Indeed, $(\mathbb Q^*; \cdot)$ is a group since $\cdot$ is a binary operation on $\mathbb Q$ since the product of two rational numbers is a rational number; associativity and existence of identity element are obvious; for every non-zero rational number, the set $\mathbb Q^*$ also contains its inverse.
  * The set of positive integers is also a subset of $\mathbb R^*$ but //not// a subgroup of the group $(\mathbb R^*; \cdot)$ since it is not closed under taking inverses.
  * The subset $\{1, 2, 5\} \subset \mathbb F_7^*$ is //not// a subgroup of $\mathbb F_7^*$ since it is not closed under multiplication: $2 \cdot 5 = 3 \not\in \{1, 2, 5\}$.

A criterion for checking whether a subset is a subgroup is as follows.

<WRAP def>
**Lemma.** Let $(G; \cdot)$ be a group. A subset $H \subset G$ is a subgroup of $G$ if and only if $H$ is closed under multiplication and taking inverses and contains the identity element of $G$.
</WRAP>

===== - Subgroup generated by an element =====

An example of subgroup is the subgroup generated by an element, defined as follows.

<WRAP def>
Let $(G; \cdot)$ be a group and $a \in G$. The set $\langle a \rangle := \{ a^k\ |\ k \in \mathbb Z \} = \{\ldots,\ a^{-3}, a^{-2}, a^{-1}, e, a, a^2, a^3, \ldots \}$, i. e. the set of all integer powers of $a$, is called the **subgroup generated by $a$**.
</WRAP>

The subgroup generated by an element is indeed always a subgroup, as follows from the simple lemma below.

**Lemma.** If $G$ is a group and $a \in G$, then $a^i a^j = a^{i+j}$ and $(a^i)^{-1} = a^{-i}$ for all integers $i$ and $j$.
++++Proof.|

To prove this statement we have to use the definitions of integer powers: $a^i = \underbrace{a \cdot a \cdot \ldots \cdot a}_{i}$ for $i > 0$, $a^0 = e$, $a^{i} = (a^{-1})^{-i}$ for $i < 0$.

First note that the second claim $(a^k)^{-1} = a^{-k}$ is a simple consequence of the first claim $a^i a^j = a^{i+j}$. Indeed, let $k$ be an integer and $a$ an element of a group. Taking $i=-k$ and $j=k$ in the formula  $a^i a^j = a^{i+j}$ we get $a^{-k}a^k = a^{-k+k} = a^0 = e$ and taking $i=k$ and $j=-k$ we get $a^k a^{-k} = a^{k+(-k)} = a^0 = e$, so $a^{-k}a^k = a^k a^{-k} = e$, which by the definition of inverse element means that $a^{-k} = (a^k)^{-1}$. So it remains to prove $a^i a^j = a^{i+j}$.

It is intutitively easy to see why $a^i a^j = a^{i+j}$ holds: $a^i a^j$ is a product of $i+j$ factors whose factors are $a$ or $a^{-1}$; the definition of inverse and identity allow to annihilate any pairs of consecutive $a$ and $a^{-1}$ since $aa^{-1} = a^{-1}a = e$ and removing a factor $e$ from a product does not change the value of the product; after this annihilation we get that $a^i a^j$ is just a product whose factors are $a$'s or the inverses of $a$, i. e. $a^i a^j$ is an integer power of $a$; it is also easy to convince oneself that the exponent is $i+j$. Writing down the details of this easy proof is surprisingly tedious, but is carried out below.

Let us consider five cases: 1) $i = 0$ or $j = 0$, 2) $i > 0, j > 0$, 3) $i < 0, j < 0$, 4) $i > 0, j < 0$, 5) $i < 0, j > 0$.

1) If $i = 0$, then $a^i a^j = e a^j = a^j = a^{i+j}$. Analogously $a^i a^j = a^{i+j}$ if $j = 0$.

2) If $i, j > 0$ then $a^i a^j = (\underbrace{a \cdot a \cdot \ldots \cdot a}_{i}) \cdot (\underbrace{a \cdot a \cdot \ldots \cdot a}_{j}) = \underbrace{a \cdot a \cdot \ldots \cdot a}_{i+j} = a^{i+j}$. The first equality is from the definition of power of an element, and associativity allowed us to ignore the braces in the second equality.

3) If $i, j < 0$ then $a^i a^j = (a^{-1})^{-i} (a^{-1})^{-j} = (\underbrace{a^{-1} \cdot \ldots \cdot a^{-1}}_{-i}) \cdot (\underbrace{a^{-1} \cdot \ldots \cdot a^{-1}}_{-j}) = (a^{-1})^{-i-j} = {a}^{i+j}$. 

4) For the case $i > 0, j < 0$, let us consider three subcases: 4a) $-j = i$, 4b) $-j < i$, 4c) $-j > i$.

4a) If $-j = i$, then $a^i a^j = a^i (a^{-1})^i$ by the definition of negative powers ($a^{k} = (a^{-1})^{-k}$ for $k < 0$). It is easy to see that $a^i (a^{-1})^i = e$ since pairs of  consecutive $a$ and $a^{-1}$ can be repeatedly “annihilated”: 
$$\underbrace{a \cdot \ldots \cdot a}_{i} \cdot \underbrace{a^{-1} \cdot \ldots \cdot a^{-1}}_{i} = \underbrace{a \cdot \ldots \cdot a}_{i-1} \cdot e \cdot \underbrace{a^{-1} \cdot \ldots \cdot a^{-1}}_{i-1} = \underbrace{a \cdot \ldots \cdot a}_{i-1} \cdot \underbrace{a^{-1} \cdot \ldots \cdot a^{-1}}_{i-1} = \ldots = e.$$
Here we used the identities $aa^{-1} = e$ and $a e = e$ and also associativity which allowed us to omit braces. Therefore $a^i a^j = e = a^{0} = a^{i+j}$ indeed.

4b) In this case we have $-j > 0$ and $i+j > 0$, so we have already proven in case 2) that $a^i = a^{i+j} a^{-j}$; therefore $a^i a^j = (a^{i+j} a^{-j}) a^j = (a^{i+j} a^{-j}) (a^{-1})^{-j} = a^{i+j} (a^{-j} (a^{-1})^{-j}) = a^{i+j} e = a^{i+j}$. At the second equality we used the definition of negative powers; at the third one, associativity; at the fourth one the property $a^k (a^{-1})^k = e$ for $k > 0$ which was proven in subcase 4a).

4c) Analogous to 4b) but use $a^j = a^{-i} a^{i+j}$.

5) Analogous to 4).
++++

Indeed, from the lemma it follows that the subgroup generated by an element is closed under multiplication and taking inverses; it also contains the identity since $a^0 = e$ by definition, therefore it is a subgroup. The subgroup generated by $a$ is the smallest subgroup which contains the element $a$, since any subgroup containing $a$ must also contain all its integer powers to be closed under multiplication and taking inverses.

**Examples.**
  * In the group $(\mathbb R^*; \cdot)$, the subgroup generated by the element $2 \in \mathbb R^*$ is $\langle 2 \rangle = \{\ldots,\ \frac18,\ \frac14,\ \frac12,\ 1,\ 2,\ 4,\ 8,\ 16,\ \ldots \}$.
  * Consider the multiplicative group of the field $\mathbb Z_7$, i. e. the group $(\mathbb Z_7^*; \cdot)$, where $\mathbb Z_7^* = \{1, 2, 3, 4, 5, 6\}$ is the set of invertible remainders modulo $7$. Then the subgroup generated by $4 \in \mathbb Z_7^*$ is $\langle 4 \rangle = \{1, 4, 2\} \subset \mathbb Z_7^*$ (this is because the powers start to repeat with period $3$ because $4^3 = 1$, as [[#subgroup_generated_by_element_of_Zn_star | explained at the introductory example]]).

<WRAP task>
What is the subgroup generated by the element $5$ in the multiplicative group of the field $\mathbb Z_{13}$? ++ Answer. | $\langle 5 \rangle = \{ 1,\, 5,\, 8,\, 12\}$ ++
</WRAP>

===== - Order =====
  
As we shall see, in any finite group (i. e. a group that contains a finite number of elements) the situation is similar to the last example about  $\mathbb Z_7^*$: the powers of an element start to repeat because some positive power of the element is the identity.

<WRAP def>
**Lemma.** Let $G$ be a finite group and $a \in G$. Then there exists a positive integer $n$ such that $a^n = e$.
</WRAP>
++++Proof.|The set $\{ a^k\ |\ k \in \mathbb Z \}$ of all powers of $a$ must be finite since it is a subset of the finite set $G$. Therefore, there must exist two powers of $a$ that are equal to each other. Let $i$ and $j$ be two integers with $i < j$ such that $a^i = a^j$. Let $n := j-i$. Then $a^n = a^{j-i} = (a^i)^{-1} a^j = (a^i)^{-1} a^i = e$.++++

If $a^n = e$, then the powers of an element of a finite group repeat with period $n$ since $a^{n+i} = a^n a^i = e a^i = a^i$ for all integers $i$. Therefore we can define the //order// of an element as follows. 

<WRAP def>
Let $(G; \cdot)$ be a finite group. The **order of an element $a \in G$** is the smallest positive integer $n$ such that $a^n = e$ where $e$ denotes the identity element. The order of $a$ is denoted by $\operatorname{ord} a$.
</WRAP>

For example, in $\mathbb{Z}_7^*$ the order of the element $4$ is $3$ because $4^3 = 1$ but $4^1 = 4 \neq 1$ and $4^2 = 2 \neq 1$.

Another use of the word //order// is the order of a group, defined below. The use of the same word //order// for two different things (order of an element and order of a group) might be a little confusing, but the lemma below shows that these concepts are related.

<WRAP def>
Let $(G; \cdot)$ be a finite group. The **order of the group $G$** is the number of elements in $G$.
</WRAP>

<WRAP def><BOOKMARK:order_of_element_is_size_of_subgroup>
**Lemma.** Let $(G; \cdot)$ be a finite group and $a \in G$. The order of the element $a$ is the order of the subgroup generated by it.
</WRAP>
++++Proof.|
Let $n$ be the order of $a$. Since the powers of $a$ repeat with period $n$, the subgroup generated by $a$ is the set $\{e,\ a,\ ,a^2,\ a^3,\ \ldots,\ a^{n-1}\}$. Obviously the order of the subgroup generated by $a$ is not greater than $n$, but it would be less than $n$ if there existed two equal powers $a^i = a^j$ such that $0 \leq i < j < n$. Suppose that this is the case. Then we have $a^{j-i} = e$, which gives a contradiction since $n$ was supposed to be the smallest positive power of $a$ equal to the identity, but $j-i < n$.
++++

For example, we have found that in $\mathbb{Z}_7^*$ the order of the element $4$ is $3$ and the subgroup generated by the element $4$ is $\{1, 2, 4\}$, which indeed contains $3$ elements.

===== - Lagrange's Theorem =====

Let us note a useful property of orders of subgroups.

<WRAP def>
**Theorem (Lagrange).** Let $(G;\ \cdot)$ be a finite group and $H \subseteq G$ a subgroup. Then the order of $H$ divides the order of $G$.
</WRAP>

++++Proof.|
For any $a\in G$ define the set $aH$ as follows:
\[
aH=\{a\cdot h\,|\, h\in H\}\enspace.
\]
The set $aH$ is called a //(left) coset// of $H$ (corresponding to the element $a\in G$).

For example, if we take $G = (\mathbb Z_7^*; \cdot)$, $H = \{1, 2, 4\}$ and $a=6$, then the coset of $H$ corresponding to the element $a$ is $6H = \{6 \cdot 1,\, 6 \cdot 2,\, 6 \cdot 4\} = \{6, 5, 3\}$.

The idea of the proof is as follows. We will show that the following two facts hold:
  - The cosets of $H$ partition the set $G$: for every two elements $a, b \in G$, the sets $aH$ and $bH$ are either disjoint or equal, and the union of all the sets $aH$, where $a \in G$, is $G$.
  - Each coset contains the same number of elements as $H$.
From these two facts, the claim of the theorem follows immediately: namely, the order of $G$ is equal to the order of $H$ times the number of different cosets of $H$.

For example, for $G = \mathbb Z_7^*$, the cosets of $H = \{1, 2, 4\}$ are
  * $1H = \{1, 2, 4\}$,
  * $2H = \{2, 4, 1\}$,
  * $3H = \{3, 6, 5\}$,
  * $4H = \{4, 1, 2\}$,
  * $5H = \{5, 3, 6\}$,
  * $6H = \{6, 5, 3\}$.
We see that $H$ has two different cosets: $\{1, 2, 4\}$ and $\{3, 5, 6\}$. These cosets indeed partition the set $G = \{1, 2, 3, 4, 5, 6\}$, i. e. every element of $G$ belongs to exactly one of these two cosets. The cosets are also indeed both of the same size as $H$: both contain three elements. So $($ the order of $H ) \cdot ($ number of cosets $) = 3 \cdot 2 = 6 = ($ the order of $G )$.

Now we will show that the two facts hold in the general case.

First note that the following claims are trivial to prove.
  * If $h\in H$ then $hH=H$. In particular, $eH=H$.
  * If $a'\in aH$ and $h'\in H$, then $a'h'\in aH$.
  * If $a_1,a_2\in aH$ then there exists $h\in H$ such that $a_1h=a_2$.
    * Indeed, if $a_1=ah_1$ and $a_2=ah_2$ for some $h_1,h_2\in H$, then $a_2=a_1\cdot (h_1^{-1}h_2)$.

Now let's prove the first fact. Obviously, each element $a\in G$ is an element of the coset $aH$. Hence the cosets of $H$ cover the group $G$. We will show that two different cosets do not intersect.

Let $aH$ and $bH$ be cosets of $H$ and assume there exists some $g\in G$, such that $g\in aH\cap bH$. Let $h_a,h_b\in H$ be such that $g=ah_a=bh_b$. We will show that then $aH\subseteq bH$, a symmetric argument would then show $bH\subseteq aH$ and thus $aH=bH$. Let $a'$ be an arbitrary element of $aH$. Let $h'\in H$ be such that $gh'=a'$; such $h'$ exists according to the last claim above. Then $a'=gh'=b(h_bh')$, showing that $a'$ is an element of $bH$.

Thus, the first fact has been proven.

It remains to prove the second fact: that if $aH$ and $bH$ are two different cosets then they have the same cardinality. We do this by exhibiting a one-to-one mapping $\varphi$ from $aH$ onto $bH$. The mapping is defined by $\varphi(g)=ba^{-1}g$ for all $g\in aH$. We have that:
  * $\varphi$ maps $aH$ to $bH$. Indeed, if $g=ah\in aH$, then $\varphi(g)=ba^{-1}g=ba^{-1}ah=bh\in bH$.
  * $\varphi$ is onto. Indeed, if $g'=bh'\in bH$ then $\varphi(ah')=g'$.
  * $\varphi$ is one-to-one. Indeed, if $\varphi(g_1)=\varphi(g_2)$ then $ba^{-1}g_1=ba^{-1}g_2$. Multiplying the sides of this equality from the left with $ab^{-1}$ gives us $g_1=g_2$.

Thus, the second fact has been proven and the whole theorem as well.
++++

<WRAP def>
**Corollary.** The order of any element of a finite group divides the order of the group.
</WRAP>

For example, we have found that the order of the element $4$ in $\mathbb{Z}_7^*$ is $3$; this indeed divides the order of the group $\mathbb{Z}_7^*$, which is $6$.

<WRAP def>
**Corollary (Generalized Fermat's Little Theorem).** Let $G$ be a finite group of order $n$. Then $a^{n} = e$ for all $a \in G$.
</WRAP>
++++ Proof.|
Let $a \in G$ be an arbitrary element. Let $k$ be the order of $a$ (the order of $a$ exists since $G$ is finite). By the Theorem of Lagrange, $k$ divides $n$, so $dk = n$ for some integer $d$. Since $a^k = e$, we also have $a^n = a^{dk} = a^{k + \ldots + k} = a^k \cdot \ldots \cdot a^k = e \cdot \ldots \cdot e = e$.
++++

If we take $G$ to be the multiplicative group of the field $\mathbb Z_p$ then the last corollary above gives us Fermat's Little Theorem: if $p$ is a prime then $a^{p-1} \equiv 1\ (\operatorname{mod} p)$.

===== - Group homomorphisms and isomorphisms =====

Analogously to the case of rings ([[04_isomorphisms]]), two groups are called isomorphic if the elements of one group can be “relabeled” so that we obtain the other group. Only instead of two operations (ring addition and multiplication) we now have only one (group multiplication). Also analogously to the homomorphism of rings, one defines homomorphism of groups — a map preserving the group operation, but not necessarily one-to-one or onto.

<WRAP def>
Let $\mathcal F$ and $\mathcal G$ be two groups.\\
\\
A function $\kappa : \mathcal F \to \mathcal G$ is called a **homomorphism** if it satisfies $\kappa(a \cdot b) = \kappa(a) \cdot \kappa(b)$ for all $a, b \in \mathcal F$.\\
\\
A homomorphism $\kappa : \mathcal F \to \mathcal G$ is called an **isomorphism** if it is one-to-one and onto. Two groups are called **isomorphic** if there exists an isomorphism between them.\\
\\
An isomorphism $\kappa : \mathcal F \to \mathcal F$ is called an **automorphism** of $\mathcal F$.
</WRAP>

With a short proof one can show that a group homomorphism always satisfies $\kappa(e) = e$ and $\kappa(a^{-1}) = \kappa(a)^{-1}$.

===== - Exponentiation and discrete logarithm =====

Although there exist many different groups that may be quite difficult to describe((It is interesting to note that even the classification of all finite //simple// groups, a subclass of finite groups, is one of the greatest achievements of algebra in the 20th century, the proof consisting of thousands of pages in hundreds of journal articles. Mathematicians haven't yet found a general classification of all finite groups. (However, for finite //abelian// groups, a simple classification actually does exist.) )), it is not hard to see that in any group the subgroup generated by an element has a very simple and familiar structure: it can be identified with the additive group $\mathbb Z_n$ for some $n$, as stated by the theorem below.

<WRAP def>
**Theorem.** Let $a$ be an element of order $n$ of a finite group. Then the map $\operatorname{exp}_a : \mathbb Z_n \to \langle a \rangle$ with $\operatorname{exp}_a(i) = a^i$ is a group isomorphism from the additive group of $\mathbb Z_n$ to the subgroup generated by $a$.
</WRAP>
++++Proof.|
First note that one could have a question what $a^i$ means when $i$ is not an element of $\mathbb Z$ but an element of $\mathbb Z_n$. If we regard $\mathbb Z_n$ as the set $\{0, 1, \ldots, n-1\}$ of all possible remainders modulo $n$, then of course there is no question. But one sometimes also talks e. g. about the element $5$ in $\mathbb Z_3$ and says things like “$5 = 2$ in $\mathbb Z_3$”. Then we have the question how $a^i$ should be defined if $i = 5 \in \mathbb Z_3$: is it $a \cdot a \cdot a \cdot a \cdot a$ or $a \cdot a$? Fortunately, such concerns turn out to be unfounded: as we saw above, the powers of $a$ are periodic with period $n = \operatorname{ord} a$, so all natural ways of interpreting $a^i$ in the statement of the theorem give the same result (e. g., if the order of $a$ is $n=3$, then $a^5 = a \cdot a \cdot a \cdot a \cdot a = a \cdot a = a^2$).

The map $\operatorname{exp}_a$ is one-to-one and onto, as we saw in the proof of [[#order_of_element_is_size_of_subgroup | the Lemma saying that the order of an element equals the size of the subgroup it generates]]. The map $\operatorname{exp}_a$ is a homomorphism since $a^{i+j} = a^i a^j$, as we also saw above. Therefore it is indeed an isomorphism.
++++

The inverse map of the exponentiation map $\operatorname{exp}_a$ is the **discrete logarithm** $\operatorname{log}_a : \langle a \rangle \to \mathbb Z_n$. In other words, if $b \in \langle a \rangle$ is an element of the subgroup generated by $a$ then its discrete logarithm $\log_a(b)$ is the number $i \in \mathbb Z_n$ such that $b = a^i$. In some groups, the discrete logarithm turns out to be much harder to compute than the exponential of an element. This asymmetry has found use in several cryptographic algorithms.


<WRAP nl>
[[07_multiplicative_group]]
</WRAP>
---------------------------------------------------------------------------------------------------------------------------------------