1. ## 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!

2. Hi!

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

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

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

Then, the definition of a generator of a group:
Let G be a group and $\displaystyle 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, $\displaystyle 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 $\displaystyle 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 $\displaystyle ax+by=d$.
In our case, take $\displaystyle a=$ one of those 1,5,7,11,13 and 17, take $\displaystyle b=18$ and, of course, $\displaystyle d=1$. Can you finish from here?

3. 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.

$\displaystyle \phi(18)=\phi(3)\phi(6)=2 \times 3 = 6$. Those are 1, 5, 7, 11, 13, 17.

4. 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.

5. You check closure under some operation exactly as noted in 3) and 4) in my first post:

"3) is closed under the operation , that is, for every also "

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) is closed under the operation $\displaystyle \cdot$ that is, for every also "

This is similar, for arbitrary elements a,b from H you must verify that $\displaystyle 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 $\displaystyle a, b \in$ <3> then $\displaystyle a+b$ is also a multiple of 3.
So 3) and 4) are checked.

6. thank you for the explanation!(:

7. you're most welcome