MATH 415 Lecture 4

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

Subgroups

$H$ is a subgroup of $G$ (denoted $H\leq 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\neq G$.

Cyclic Subgroups

We call $\left\langle a\right\rangle$ a cyclic subgroup of a group $\left\langle G,*\right\rangle$ generated by $a$, where $a$ is the generator.

We call a group $\left\langle G,*\right\rangle$ cyclic if there is an element $a\in G$ such that $G=\left\langle a\right\rangle$.

If we take an arbitrary group $\left\langle G,\cdot \right\rangle$ 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=\left\{a^{n}~\mid ~n\in \mathbb {Z} \right\}\,\!$

This is a subgroup generated by $a$, with notation $H=\left\langle a\right\rangle$.

Theorem. $H=\left\langle a\right\rangle$ is the smallest subgroup of $G$ containing $a$.

Examples on Integers

It's worth noting that $\mathbb {Z} =\left\langle 1\right\rangle =\left\langle -1\right\rangle$.

All subgroups of $\left\langle \mathbb {Z} ,+\right\rangle$ are of the form $n\,\mathbb {Z}$. When $n\neq \pm 1$, then $n\,\mathbb {Z} <\mathbb {Z}$.

Consider $\left\langle \mathbb {Z} _{12},+\right\rangle$:

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

Consider subgroup $\left\langle 3\right\rangle =H=\left\{0,3,6,9\right\}$, a subgroup of $\mathbb {Z} _{12}$

We call $\left\langle 3\right\rangle$ 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=\left\langle a\right\rangle$, 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 {Z} ^{+}$ and for all $n\in \mathbb {Z}$, there exist $q\in \mathbb {Z}$ and $r\in \mathbb {Z}$ such that

$n=m\,q+r\quad \quad 0\leq 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=\left\langle a\right\rangle$ be a cyclic subgroup, and let $H\leq G$.

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

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

The claim is that $H=\left\langle a^{m}\right\rangle$.

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=m\,q+r$. Therefore $b=a^{n}=a^{m\,q+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 $\left\langle \mathbb {Z} ,+\right\rangle$ are of the form $n\,\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=\left\{n\,r+m\,s~\mid ~n,m\in \mathbb {Z} \right\}$ is a subgroup of $\mathbb {Z}$. For this we know $H$ is cyclic (because $\mathbb {Z}$ is cyclic), and its generator must be of the form $H=\left\langle d\right\rangle$ for generator $d=\mathrm {gcd} (r,s)$. Therefore $d=n\,r+m\,s$ for some $r,s\in \mathbb {Z}$.

Coprimality

We say that two integers $r$ and $s$ are coprime (or relatively prime) if $\mathrm {gcd} (r,s)=1$. Thus $1=m\,r+n\,s$ for some $m,n\in \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=\left\langle a\right\rangle$ be cyclic.

• If $|G|=\infty$, then $G\simeq \mathbb {Z}$.
• If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |G| = n < \infty} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G \simeq \mathbb{Z}}

Proof. For all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \in \mathbb{Z}^+} , $a^{m}\neq e$. We claim that $a^{m}\neq a^{n}$ if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \ne n} because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^m = a^n} implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^m \cdot (a^n)^{-1} = a^{m-n} = e} . But for $m>n$, this is not true.

Now let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi : G \to \mathbb{Z}} be defined as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(a^m) = m} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} is one-to-one because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^m \ne a^n \iff m \ne n} . $\phi$ is also onto. Finally, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(a^m \cdot a^n) = \phi(a^m) + \phi(a^n)} .

Similarly, a group Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \{ e, a, a^2, \ldots, a^{n-1} \}} corresponds to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z} = \{ 0, 1, 2, \ldots, n-1 \}} .

quod erat demonstrandum

Consequently, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G \simeq \mathbb{Z}_n \simeq U_n} . This is why these are called cyclic groups

Structure of Cyclic Subgroups

We already know that $\mathbb {Z}$ has only subgroups Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \, \mathbb{Z}} . In particular, if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \, \mathbb{Z} < n \, \mathbb{Z}} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \mid m} .

Theorem 6.14

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |G| = n} , so $G\simeq \mathbb {Z} _{n}$. Furthermore, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \left\langle a \right\rangle} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b = a^s \in G} . And finally, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H = \left\langle b \right\rangle \le G} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |H| = \frac{n}{d} \,\!}

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\langle a^s \right\rangle = \left\langle a^t \right\rangle \iff \mathrm{gcd}(s,n) = \mathrm{gcd}(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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |G| = n} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \left\langle a \right\rangle} , then other generators are of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^s} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{gcd}(s,n) = 1} .