Abstract Algebra/Group Theory/Cyclic groups

From Wikibooks, open books for an open world
Jump to: navigation, search

Definition[edit]

  • A cyclic group generated by g is


  • \langle g \rangle = \lbrace g ^{n} \; | \;  n \in \mathbb{Z} \rbrace


  • where  g^{n} = 
\begin{cases} 
  \underbrace{g \ast g \cdots \ast g}_{n} ,  & n \in \mathbb{Z}, n \ge 0\\
  \underbrace{g^{-1} \ast g^{-1} \cdots \ast g^{-1}}_{-n}, & n \in \mathbb{Z}, n < 0
\end{cases}


  • Induction shows: g^{m + n} = g^{m}  \ast g^{n} \text{ and } g^{mn} = [g^{m}]^{n}

a Cyclic Group of Order n is Isomorphic to the Integers Moduluo n with Addition[edit]

Theorem[edit]

Let Cm be a cyclic group of order m generated by g with \ast

Let  (\mathbb{Z} / m, +) be the group of integers modulo m with addition


Cm is isomorphic to  (\mathbb{Z} / m, +)

Lemma[edit]

Let n be the minimal positive integer such that gn = e

g^{i} = g^{j} \leftrightarrow i = j~\text{mod}~n
Proof of Lemma
Let i < j. Let i - j = sn + r where 0 ≤ r < n and s,r,n are all integers.
1. g^{i} = g^{j} \;

2.  e = g^{i - j} = g^{sn + r} = [g^{n}]^{s} \ast g^{r} = [e]^{s} \ast g^{r} = g^{r} as i - j = sn + r, and gn = e
3.  g^{r} = e

4.  r = 0 as n is the minimal positive integer such that gn = e
and 0 ≤ r < n

5.  i - j = sn 0. and 7.
6.  i = j~\text{mod}~n

Proof[edit]

0. Define   \begin{align}
 f\colon C_m &\to \mathbb{Z}/m \\
 g^{i} &\mapsto i ~\text{mod}~m
\end{align}


Lemma shows f is well defined (only has one output for each input).


f is homomorphism:
f(g^{i}) + f(g^{j}) = i + j ~\text{mod}~m = f(g^{i +j}) = f(g^{i} \ast g^{j})


f is injective by lemma


f is surjective as both \mathbb{Z}/m and C_{m} has m elements and m is injective

Cyclic groups[edit]

In the previous section about subgroups we saw that if G is a group with g\in G, then the set of powers of g, \langle g \rangle = \{g^n\mid n\in\mathbb{Z}\} constituted a subgroup of G, called the cyclic subgroup generated by g. In this, section, we will generalize this concept, and in the process, obtain an important family of groups which is very rich in structure.

Definition 1: Let G be a group with an element g\in G such that \langle g \rangle = G. Then G is called a cyclic group, and g is called a generator of G. Alternatively, g is said to generate G. If there exists an integer n such that g^n=e, and n is the smallest positive such integer, G is denoted C_n, the cyclic group of order n. If no such integer exists, G is denoted C_\infty, the infinite cyclic group.


The infinite cyclic group can also be denoted F_{\{g\}}, the free group with one generator. This is foreshadowing for a future section and can be ignored for now.


Theorem 2: Any cyclic group is abelian.

Proof: Let G be a cyclic group with generator g. Then if h,k\in G, then h=g^n and k=g^m for some n,m\in \mathbb{Z}. To show commutativity, observe that hk=g^ng^m=g^{n+m}=g^{m+n}=g^mg^n=kh and we are done.


Theorem 3: Any subgroup of a cyclic group is cyclic.

Proof: Let G be a cyclic group with generator g, and let H\leq G. Since G=\langle g \rangle, in paticular every element of H equals g^n for some n\in\mathbb{Z}. We claim that if a the lowest positive integer such that g^a\in H, then H=\langle g^a \rangle. To see this, let g^n\in H. Then n=qa+r and 0\leq r < a for unique q,r\in \mathbb{Z}. Since H is a subgroup and g^a\in H, we must have g^n (g^a)^{-q}=g^{qa+r}g^{-qa}=g^r\in H. Now, assume that r>0. Then g^r\in H contradicts our assumption that a is the least positive integer such that g^a\in H. Therefore, r=0. Consequently, g^n\in H only if n=qa, and H=\langle g^a \rangle and is cyclic, as was to be shown.

As the alert reader will have noticed, the preceeding proof invoked the notion of division with remainder which should be familiar from number theory. Our treatment of cyclic groups will have close ties with notions from number theory. This is no coincidence, as the next few statements will show. Indeed, an alternative title for this section could have been "Modular arithmetic and integer ideals". The notion of an ideal may not yet be familiar to the reader, who is asked to wait patiently until the chapter about rings.


Theorem 4: Let \mathbb{Z}_n=\{0,1,2,...,n-1\} with addition defined modulo n. That is a+b\equiv r \,\mathrm{mod}\,n, where a+b=qn+r. We denote this operation by a+_nb=r. Then (\mathbb{Z}_n,+_n) is a cyclic group.

