Abstract Algebra with Maple
Chapter 5: Cyclic Groups

5. Cyclic Groups

Primitive Roots

Group has generators. To find them, we can use procedure un . For example,

> un:=n->select(m->evalb(igcd(m,n)=1),[$1..n]):

> un(20);

The generators of U ( n ) if they exist, are called primitive roots mod n . One of them can be found using the function primroot from the numtheory package that we already loaded in section 2. For example,

> with(numtheory):

> primroot(43);

It fails when the group U ( n ) is not cyclic, so it doesn't have a generator. For example,

> primroot(45);

To find all generators, we can use the following procedure:

> primroots:=n->{seq(primroot(n)^un(phi(n))[i] mod n, i=1..phi(phi(n)))}:

For example,

> primroots(43);

> primroots(45);

The number of generators of U ( n ) equals when it is a cyclic group. For example,

> phi(phi(43));

Elements of Order d

Theorem 4.4 on p. 80 of Dr. Gallian's text tells us that if d is a positive divisor of n , then there are elements of order d in . The following procedure lists all of them:

> nordlist:=(d,n)->`if`(type(n/d,integer),map(x->x*n/d mod n,un(d)),[]):

For example, the list of elements of order 20 in :

> nordlist(20,100);

The following procedure counts the number of elements of order d in U ( n ):

> nordU:=proc(d,n) local i, k;
k:=0; for i from 1 to phi(n) do if order(un(n)[i],n)=d then k:=k+1 fi od; k end:

For example, the number of elements of order 2 in U (45):

> nordU(2,45);

It immediately implies that U (45) is not a cyclic group, because a cyclic group might have either 0 elements of order 2 if it has an odd order, or 1 element of order 2 if it has an even order.

The following procedure counts the number of elements of order d in an extended group G :

> Nord:=proc(d,g) local i, k;
k:=0; for i from 1 to nops(g[1]) do if Ord(g[1][i],g)=d then k:=k+1 fi od; k end:

For example, the number of elements of order 10 in SL (2, ):

> Nord(10,SL2(5));

Notice that

> phi(10);

and 24 is divisible by , as it is supposed to be according to the Corollary on p. 80 of Dr. Gallian's book.

Another example, the number of elements of order 2 in groups GL (2, ) for n from 2 to 6:

> for n from 2 to 6 do Nord(2,GL2(n)) od;

Subgroup Lattice of

We have to load two packages for this section:

> with(plottools): with(networks):

Warning, these names have been redefined: dodecahedron, icosahedron, octahedron, tetrahedron

A subgroup lattice of can be drawn using the following procedure:

> subZ:=proc(n) local d,i,j,k,x,G,len,L,LL;
new(G); d:=divisors(n);
addvertex(map(x->cat(`<`,x mod n,`>`),d),G); len:=a->add(ifactors(a)[2,i,2],i=1..nops(ifactors(a)[2]));
L:=seq(convert(select(a->evalb(len(a)=i),d),list),i=0..len(n));
for i from 1 to len(n) do for j from 1 to nops(L[i]) do for k from 1 to nops(L[i+1]) do
if L[i+1,k] mod L[i,j] = 0 then addedge(map(x->cat(`<`,x mod n,`>`),[L[i,j],L[i+1,k]]),G) fi od od od;
LL:=seq(map(x->cat(`<`,x mod n,`>`),L[i]),i=1..len(n)+1);
rotate(draw(Linear(LL),G),-Pi/2);
end:

For example, for n = 30:

> subZ(30);

It looks like a cube, doesn't it? Even more after rotating the picture by 90 degrees:

> rotate(%,Pi/2);

Another example, for n = 210 (a 4-dimensional hypercube:-)

> subZ(210);

Don't stop at that, draw a 5-dimensional hypercube!

> subZ(2310);

Number of subgroups of equals the number of divisors of n , which can be evaluated using the function tau :

> tau(30);

> tau(210);

> tau(2310);

>

Exercises.

• 1 . Find which of the groups U ( n ) with n from 46 to 54 are cyclic, and find the generators for them.
• 2 . Find the number of elements of the order 10 in and list all of them.
• 3. Find the number of elements of the order 2 in U (24).
• 4 . Find the number of elements of the order 12 in SL (2, ).
• 5 . Find the number of elements of the order 2 in GL (2, ) for n from 7 to 20.
• 6 . List the elements of the order 3 in SL (2, ).
• 7 . Draw subgroup lattices of , , and .