## Cyclic Groups and Generators

Some groups have an interesting
property: all the elements in the group can be obtained by repeatedly
applying the group operation to a particular group element. If a group
has such a property, it is called a cyclic group and the particular
group element is called a generator. A trivial example is the group
*Z*_{n}, the additive group of
integers modulo *n*. In
*Z*_{n}, 1 is always a
generator:

1 ≡ 1 mod n

1+1 ≡ 2 mod n

1+1+1 ≡ 3 mod n

...

1+1+1+...+1 ≡ n ≡ 0 mod n

If a group is cyclic, then there may exist multiple generators.
For example, we know *Z*_{5} is a
cyclic group. The element 1 is a generator for sure. And if we take a
look at 2, we can find:

2 ≡ 2 mod 5

2+2 ≡ 4 mod 5

2+2+2 ≡ 6 ≡ 1 mod 5

2+2+2+2 ≡ 8 ≡ 3 mod 5

2+2+2+2+2 ≡ 10 ≡ 0 mod 5

So all the group elements {0,1,2,3,4} in
*Z*_{5} can also be generated by
2. That is to say, 2 is also a generator for the group
*Z*_{5}.

Not every element in a group is a generator. For example, the
identity element in a group will never be a generator. No matter how
many times you apply the group operator to the identity element, the
only element you can yield is the identity element itself. For example,
in *Z*_{n}, 0 is the identity
element and 0+0+...+0 ≡ 0 mod n in all cases.

Not every group is cyclic. For example,*
Z*_{n}^{*}, the
multiplicative group modulo n, is cyclic if and only if
*n* is 1 or 2 or 4 or
*p*^{k} or
*2*p*^{k} for an odd prime
number *p* and *k* ≥ 1. So
*Z*_{5}^{*}
must be a cyclic group because 5 is a prime number. Actually all the
elements in
*Z*_{5}^{*},
{1,2,3,4} can be generated by 2:

2^{1} ≡ 2 mod 5

2^{2} ≡ 4 mod 5

2^{3} ≡ 8 ≡ 3 mod 5

2^{4} ≡ 16 ≡ 1 mod 5

And
*Z*_{12}^{*}
is not a cyclic group. The elements in
*Z*_{12}^{*}
are: {1,5,7,11}. Obviously the identity element 1 cannot be a generator.
Let's check the other three elements:

None of the elements can generate the whole group. Therefore, none
of them is a generator. So
*Z*_{12}^{*}
is indeed not cyclic.

If
*Z*_{n}^{*}
is cyclic and *g* is a generator of
*Z*_{n}^{*},
then *g* is also called a primitive root modulo
*n*.