We have the following result.
More on Cyclic Groups
Let $G$ be a cyclic group of order $n$, and let $a \in G$ be a generator. Then for any $b = a^k$, the order of $b$ is $\dfrac{n}{d}$ where $d = \gcd(n, k)$.
What's the order of $6$ in $\mathbb{Z}_8$? $$\overline{6} = {\overline{6}, \overline{4}, \overline{2}, \overline{0}} \quad \leadsto \quad \gcd(6, 8) = \gcd(2 \cdot 3,\ 2 \cdot 2 \cdot 2) = 2.$$
Let $G$ be a cyclic group of order $p$, for $p$ a prime. What are all possible orders? $$\gcd(p, *) \in \{1, p\}$$ $\therefore$ any element is either the identity or a generator!
The generators of $\mathbb{Z}_n$ are $r$ s.t. $\gcd(r, n) = 1$.
Let $p$ be a prime; how many generators are there for $\mathbb{Z}_{p^2}$?
Solution
Note that $\gcd(p^2, *) \in {1, p, p^2}$ and so any el't sorts into order $1$ (identity), $p$ (the element $p$ and its multiples) and $p^2$ (everything else). $$\therefore\ (p)(p-1). \qquad \square$$
$p = 3$, $\mathbb{Z}_9 = {\overline{0}, \overline{1}, \dots, \overline{9}}$.
Solution
| element | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| order | 1 | 9 | 9 | 3 | 9 | 9 | 3 | 9 | 9 |
Show that, for $n > 2$, $\mathbb{Z}_n$ has an even number of generators.
Solution
Want to show, for $n > 2$, $$2 \mid \left| { k \in \mathbb{Z} \mid 0 \leq k < n,\ \gcd(k, n) = 1 } \right|.$$ Claim. If $a$ generates, then $-a$ also generates.
Why? $\gcd(a, n) = 1$, then $\gcd(-a, n) = \gcd(n - a, n) = \gcd(n, a) = 1$.
Claim. If $n > 2$, $a \neq -a$.
Why? Suppose so. Then $\operatorname{ord}(a) = 2$, so since $n \neq 2$, $a$ cannot generate. $\square$
Permutation Groups
Let $[n] = {1, \dots, n}$ be a finite set of $n$ el'ts. Define a permutation as $$\sigma : [n] \longrightarrow [n]$$ such that $\sigma$ is one-to-one and onto. The set of such forms a group under composition.
Let $n = 3$. $S_3$ are the permutations of ${1, 2, 3}$. We can write $$1 \mapsto 2, \quad 2 \mapsto 3, \quad 3 \mapsto 1 \qquad \text{as} \qquad (1\ 2\ 3).$$
What's the order of this el't?
Answer:
$$(1\ 2\ 3)(1\ 2\ 3) = (1\ 3\ 2)$$ $$(1\ 2\ 3)(1\ 3\ 2) = (1)(2)(3) \equiv \mathbb{1}$$Thus the order is $3$.
Compute the product of $(1\ 3\ 5)$ and $(3\ 4\ 7)$ in $S_7$.
Solution
Is this group abelian?
In $S_3$, consider $(1\ 2)$ and $(2\ 3)$: $$(2\ 3)(1\ 2) = (1\ 3\ 2)$$ $$(1\ 2)(2\ 3) = (1\ 2\ 3)$$
How do we generalize this argument?
Every permutation in $S_n$ can be represented as a product of disjoint cycles.
Sketch of Proof
We'll start by "tracking each number." $[n] = {1, \dots, n}$, so $\forall, \sigma \in S_n$, write $$X_1 = { \sigma(1), \sigma^2(1), \dots }.$$ $S_n$ is finite, and $[n]$ is finite, so $X_1$ must be. Let $i \in [n] \setminus X_1$. Then $$X_2 = { \sigma(i), \sigma^2(i), \dots }$$ and $X_1 \cap X_2 = \emptyset$. Repeat this process recursively; it must stop in finite steps since $[n]$ is finite. Define the cycle: $$\sigma_i(x) = \begin{cases} \sigma(x) & x \in X_i \ x & x \notin X_i \end{cases}$$ Then $\sigma = \prod \sigma_i$, these are all disjoint. $\square$
Another way to represent permutations is through "building blocks," called transpositions: $$(a_1\ \cdots\ a_n) = (a_1\ a_n) \cdots (a_1\ a_2)$$
If we can represent a permutation w/ an even number of transpositions, it's even; else it's odd.
Consider $A_n = { \sigma \in S_n \mid \sigma \text{ even} }$. Then $A_n \leq S_n$.
What does $A_4$ look like?
$S_4$ has $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ el'ts, so $A_4$ should have $12$. Look for:
- Odd length cycles:
- $(1)(2)(3)(4) = \mathbb{1}$
- $(1\ 2\ 3),\ (1\ 3\ 2)$
- $(1\ 3\ 4),\ (1\ 4\ 3)$
- $(1\ 2\ 4),\ (1\ 4\ 2)$
- $(2\ 3\ 4),\ (2\ 4\ 3)$
- Products of an even # of disjoint transpositions:
- $(1\ 2)(3\ 4)$, $(1\ 3)(2\ 4)$, $(1\ 4)(2\ 3)$
Subgroup lattice:
What do we notice about the orders of groups?