# subgroups and generators

• Aug 30th 2009, 04:45 AM
alexandrabel90
subgroups and generators
Hi,
Im really confused with subgroups and generators. May I know what is the difference?

I was reading a book where they state that the subgroups of Z18 are <0>,<1>,<2>,<3>,<6>,<9> and the generators are 1,5,7,11,13 and 17. what does that mean?

Thanks!
• Aug 30th 2009, 06:15 AM
Taluivren
Hi!

Firstly let's revise the definition of subgroup:
Let $\langle G, \cdot, ^{-1}, e \rangle$ be a group ( $\cdot$ is the binary operation, $^{-1}$ is unary operation of taking an inverse and $e$ is the identity element). If a set $H$ satisfies following conditions:
1) $H \subseteq G$
2) $H$ contains the identity element $e$ of $G$,
3) $H$ is closed under the operation $^{-1}$, that is, for every $a \in H$ also $a^{-1} \in H$
4) $H$ is closed under the operation $\cdot$, that is, for every $a, b \in H$ also $a \cdot b \in H$,
then we say that $H$ is a subgroup of $G$.

This means that the set $H$ together with operation $\cdot$ restricted to $H$ and with the identity element $e$ forms a group.

In Z18, for example $\{0, 6, 12\}$ is a subgroup, or whole Z18 is a subgroup, or $\{0\}$ is a subgroup,... (check it!)

Then, the definition of a generator of a group:
Let G be a group and $S \subseteq G$ be a set. We say that S is a generating set of G, if every element of G can be expressed as the product of finitely many elements of S and their inverses. We write this as <S> = G. When there is only one element in S, $S = \{x\}$, we write <x> = G and we say that the group G is generated by x, or that x is its generator.

Now to your example. What are the generators of Z18? We see that 1 is surely a generator (every element of Z18 can be expressed as 1+1+..+1)
Are there any other generators? Yes, exactly those stated in your book, let's see why. Firstly, can you see why the remaining elements are not generators?
Spoiler:

Every such element a has a common factor (>1) with 18. No matter how long the sequence $a+a+...+a$ is, the result will always have this common factor with 18. So you can never get the element 1 (which does not have this common factor with 18)! Thus, a doesn't generate G.

Next, let's verify that every of the elements 1,5,7,11,13 and 17 generates Z18. If you have heard of Bezout's identity, it is easy. It says that if a and b are nonzero integers with greatest common divisor d, then there exist integers x and y such that $ax+by=d$.
In our case, take $a=$ one of those 1,5,7,11,13 and 17, take $b=18$ and, of course, $d=1$. Can you finish from here?
• Aug 30th 2009, 06:23 AM
algtop
Quote:

Originally Posted by alexandrabel90
Hi,
Im really confused with subgroups and generators. May I know what is the difference?

I was reading a book where they state that the subgroups of Z18 are <0>,<1>,<2>,<3>,<6>,<9> and the generators are 1,5,7,11,13 and 17. what does that mean?

Thanks!

<0>={0}
<1>=<5>=<7>=<11>=<13>=<17>=Z_18 (the whole group)
<2>={0,2,4,6,8,10,12,14,16}
<3>={0,3,6,9,12,15}
<6>={0,6,12}
<9>={0,9}

You can check that the above sets satisfy the group axioms under addition operation.

You can generate a whole group using 1 only ( For instance, 5=1+1+1+1+1, 0 = 1+1+1+..... (18 times 1).

There is a pattern for a generator 1, 5, 7, 11, 13, 17 of Z_18. They are all coprime with Z_18.

The number of generators for Z_18 can be acquired by using an Euler totient function.

$\phi(18)=\phi(3)\phi(6)=2 \times 3 = 6$. Those are 1, 5, 7, 11, 13, 17.
• Aug 30th 2009, 08:24 AM
alexandrabel90
thank you! i get it now..

by the way, how do you check that it is closed under -1 and under the operation?

I can never grasp the concept of something being closed.
• Aug 30th 2009, 08:52 AM
Taluivren
You check closure under some operation exactly as noted in 3) and 4) in my first post:

"3) http://www.mathhelpforum.com/math-he...49c17196-1.gif is closed under the operation http://www.mathhelpforum.com/math-he...38ef43ea-1.gif, that is, for every http://www.mathhelpforum.com/math-he...8f44fa3e-1.gif also http://www.mathhelpforum.com/math-he...b9e79d4a-1.gif"

This means if someone gives you an arbitrary element from the subset H, you have to prove that its inverse (which is known to exist and be unique because G is a group) also belongs to the subset H. If the inverse is not in H, then H can't be a subgroup!

"4)http://www.mathhelpforum.com/math-he...49c17196-1.gif is closed under the operation $\cdot$ that is, for every http://www.mathhelpforum.com/math-he...a20c94c9-1.gif also http://www.mathhelpforum.com/math-he...5c821a40-1.gif"

This is similar, for arbitrary elements a,b from H you must verify that $a \cdot b$ also belongs to H.

So in your example we can check that <3>={0,3,6,9,12,15} is closed under taking inverses: they are all multiples of 3 from Z18, inverse of any element a of this set is 18 - a which is also a multiple of 3. And if $a, b \in$ <3> then $a+b$ is also a multiple of 3.
So 3) and 4) are checked.
• Aug 30th 2009, 09:03 AM
alexandrabel90
thank you for the explanation!(:
• Aug 30th 2009, 09:04 AM
Taluivren
you're most welcome