Proof: We must first show that (\mathbb{Z}_n,+_n) is a group, then find a generator. We verify the group axioms. Associativity is inherited from the integers. The element 0\in Z_n is an identity element with respect to +_n. An inverse of a\in Z_n is an element b such that a +_n b=0. Thus b+a|n. Then, b\equiv n-a \equiv -a \,\mathrm{mod}\,n, and so b=n-a=-a, and (\mathbb{Z}_n,+_n) is a group. Now, since a=a\cdot 1 = \underbrace{1+...+1}_{a\,\mathrm{terms}}, 1 generates \mathbb{Z}_n and so (\mathbb{Z}_n,+_n) is cyclic.

Unless we explicitly state otherwise, by \mathbb{Z}_n we will always refer to the cyclic group (\mathbb{Z}_n,+_n). Since the argument for the generator of \mathbb{Z}_n can be made valid for any integer a, this shows that also \mathbb{Z} is cyclic with the generator 1.


Theorem 5: An element a\in\mathbb{Z}_n is a generator if and only if \gcd(a,n)=1.

Proof: We will need the following theorem from number theory: If m,n are integers, then there exists integers r,s such that rm+sn=1, if and only if \gcd(m,n)=1. We will not prove this here. A proof can be found in the number theory section.

For the right implication, assume that \langle a \rangle = \mathbb{Z}_n. Then for all b\in \mathbb{Z}_n, b\equiv pa \,\mathrm{mod}\, n for some integer p. In paticular, there exists an integer s such that sa\equiv 1 \,\mathrm{mod}\,n. This implies that there exists another integer r such that sa-rn=1. By the above-mentioned theorem from number theory, we then have \gcd(a,n)=1. For the left implication, assume \gcd(a,n)=1. Then there exists integers s,r such that sa-rn=1 \,\Rightarrow\, sa\equiv 1 \,\mathrm{mod}\,n, implying that sa=1 in \mathbb{Z}_n. Since 1 generates \mathbb{Z}_n, it must be true that a is also a generator, proving the theorem.


We can generalize Theorem 5 a bit by looking at the orders of the elements in cyclic groups.


Theorem 6: Let H=\langle g \rangle \leq \mathbb{Z}_n. Then, |H|=|a|=\frac{n}{\gcd(a,n)}.

Proof: Recall that the order of a\in \mathbb{Z}_n is defined as the lowest positive integer r such that ra=0 in \mathbb{Z}_n. Since \langle g \rangle is cyclic, there exists an integer s such that ra=sn is minimal and positive. This is the definition of the least common multiple; \mathrm{lcm}(a,n)=ra=|a|a. Recall from number theory that \mathrm{lcm}(a,n)\cdot \gcd(a,n)=an. Thus, |a|=\frac{\mathrm{lcm}(a,n)}{a}=\frac{an}{a\cdot \gcd(a,n)}=\frac{n}{\gcd(a,n)}, as was to be proven.


Theorem 7: Every subgroup of \mathbb{Z} is of the form n\mathbb{Z}=\{na\mid a\in \mathbb{Z}\}.

Proof: The fact that any subgroup of \mathbb{Z} is cyclic follows from Theorem 3. Therefore, let n generate H\leq G. Then we see immediately that H=n\mathbb{Z}.


Theorem 8: Let a,b\in\mathbb{Z} be fixed, and let H=\{ra+sb|r,s\in \mathbb{Z}\}. Then H is a subgroup of \mathbb{Z} generated by \gcd(a,b).

Proof: We msut first show that H is a subgroup. This is immediate since (ra+sb)-(r^\prime a + s^\prime b) = (r-r^\prime)a+(s-s^\prime)b\in H. From the proof of Theorem 3, we see that any subgroup of \mathbb{Z} is generated by its lowest positive element. It is a theorem of number theory that the lowest positive integer d such that d=ra+sb for fixed integers a,b and r,s\in\mathbb{Z} equals the greatest common divisor of a and b or \gcd(a,b). Thus \gcd(a,b) generates H.


Theorem 9: Let n\mathbb{Z} and m\mathbb{Z} be subgroups of \mathbb{Z}. Then n\mathbb{Z}\cap m\mathbb{Z} is the subgroup generated by \mathrm{lcm}(n,m).

Proof: The fact that n\mathbb{Z}\cap m\mathbb{Z} is a subgroup is obvious since n\mathbb{Z} and m\mathbb{Z} are subgroups. To find a generator of n\mathbb{Z}\cap m\mathbb{Z}, we must find its lowest positive element. That is, the lowest positive integer p such that p is both a multiple of n and of m. This is the definition of the least common multiple of n and m, or \mathrm{lcm}(n,m), and the result follows.


It should be obvious by now that C_n and \mathbb{Z}_n, and C_\infty and \mathbb{Z} are the same groups. This will be made precise in a later section but can be visualized by denoting any generator of C_n or C_\infty by 1.

We will have more to say about cyclic groups later, when we have more tools at our disposal.