MATH 415 Lecture 4

« previous | Thursday, September 5, 2013 | next »

Subgroups

$H$ is a subgroup of $G$ (denoted $H\le G$) if:

1. $H$ is closed with respect to $*$
2. $e\in H$
3. $a^{-1}\in H$ for all $a\in H$

We say $H$ is a proper subgroup of $G$ (denoted $H<G$) if $H\ne G$.

Cyclic Subgroups

We call $⟨a⟩$ a cyclic subgroup of a group $⟨G,*⟩$ generated by $a$, where $a$ is the generator.

We call a group $⟨G,*⟩$ cyclic if there is an element $a\in G$ such that $G=⟨a⟩$.

If we take an arbitrary group $⟨G,\cdot ⟩$ and an element $a\in G$,

We can compute a subset $H$ containing identity element $a^0$, $a$, $a*a=a^2$, $a*a*a=a^3$, and so on up to $a^n$. Then invert all of these to find $a^{-n}$:

$H=\{a^n\mid n\in \mathbb{\mathbb{Z}}\}$

This is a subgroup generated by $a$, with notation $H=⟨a⟩$.

Theorem. $H=⟨a⟩$ is the smallest subgroup of $G$ containing $a$.

Examples on Integers

It's worth noting that $\mathbb{\mathbb{Z}}=⟨1⟩=⟨-1⟩$.

All subgroups of $⟨\mathbb{\mathbb{Z}},+⟩$ are of the form $n\mathbb{\mathbb{Z}}$. When $n\ne \pm 1$, then $n\mathbb{\mathbb{Z}}<\mathbb{\mathbb{Z}}$.

Consider $⟨{\mathbb{\mathbb{Z}}}_{12},+⟩$:

$\{0,1,2,3,4,5,6,7,8,9,10,11\}$, with $0$ as identity.

Consider subgroup $⟨3⟩=H=\{0,3,6,9\}$, a subgroup of ${\mathbb{\mathbb{Z}}}_{12}$

We call $⟨3⟩$ a subgroup generated by 3.

Examples on Complex Numbers

Recall the Roots of Unity: $U_n$ is a cyclic subgroup generated by $\zeta$.

Theorem 6.1. Every cyclic group is Abelian.

Proof. For

$g,h\in G=⟨a⟩$

, we have

$g=a^n$

and

$h=a^m$

.

$a^m{a}^n=a^n{a}^n=a^{m+n}$

and is thus commutative.

quod erat demonstrandum

Division Algorithm for Integers

For all $m\in {\mathbb{\mathbb{Z}}}^{+}$ and for all $n\in \mathbb{\mathbb{Z}}$, there exist $q\in \mathbb{\mathbb{Z}}$ and $r\in \mathbb{\mathbb{Z}}$ such that

$n=mq+r0\le r<m$

Where $q$ is the quotient and $r$ is the remainder.

Theorem 6.6

A subgroup of a cyclic group is cyclic.

Proof. Let $G=⟨a⟩$ be a cyclic subgroup, and let $H\le G$.

If $H=\left\{e\right\}$ (trivially cyclic), we're done.

Otherwise, for some element $e\ne c\in H$, we know $c=a^m$ for some smallest positive integer $m$.

The claim is that $H=⟨a^m⟩$.

Let's pick an element $b\in H$. We know that $b=a^n$ for some $n$. We can write $n$ via the division algorithm: $n=mq+r$. Therefore $b=a^n=a^{mq+r}=(a^m{)}^q\cdot a^r$. Since $r<m$, we must assume $r=0$ since $m$ was defined to be smallest positive integer.

From this, we get "All subgroups of $⟨\mathbb{\mathbb{Z}},+⟩$ are of the form $n\mathbb{\mathbb{Z}}$" as a corollary.

Greatest common divisor also comes as a result of this.

Greatest Common Divisor

Exercise 45 in the book (for homework) asks us to prove $H=\{nr+ms\mid n,m\in \mathbb{\mathbb{Z}}\}$ is a subgroup of $\mathbb{\mathbb{Z}}$. For this we know $H$ is cyclic (because $\mathbb{\mathbb{Z}}$ is cyclic), and its generator must be of the form $H=⟨d⟩$ for generator $d=\mathrm{g}\mathrm{c}\mathrm{d}(r,s)$. Therefore $d=nr+ms$ for some $r,s\in \mathbb{\mathbb{Z}}$.

Coprimality

We say that two integers $r$ and $s$ are coprime (or relatively prime) if $\mathrm{g}\mathrm{c}\mathrm{d}(r,s)=1$. Thus $1=mr+ns$ for some $m,n\in \mathbb{\mathbb{Z}}$.

If $r$ divides a product of integer factors, it must divide at least one of the factors.

Theorem 6.10

Classification of Cyclic Groups

Let $G=⟨a⟩$ be cyclic.

• If $|G|=\mathrm{\infty }$, then $G\simeq \mathbb{\mathbb{Z}}$.
• If $|G|=n<\mathrm{\infty }$, then $G\simeq \mathbb{\mathbb{Z}}$

Proof. For all $m\in {\mathbb{\mathbb{Z}}}^{+}$, $a^m\ne e$. We claim that $a^m\ne a^n$ if $m\ne n$ because $a^m=a^n$ implies $a^m\cdot (a^n{)}^{-1}=a^{m-n}=e$. But for $m>n$, this is not true.

Now let $\varphi :G\to \mathbb{\mathbb{Z}}$ be defined as $\varphi (a^m)=m$. $\varphi$ is one-to-one because $a^m\ne a^n⟺m\ne n$. $\varphi$ is also onto. Finally, $\varphi (a^m\cdot a^n)=\varphi (a^m)+\varphi (a^n)$.

Similarly, a group

$G=\{e,a,a^2,\dots ,a^{n-1}\}$

corresponds to

$\mathbb{\mathbb{Z}}=\{0,1,2,\dots ,n-1\}$

.

quod erat demonstrandum

Consequently, $G\simeq {\mathbb{\mathbb{Z}}}_n\simeq U_n$. This is why these are called cyclic groups

Structure of Cyclic Subgroups

We already know that $\mathbb{\mathbb{Z}}$ has only subgroups $n\mathbb{\mathbb{Z}}$. In particular, if $m\mathbb{\mathbb{Z}}<n\mathbb{\mathbb{Z}}$, then $n\mid m$.

Theorem 6.14

Let $|G|=n$, so $G\simeq {\mathbb{\mathbb{Z}}}_n$. Furthermore, let $G=⟨a⟩$. Let $b=a^s\in G$. And finally, let $H=⟨b⟩\le G$.

$|H|=\frac{n}{d}$

where $d=\mathrm{g}\mathrm{c}\mathrm{d}(n,s)$, and

$⟨a^s⟩=⟨a^t⟩⟺\mathrm{g}\mathrm{c}\mathrm{d}(s,n)=\mathrm{g}\mathrm{c}\mathrm{d}(t,n)$

There is something wrong with the second part of this theorem in the book. Find it and report it next time.

Corollary. if $|G|=n$ and $G=⟨a⟩$, then other generators are of the form $a^s$, where $\mathrm{g}\mathrm{c}\mathrm{d}(s,n)=1$.