📚 The CoCalc Library - books, templates and other resources

cocalc-examples / paulsen-abstract-algebra / group02.ipynb

¹³²⁹²² views
License: OTHER

Kernel: SageMath (stable)

Abstract Algebra: An Interactive Approach, 2e

Chapter 2
The Structure Within a Group

Initialization: This cell MUST be evaluated first:

In [0]:

%display latex
try:
    load('absalgtext.sage')
except IOError:
    load('/media/sf_sage/absalgtext.sage')

Generators of Groups
Defining Finite Groups in Sage
Subgroups
Sage Interactive Problems

Generators of Groups

In the last chapter, we introduced the definition of a group, giving some simple examples of groups. There are, of course, many other examples of groups that we will want to work with. We want to learn how to efficiently program Sage to work with any specific group. Many of these groups will be fairly large, and so rather than giving Sage the entire group, we will define a group using a very small number of elements. From these few elements, Sage will be able to reconstruct the entire group. These few elements will be called the generators of the group. So before we can learn how to program a group into Sage, we first need to understand generators.

In this section we will deal with finite groups, that is groups which only have a finite number of elements. We have seen several examples of finite groups, such as Terry's group, Z_n, and Z_n^*. Let us return to one of the groups that we studied in the last section, Z₁₀.

EXPERIMENT:
Study the powers of the elements 3 and 4 in the group Z₁₀.

The following command loads this group into Sage.

In [0]:

G = ZGroup(10); G

One of the experiments from the last section was to make circle graphs of the opperation "Add n to each number." For example, the circle graph of Add(3), which maps each element x to the element x+3, is given by

In [0]:

CircleGraph(G, Add(3))

This graph allows us to visualize powers of 3 in the group Z₁₀. If we follow the red arrows, starting with 0, we have the sequence

{0, 3, 6, 9, 2, 5, 8, 1, 4, 7, 0 …}

This tells us that, in this group Z₁₀,

3⁰ =	0,
3¹ =	3,
3² =	3·3 = 6
3³ =	3·3·3 = 9
3⁴ =	3·3·3·3 = 2, etc.

Recall that in this group, the dot represents addition modulo 10, so an exponient represents repeated addition. It is easy to see from the circle graph that every element in the group can be expressed as a power of 3, since one can travel the red arrows to get from 0 to any element of the group. This will not always be the case, as the circle graph of "Add(4)" indicates.

In [0]:

CircleGraph(G, Add(4))

Notice that Sage draws this graph with arrows of two different colors. This highlights the fact that one cannot travel an arrow to get from a red point to a green point. Thus, not every element can be written as a power of 4.

DEFINITION 2.1
We'll say that the element g ∈ G is a generator of the group G if every element of G can be expressed as a power of g.

EXPERIMENT:
Using the circle graph, determine which elements of Z₁₀ are generators. Is this set of numbers familar?

We can have Sage list all of the generators of a group for us, using the command Generators(). In the case of Z₁₀, the generators are:

In [0]:

Generators(G)

EXPERIMENT:
Try finding the generators of Z_n for different values of n. Do you notice a pattern?

EXAMPLE:
Find all of the generators of the group Z₇^*.

This group is small enough to do by hand. For each of the elements in Z₇^* = {1, 2, 3, 4, 5, 6}, we raise the element to different powers until we reach the identity.

1² = 1.

2² = 4, 2³ = 1.

3² = 2, 3³ = 6, 3⁴ = 4, 3⁵ = 5, 3⁶ = 1.

4² = 2, 4³ = 1.

5² = 4, 5³ = 6, 5⁴ = 2, 5⁵ = 3, 5⁶ = 1.

6² = 1

Thus, we see that 3 and 5 are generators.

From the first experiment one might notice a pattern. Notice that 1 will always be a generator of Z_n, for Add(1) takes every point on the circle to the next point. See if you can use this fact to prove the next proposition.

PROPOSITION 2.1
The generators of Z_n are precisely the integers between 0 and n that are coprime to n.

Click here for the proof.

The count of numbers less than n that are coprime to n is called the Euler totient function of n, and is denoted ϕ(n). Thus, the number of generators of Z_n is precisely ϕ(n). Here is a small table of this function up to n = 36.

Table of ϕ(n)
n	ϕ(n)	n	ϕ(n)	n	ϕ(n)
1	1	13	12	25	20
2	1	14	6	26	12
3	2	15	8	27	18
4	2	16	8	28	12
5	4	17	16	29	28
6	2	18	6	30	8
7	6	19	18	31	30
8	4	20	8	32	16
9	6	21	12	33	20
10	4	22	10	34	16
11	10	23	22	35	24
12	4	24	8	36	12

For larger values of n, we can use the Sage command EulerPhi. For example, to find the number of generators of Z₆₀, type

In [0]:

EulerPhi(60)

How does Sage come up with this anwser? It uses a fairly simple formula based on the prime factorization of the number. Here is the formula, along with a proof of why this formula works:

THEOREM 2.1: The Totient Function Theorem
If the prime factorization of n is given by

n = p₁^r¹ · p₂^r² · p₃^r³ ··· p_k^rₖ,

where p₁, p₂, p₃, … p_k are primes, and r₁, r₂, r₃, … r_k are positive integers, then the count of numbers less then n which are coprime to n is

ϕ(n) = (p₁ − 1)p₁^r¹⁻¹ · (p₂ − 1)p₂^r²⁻¹ · (p₃ − 1)p₃^r³⁻¹ ··· (p_k − 1)p_k^rₖ−1,

Click here for the proof.

Now that we know how to find generators of Z_n, let us move on to other groups. Consider for example Z₁₀^*. First we load this into Sage:

In [0]:

G = ZStar(10); G

The elements are {1, 3, 7, 9}. Is 1 a generator of this group? Let's check:

In [0]:

CircleGraph(G, Mult(1))

We see that 1 is not a generator because 1 is the identity element.

EXPERIMENT:

Replace Mult(1) in the last command with Mult(3), Mult(7), and Mult(9) to see which elements, if any, are generators. Recall that the test for a generator is that any element can be reached by any other element in the circle graph by means of the arrows. How many generators are there?

According to the table for ϕ(n), Z₈^* also has four elements. Let us try the same experiment with Z₈^*. First we load the group into Sage:

In [0]:

G = ZStar(8); G

The elements of this group are {1, 3, 5, 7}. Let us check to see if 3 is a generator:

In [0]:

CircleGraph(G, Mult(3))

EXPERIMENT:

Replace Mult(3) in the above command with Mult(5), Mult(7), and Mult(1). How many generators are there to this group?

By doing this experiment, you will discover that Z₈^* has a totally different structure than Z₁₀^*, in spite of the similarity in how they are defined. As you tried to determine why no element of Z₈^* acts as a generator, you might notice that every element squared is equal to 1. This is seen in the multiplication table

In [0]:

MultTable(G)

We can also verify this by finding the set of generators of Z₈^*.

In [0]:

Generators(G)

Because of this property of Z₈^*, no element can generate the whole group.

From these examples, we see that some groups have generators, while others do not. This leads us to the following definition.

DEFINITION 2.2
We say a group is cyclic if there is one element that can generate the entire group.

Although we have seen an example of a finite group that is not cyclic, we will later see that the structure of any finite abelian group can be expressed in terms of cyclic groups.

Even when a group is not cyclic, we sometimes can find two elements by which every element of the group can be expressed. For example, consider the group Z₈^*, and the two elements 3 and 5. The following command maps both Mult(3) and Mult(5) on the same circle graph.

In [0]:

CircleGraph(G, Mult(3), Mult(5))

The red arrows represent multiplying by 3, while the green arrows represent multiplication by 5. Notice that by a combination of red and green arrows, any element of the group can reach any other element through a sequence of arrows, even though neither the red arrows alone nor the green arrows can do this job. We say that the set {3,5} generates the group.

Let us look at one more example. Consider Terry's group, which is loaded into Sage by the command

In [0]:

G = InitTerry(); G

Let us see if one of the dance steps will generate the group.

In [0]:

CircleGraph(G, Mult(Spin))

EXPERIMENT:
By replacing the "Spin" in the last command with the other elements of Terry's group, see if any of the elements generate the group. If not, see if you can find a combination of two elements which generate the group.

One of the keys for entering a group into Sage is knowing one or two elements (or sometimes even three) that will generate the entire group. This information begins to reveal the structure of the group itself.

Defining Finite Groups in Sage

This part of the worksheet shows how to define finite groups in only Sage. The corresponding section in the Mathematica notebook explains entering groups into Mathematica.

We saw in the last section that for some groups there is a single element that generates the entire group, whereas in other groups two or more elements are required. In this section we will show how a finite group can be entered into Sage using a set of elements that generates the group. We will begin with a cyclic group Z_n which has a single generator which we will call x. From the circle graphs of Z_n that we saw in the last secton, we could see that the sequence of n elements

e =	x⁰,
x =	x¹,
x·x =	x²,
x·x·x =	x³,
⋯⋯⋯⋯	⋯⋯
x·x·x· ⋯ ·x =	xⁿ⁻¹,

must mention every element of Z_n exactly once. In fact, this gives us a way to label the elements of Z_n in terms of the generator x. We also find that xⁿ = e. Thus, we can define the group Z_n merely by saying "x is a generator of the group, and n is the lowest positive number such that xⁿ is the identity."

There are Sage routines included that allow us to quickly make these definitions. Execute the following three statements:

In [0]:

InitGroup("e")

In [0]:

AddGroupVar("x")

In [0]:

Define(x^5, e)

What does this do? The first command we have seen once before: it defines the identity element to be e. The second command defines "x" to be a group variable. Finally, the third command defines x⁵ to be the identity. This is all we need to define the group Z₅.

Of course we will want to see the group. The Sage command ListGroup() lists the elements of the currently defined group in a systematic order.

In [0]:

Z5 = ListGroup(); Z5

Thus, the elements of this group are:

{e, x, x², x³, x⁴}.

A multiplication table can be given by:

In [0]:

MultTable(Z5)

Although the {0, 1, 2, 3, 4} notation is more concise for this particular example, the use of generators is more versitile, since almost all finite groups can be expressed easily using generators.

EXAMPLE:
Define the group Z₈^* in Sage.

We saw that every element of this group squared is the identity so this group is not cyclic. However, we found that every element can be expressed in terms of two of the elements, 3 and 5. Hence the set {3, 5} generates the group.

By calling a = 3 and b = 5, we can define the group this way:

In [0]:

InitGroup("e")

In [0]:

AddGroupVar("a")

In [0]:

AddGroupVar("b")

In [0]:

Define(a^2, e)

In [0]:

Define(b^2, e)

Is this enough to define the group? Since 7 = 3·5, the last element can be written a·b. The list of four elements would be

In [0]:

G = [e, a, b, a*b]

Let us see the multiplication table:

In [0]:

MultTable(G)

Notice the four black squares, such as one corresponding to b times a. Sage needs to be told that b·a is the same thing as a·b, so we need a third define statement:

In [0]:

Define(b*a, a*b)

Will this be enough for Sage to find all products? This last Define command redefined the meaning of the variables a and b, so we must first relist the elements of the group.

In [0]:

G = [e, a, b, a*b]

In [0]:

MultTable(G)

This time, there are no black squares, so the group has been completely defined in Sage. We can also find out if we have finished defining the group by entering the command

In [0]:

Group(a, b)

As long as Sage returns with a list of elements, the group has been sucessfully been defined. Notice that since we needed two generators for this group, we needed to include both generators in the Group command.

We can define several groups in Sage at the same time, and by listing the generators with the Group command, Sage will know which group we are refering to. In contrast, ListGroup() will only list the most recently defined group. In fact, it is a good idea to use a different letter for the identity element if we are to define two different groups, and use different letters for the generators.

EXAMPLE:
Suppose we have three different books on a shelf, and we consider rearrangements of the books. Enter this group into Sage.

We can illustrate the three books by executing the following command:

In [0]:

InitBooks(3)

Suppose we want to rearrange the three books. One way we can rearrange them is to swap the first two books. This can be done with the command

In [0]:

MoveBooks(First)

Another way we can rearrange the books is to take the first book out, slide the other two to the left, and replace the book after the other two. This can be done by the command:

In [0]:

MoveBooks(Left)

EXPERIMENT:
By using only the commands First and Left, how many ways can you rearrange the three books? There are a total of 6 ways to arrange three books. Can you obtain all 6 arrangements using just these two commands?

In doing this experiment, you probably found that there are four other ways we could have rearranged the books, namely swapping the last two books (Last), moving that last book to the front (Right), reversing the order of the books (Rev), and finally leaving the books as they are (Stay). These four additional motions also work in the MoveBooks command, yet the last experiment showed that all arrangements can be obtained using just the commands First and Left. Therefore, the set {First, Left} generates the group of all permutations of the three books.

Let us define this group in Sage. Rather than using the names, we will use the abbreviations: e = the identity element, a = First, and b = Left.

We begin by defining the identity element to be e.

In [0]:

InitGroup("e")

Next, we have to set up the variables a and b to be two members of the group. We can do this with one AddGroupVar command.

In [0]:

AddGroupVar("a","b")

Now, if we swap the first two books twice, we get back where we started. We thus see that a² = e. So we define:

In [0]:

Define(a^2, e)

If we perform the Left action three times, we also will be back where we started. Thus, we have b³ = e so we can define

In [0]:

Define(b^3, e)

In defining Z₈^*, we needed to also define b·a in terms of a·b. Let us do that for this group also. Notice what happens if we first move the books to the left, and then swap the first two books:

In [0]:

InitBooks(3); MoveBooks(Left, First)

Is this the same result if we do those actions in the opposite order? Let's check:

In [0]:

InitBooks(3); MoveBooks(First, Left)

Apparently, we need to move the books once more to the left to get the same effect. Let's try it.

In [0]:

InitBooks(3); MoveBooks(First, Left, Left)

This tells us that b·a = a·b·b. This group is apparently not commutative. We enter this final definition into Sage.

In [0]:

Define(b*a, a*b^2)

If we use the Group command to find the list of elements,

In [0]:

Group(a, b)

we find that the last two elements are not written in standard order. In fact, if we compare this list to the ListGroup output,

In [0]:

G = ListGroup(); G

we find that a·b·a is really b². Sage is able to tell us that these are the same element,

In [0]:

a*b*a == b^2

but will not immediately simplify an expression involving group elements.

In [0]:

b^7

Sage will, however, simplify expressions when putting them in a multiplication table.

In [0]:

MultTable(G)

Is this really a group? We can tell from the multiplication table that G is closed with respect to multiplication, and that there is an identity element, e. We also recognize the familiar Latin square property that we have seen in all of the other multiplication tables. Since every row and every column contains exactly one e, every element has a unique inverse. The only property that we cannot check directly using the multiplication table is the associativity property. But this property is guaranteed by the way Sage defines groups. We call this group S₃, the permutation group on 3 objects. (Obviously it makes no difference what the three objects are. Books are just one possibility.)

Can Sage determine the inverse of an element? Let's try it:

In [0]:

(a*b)^-1

Apparently, Sage is using Proposition 1.2, (u·v)^-1 = v^-1·u^-1. However, it does not simplify this to simpliest form. However, it will be able to detect which element this is.

In [0]:

(a*b)^-1 == a*b

At first it might seem frustrating that Sage does not simplify group elements. However, the command

In [0]:

SetReducedMult()

will cause all products to reduce to their simpliest form. Unfortunately, this isn't the same form as the elements given in ListGroup.

In [0]:

(a*b)^-1

In [0]:

a*b

See if you can determine which elements of this group are their own inverses.

EXPERIMENT:
You may have noticed some simularities between the group S₃ and Terry's group. How are these two groups related?

Hint: Terry is colored with the same three colors as the books. Can you find a correspondence between an orientation of Terry and an arrangement of the three books?

The relationship between Terry's group and S₃ becomes crystal clear when we look at the multiplication tables of these two. The following Sage command reloads S₃, and displays a multiplication table.

In [0]:

InitGroup("e"); 
AddGroupVar("a","b"); 
Define(a^2,e); 
Define(b^3,e); 
Define(b*a,a*b^2); 
G = ListGroup(); 
MultTable(G)

The following command does the same thing for Terry's group.

In [0]:

G = InitTerry();
MultTable(G)

Notice that even though the names of the elements are different, the color patterns in the two tables are identical. Since all of the group properties come from the multiplication table, these two groups must act in exactly the same way. We say that Terry's group and S₃ are isomorphic. We will cover isomophic groups later in Chapter 4.

Let's see an example of a larger group. The command below produces a picture of an octahedron. (Think of this as two square pyramids fused together at the bases.)

In [0]:

InitOctahedron()

This happens to be the shape of an uncut diamond. (Many other gemstones are this shape.) There are eight triangles, which are colored with eight different colors. One problem a gem cutter often faces is determining the orientation he should put the gemstone before he starts to cut. In which case, he needs to know all of the possible ways the octahedron can be rotated. The set of rotations would form a group, similar to Terry's dance steps.

EXAMPLE:
Consider the group of rotations on the octahedron, and enter this group into Sage.

To see the other colors we can flip over this octahedron, using the following command:

In [0]:

RotateOctahedron(a)

Notice that in the flipping, the orange and blue faces switched places, while the red and fuchsia faces went to the other side. We can see even more of the octahedron by rotating the face closest to us, that is, the face which is now black. We can rotate this one third of a turn counter-clockwise with the command

In [0]:

RotateOctahedron(b)

Between these two actions we can see all of the colors. But there is one more thing that we can do: rotate about a vertex. We can rotate the octahedron one quarter of a turn clockwise about the vertex closest to us with the command

In [0]:

RotateOctahedron(c)

With these three actions we can rotate the octahedron in many different ways. The set of all actions formed by combining actions a, b and c form a group.

EXPERIMENT:
In the previous command, change the letter c to either a or b, and re-execute the command. Repeat this for different letters, and observe what happens. Can you get the octahedron back to the way it began? (The face closest to us was red, and the fuchsia face was immediately below it.)

In experimenting with this group you probably noticed some truisms for this group. For example, the action a, when performed twice, returns the octahedren to its starting position. The action b, performed three times, also gives us the identity. Finally, the action c must be performed four times before we get to where we started. We can explain these statements to Sage:

In [0]:

InitGroup("e")
AddGroupVar("a","b","c")
Define(a^2,e)
Define(b^3,e)
Define(c^4,e)

You may also have noticed that this group is not commutative. That is, b·a does not do the same thing as a·b. However, b·a is another kind of flip, so that b·a·b·a = e. To see this clearly, try the following command:

In [0]:

ShowOctahedron()
RotateOctahedron(b,a,b,a)

This animation told us that b·a is its own inverse, and so

b·a = (b·a)^-1 = a^-1·b^-1 = a·b²

We can enter this into Sage with the command

In [0]:

Define(b*a, a*b^2)

To find some other identities, we can try to find other combinations of a, b, and c that produce the identity element. Try this out:

In [0]:

ShowOctahedron()
RotateOctahedron(c,b,c,c,a)

Finally, try this:

In [0]:

ShowOctahedron()
RotateOctahedron(c,a,c,c,c,a,b)

These animations show us that

c·b·c²·a = e, and c·a·c³·a·b = e

Even though you probably wouldn't have discovered these on your own, you might have discovered formulas similar to these in your experimentation. Let's see what we can do with these two.

From the first one, we have that

c·b = (c·c·a) ^-1 = a^-1·c^-1·c^-1 = a·c³·c³ = a·c².

From the second, we can deduce that

c·a = (c³·a·b)^-1 = b^-1·a^-1·c^-3 = b²·a·c⁹ = b²·a·c = b·a·b²·c = a·b²·b²·c = a·b·c

Notice that we had to use the identity b·a = a·b² twice in the final computation. We can enter these properties into Sage as well:

In [0]:

Define(c*a, a*b*c)
Define(c*b, a*c^2)

Notice that we have defined b·a, c·a, and c·b in terms of operations that are performed in "alphabetical order." This is a very good strategy for defining any group. If Sage can sort b·a, c·a, and c·b into alphabetical order, then it can manipulate any combination of operations until it produces a form in alphabetical order. This is not the only way that we can define a group in Sage, but it is the one of the most efficient. Thus, Sage should have all of the information it needs to determine the group.

Let's plunge ahead and find out what this group looks like.

In [0]:

G = ListGroup(); G

We call this the octahedral group. How large is it? Well, we can either squint and count commas, or we can use the command

In [0]:

len(G)

and have Sage count for us. Either way, we find we have 24 elements in our group. (We could also have found this number using geometry on the octahedron. See Problem 7 of §2.3.)

Is the set of rotations a group? The associativity comes automatically with Sage. The other properties can be verified by looking at the multiplication table. Of course, this group is too large to write out all of the elements in the table. But watch what happens:

In [0]:

MultTable(G)

Each element is color coded in one of 24 colors, and this code is given by the list on the left. Can you use this table to find the elements which are their own inverses?

Subgroups

Whenever we have a group G, we say that H is a subset of G, denoted

H ⊆ G,

if H consists only of the elements of G. The empty set {} is always considered to be a subset, but we will restrict our attention to non-empty subsets. We are particularly interested if the set H forms a group, since we then would have a "group within a group."

DEFINITION 2.3
We say that H is a subgroup of G if H is a non-empty subset of G and H is a group with respect to the multiplication (·) of G.

It should be noted that all non-trivial groups have at least two subgroups. One subgroup contains just the identity element {e}, while another contains all of the elements of G. These two subgroups are called the trivial subgroups.

For H to be a group, it must satisfy the 4 properties of groups. But the associative property of H is guaranteed because G is associative. Thus, we need these three properties to be true:

1: H is closed under multiplication. That is,

if x and y ∈ H, then x·y ∈ H.

2: The identity element of G is in H.

3: Every element of H has its inverse in H. That is,

if x ∈ H, then x^-1 ∈ H.

These three properties can be combined into one simple test.

PROPOSITION 2.2
Let H ⊆ G, and H ≠ { }. Then H is a subgroup of G if, and only if, we have

x·y^-1 ∈ H for all x, y ∈ H.

Click here for the proof.

Let us look at an example. The following commands reload the group S₃, the permutation group on three objects, into Sage.

In [0]:

InitGroup("e")
AddGroupVar("a","b")
Define(a^2,e)
Define(b^3,e)
Define(b*a,a*b^2)
G = ListGroup(); G

Even though this is a fairly small group (6 elements) we can still find smaller groups within this one. For example, consider the subset

H = {e, b, b²}.

It is easy to see that if x and y are in H, then x·y^-1 is in H . (There are nine multiplications to check.) Therefore, this is a subgroup.

How can we verify this is a subgroup using Sage? Let us look at the multiplication table for H:

In [0]:

MultTable([e, b, b^2])

Since there are no black squares in this table, it is closed under multiplication. Also, every row and column contains one e, so inverses exist for every element. Thus, H is a subgroup of S₃.

Try the following subset instead:

In [0]:

MultTable([e, a, b])

Notice the black squares in the table. This indicates that the subset is not closed under multiplication, and hence is not a subgroup.

EXPERIMENT:
Try changing the subset in the above command to see if you can find other subgroups of S₃. How many are there? Don't forget the group itself can be considered to be a subgroup. What about the set containing just the identity?

Here is another example. Recall that ℤ is the group of integers using addition as the operation. If we let k be any integer then we can let

k ℤ = {k·x | x ∈ ℤ}.

The vertical line is read "for which." Thus, k ℤ is the set of "all numbers which can be expressed as k·x for which x is an integer." In other words, k ℤ is the set of all multiples of k. It is clear that k ℤ is a group under addition, since the difference of two multiples of k gives another multiple of k.

One of the main tools we will use to find subgroups of a group is the intersection. Given two subsets H and K of G, the Sage command Intersection finds the set of elements that are in both subsets, denoted H ∩ K. For example, if we are given two sets

In [0]:

H = [e, b, b^2]
K = [e, a]

then the Sage command

In [0]:

Intersection(H, K)

finds the set of all elements in common with H and K. Note that sets are entered in Sage using square brackets, even though they are often displayed using curly braces. (Technically, using square brackets produce a list of elements, which acts similar to a set. But the Sage routines know to treat a list as if it were a set.) Moreover, we can consider taking the intersection of a collection of many sets. If we let

In [0]:

L = [[e, a, b], [e, a*b, b], [e, a, b, b^2]]

then L represents a "set of sets." We can take the intersection of all of the sets in this collection with the command

In [0]:

Intersection(L)

The mathematical notation for this intersection is

∩	H.
H ∈ L

PROPOSITION 2.3
Given a group G and a non-empty collection of subgroups, denoted by L, then the intersection of all of the subgroups in the collection

H^* =	∩	H
	H ∈ L

is a subgroup of G.

Click here for the proof.

This proposition provides us with a general method of producing the subgroups of a group G. Let S be any subset of G. We can consider the collection of all subgroups of G which contain the set S, denoted by L.

DEFINITION 2.4
Given a subset S of a group G, we define the subgroup generated by S to be

[S] =	∩	H,
	H ∈ L

where L denotes the collection of subgroups of G that contains the set S.

By Proposition 2.3, this a subgroup of G. (The collection L is non-empty since it contains G.) By the way that the collection was defined, [S] contains S.

Actually, [S] is the smallest subgroup of G that contains S. For if H is a subgroup of G containing S, then H ∈ L, so that [S] ⊆ H.

We can define [S] in another way. It is clear that [S] contains all of the products of the form

(*)

x₁·x₂·x₃· ··· ·x_n,

where either x_k ∈ S or x_k^-1 ∈ S, (1 ≤ k ≤ n).

Notice that the set of all these products forms a subgroup H of G, and this subgroup contains S. Thus, [S] ⊆ H. But any element of the form (*) must be in [S]. Thus we also have H ⊆ [S]. Therefore H = [S]. In other words, [S] is the subgroup of G consisting of all products of the form (*).

In fact, the Sage command Group finds [S] for any set S. If S is a set of generators of the group G, then [S] = G, so we produced the entire group with the command Group(S). Yet for other sets, we can use the Group command to find the subgroups of a given group.

For example, consider the group S₃:

In [0]:

InitGroup("e")
AddGroupVar("a","b")
Define(a^2,e)
Define(b^3,e)
Define(b*a,a*b^2)
ListGroup()

In [0]:

SetReducedMult()

Now we can try out the group command to find [S] for different sets S. For example, what if S = {b}? Try it out for yourself:

In [0]:

Group(b)

This gives us the subgroup of order 3 that we saw before. What if S is the set {b, a·b}?

In [0]:

Group(b, a*b)

Had we not used the SetReducedMult command, the elements would have appeared in unusual combinations, yet we could still see that we had all 6 elements. With SetReducedMult, we get the same result as

In [0]:

Group(a, b)

The elements will not appear in their standard form. However, we see that we have 6 elements, so this apparently gives us the whole group. So {b, a·b} is also a set of generators for the group.

EXPERIMENT:
By using the Group command, find all of the subgroups of G. How many are there?

Let's look at a larger group. We found the octahedral group had order 24. Recall that the group was entered with the following Sage commands.

In [0]:

InitGroup("e")
AddGroupVar("a","b","c")
Define(a^2, e)
Define(b^3, e)
Define(c^4, e)
Define(b*a, a*b^2)
Define(c*a, a*b*c)
Define(c*b, a*c^2)
G = ListGroup(); G

In [0]:

SetReducedMult()

For any set S we can find the subgroup [S] by typing G = Group(S)

For example, suppose that the S is the single element {c}. We would type

In [0]:

Group(c)

and find we have a subgroup of order 4.

We can try other combinations of elements. For example, S = {b, c}:

In [0]:

Group(b, c)

This appears as big as the whole group. Let's double check:

In [0]:

len(_)

Since the size of this subgroup is 24 it must be the entire group. This means that the group can be generated with just two of the elements.

Why then did we use three elements to define the group originally? It turns out to be more efficient to define the group in Sage using three elements rather than two! Besides, it is much easier to put the octahedron back into its original position when one can flip the whole thing over.

Here is another subgroup:

In [0]:

Group(a, b)

Wait! This looks familiar. Where have we seen this before?

Look back at the definition of S₃. We had a and b as the generators, and we even had a² = e, b³ = e, and b·a = a·b². But these rules are all true of this subgroup of the octahedral group. Therefore, these are the same groups. We have found a copy of S₃ inside of the octahedral group.

Recall that we defined a group to be cyclic if there was one element in the group that generates the entire group. We also found that the element which generated the group was not unique. We called all such elements generators of the group.

Let us now consider just the cyclic subgroups of a group G. Notice that if we pick any element x of G, then [{x}] will always be a cyclic subgroup of G. This subgroup is usually denoted by [x].

EXAMPLE:
Find all of the cyclic subgroups of S₃.

The process of finding all of the cyclic subgroups is similar to finding the generators of a group. For each element, we consider raising that element to higher and higher powers until we produce the identity element.

(e)² = e.
(a)² = e.
(b)² = b²,	(b)³ = e.
(a·b)² = e.
(b²)² = b,	(b²)³ = e.
(a·b²)² = e.

Thus, there are 5 cyclic subgroups, {e}, {e, a}, {e, b, b²}, {e, a·b}, and {e, a·b²}. Notice that none of the elements were generators, so the group itself is not cyclic.

The easiest way to keep track of the cyclic subgroups is to note the size of the subgroup generated by each element.

DEFINITION 2.5
Let G be a group and let x be an element in G, We define the order of x to be |[x]|. That is, if [x] is finite, the order of x is the number of elements in [x]. If [x] is an infinite group we define the order of x to be infinity.

For all of the examples we have seen in computing [x], the power of the element x eventually reached the identity element, indicating that we have finished finding the cyclic subgroup. Here is a proof that shows this will always happen for a finite subgroup.

PROPOSITION 2.4
Suppose that the element x has finite order n. Then n is the smallest positive integer such that xⁿ = e. Furthermore,

[x] = {e, x, x², x³, …, xⁿ⁻¹}.

Click here for the proof.

EXAMPLE:
Find the cyclic subgroups of the group Z₁₅^* = {1, 2, 4, 7, 8, 11, 13, 14}, showing the orders of the elements.

We compute powers of each element until we reach the identity.

1² = 1.
2² = 4,	2³ = 8,	2⁴ = 1.
4² = 1.
7² = 4,	7³ = 13,	2⁴ = 1.
8² = 4,	8³ = 2,	8⁴ = 1.
11² = 1.
13² = 4,	13³ = 7,	13⁴ = 1.
14² = 1.

Thus, we see that the cyclic subgroups are [1] = {1}, [2] = [8] = {1,2,4,8}, [4] = {1, 4}, [7] = [13] = {1,4,7,13}, [11] = {1, 11}, [14] = {1, 14}. We also see that 1 has order 1, the elements 4, 11, and 14 have order 2, and the elements 2, 7, 8, and 13 have order 4. Note that this group lacks a generator.

We can make a similar observation if we have an infinite cyclic subgroup.

PROPOSITION 2.5
Suppose that x has infinite order. Then xⁿ is not the identity element for all nonzero integers n. Furthermore,

[x] = {…, x^-3, x^-2, x^-1, x⁰ = e, x¹, x², x³, …},

where the powers of x are all distinct.

Click here for the proof.

Even though the group in Proposition 2.5 is infinite, we can still define it in Sage. In fact, we defined an infinite group in the process of defining all of the other groups. If we have x as the generator of an infinite group, then the group is defined by the following:

In [0]:

InitGroup("e")
AddGroupVar("x")

At this point, we have an infinite group defined.

In [0]:

x^4 * x^-7

In [0]:

Order(x)

Granted, we cannot display all of the elements as we did for other groups (Group(x) would require interupting Sage), but we can still multiply elements of this group.

Because of Propositions 2.4 and 2.5, we know something about all cyclic groups. Any cyclic group G is either a finite group

G = { e = x⁰, x¹, x², x³, … , x^n-1}

of order n, or is an infinite group

G = {…, x^-3, x^-2, x^-1, x⁰ = e, x¹, x², x³, …}

where all powers of x are distinct.

Note that in the first case, G closely resembles Z_n. In the second case, G closely resembles ℤ. From this, we can quickly determine the nature of a subgroup of a cyclic group.

PROPOSITION 2.6
A subgroup of a cyclic group must be cyclic.

Click here for the proof.

EXAMPLE:
Find all the subgroups of the group ℤ.

Since ℤ is cyclic, we know that all subgroups are cyclic, hence can be expresses as [k] for some integer k. But [k] would be the multiples of k,

[k] = { k·x | x ∈ ℤ}.

We will denote the subgroup of the multiples of k by k ℤ. Note that 0 ℤ = {0}, and 1 ℤ = ℤ, so even the trivial subgroups are of this form.

Finding all of the subgroups of a non-cyclic group is trickier, since we have to consider subgroups generated by two or more elements. Sage can speed up the process.

EXAMPLE:
Find all of the subgroups of the group S₃.

We found all of the cyclic subgroups in a previous example: {e}, {e, a}, {e, b, b²}, {e, a·b}, and {e, a·b²}. Note that any subgroup containing b must also contain b², and vice-versa. Also all subgroups will contain e. So to find subgroups that require two elements, we have 6 combinations to try:

In [0]:

InitGroup("e")
AddGroupVar("a", "b")
Define(a^2, e)
Define(b^3, e)
Define(b*a, a*b^2)
SetReducedMult()

In [0]:

Group(a, b)

In [0]:

Group(a, a*b)

In [0]:

Group(a, a*b^2)

In [0]:

Group(b, a*b)

In [0]:

Group(b, a*b^2)

In [0]:

Group(a*b, a*b^2)

In each case, we produced the entire group. This shows that the only non-cyclic subgroup of S₃ is S₃ itself. Thus, we have found a total of 6 subgroups of S₃.

EXAMPLE:
Find the orders of the elements of the octahedral group.

If we reload the octahedral group,

In [0]:

InitGroup("e")
AddGroupVar("a", "b", "c")
Define(a^2, e); Define(b^3, e); Define(c^4, e)
Define(b*a, a*b^2); Define(c*a, a*b*c); Define(c*b, a*c^2)
G = ListGroup(); G

we can use Sage to quickly find the order of any element in the group. To find the order of the element b·c, we first find the subgroup [b·c].

In [0]:

Group(b*c)

This gives us the subgroup generated by the element b·c. We can observe the length of this to be 4 directly, or we can use Sage's len command:

In [0]:

len(_)

The Sage command Order combines these two operations into one. For example, to find the order of a·c, we type

In [0]:

Order(a*c)

EXPERIMENT:
Try replacing the "a*c" with other elements of the group. What do you observe about the orders of the elements?

There is a trick for finding the orders of all of the elements of the group at the same time.

In [0]:

[ Order(x) for x in G ]

Every element of this group besides the identity has order 2, 3, or 4. There is a geometrical reason for this: every element represents a rotation of either ±90°, ±120°, or 180°. (See Problem 7 from §2.3.)

Let us now consider the orders of the elements of a cyclic group. Consider, for example, the group Z₁₂.

In [0]:

G = ZGroup(12); G

We can find the orders of all of the elements in the group G using the same technique.

In [0]:

[ Order(x) for x in G ]

This tells us that there is one element of order 1, one element of order 2, 2 elements of order 3, 2 elements of order 4, 2 elements of order 6, and finally 4 elements of order 12.

It is apparent that finding the number of elements of order k involve finding the number of solutions to the equation x^k = e. To help us find the number of solutions for a cyclic group, let us first prove the following proposition about modular multiplication.

PROPOSITION 2.7
Let n and k be two positive integers. Then

x·k ≡ 0 (mod n)

if and only if

x =	a·n
	gcd(n, k)

for some integer a.

Click here for the proof.

We can now find the number of elements in a cyclic group that satisfies the equation x^k = e.

COROLLARY 2.1
Let G be a cyclic group of order n. Then there are precisely gcd(n, k) elements of G such that x^k = e.

Click here for the proof.

EXPERIMENT:
Use Sage to find the number of solutions to x⁸ = 0 in Z₁₂. Does this result agree with Corollary 2.1?

Finding the number of solutions to the equation x^k = e in a group will become important as we classify the different groups. We will give a notation to this count.

DEFINITION 2.6
Let G be a group, and k a positive integer. Then the number of elements of G for which x^k = e is called the k^th root count of G, and is denoted by

R_k(G) = ⎜{x ∈ G | x^k = e}⎟.

Corollary 2.1 can now be expressed in the new notation. If G is a cyclic group, then

R_k(G) = gcd(|G|, k).

Sage has a command RootCount(G, k) that will compute R_k(G). For example, we can redo the last experiment with the commands:

In [0]:

G = ZGroup(12)

In [0]:

RootCount(G, 8)

Now let's look at a more complicated group. You probably have heard of the infamous Rubik's Cube^©. Rubik also came out with a number of other puzzles, one of which is called the Pyraminx™. The Pyraminx™ consists of a triangular pyramid, with each of the four triangular sides partitioned into nine smaller triangles. The four "tips" can rotate, but this does not affect the puzzle. To simplify the picture we can chop off the tips of the pyramid. Execute the following command to show a picture of the puzzle with the tips cut off:

In [0]:

InitPuzzle()

Now the four corners of this puzzle can rotate, moving some of the middle pieces in the process. For example, the front corner can rotate clockwise 120° by the command:

In [0]:

RotatePuzzle(f)

We can rotate the back corner clockwise with the command:

In [0]:

RotatePuzzle(b)

At this point, we see the advantage of chopping off the four tips of the pyramid: this allows us to peer inside of the puzzle to see what is on the back face!

The left and right corners can be rotated using the commands

In [0]:

RotatePuzzle(l)

In [0]:

RotatePuzzle(r)

Now we have really scrambled the puzzle! Not to fear––we can put the puzzle back into its original form with the command

In [0]:

InitPuzzle()

That is sure much easier than taking the puzzle apart and putting it back together again!

The set of all actions on the puzzle forms a group, called the Pyraminx™ group. This group is generated by the elements {t, b, r, l}. However, this group has over 900,000 elements! Thus, it is not such a good idea to have Sage list all elements of the group. It really wouldn't tell us much, and would probably run us out of memory.

We can determine information about the Pyraminx™ group by working with the puzzle. For example, we know that the elements r, l, t and b each have order 3. But what about the element b·f? Try this out yourself:

In [0]:

RotatePuzzle(b,f)

Notice that we have the animation feature here. How many times must this statement be executed to get back to the original state? This will give us the order of the element b·f. So we have a subgroup, namely [b·f] of that order.

EXPERIMENT:
Using this method of repeating the operation, find the orders of the following elements:

b·f·r·f·f
f·b·r

One can see quite a variety of possibilities for the order of an element in this group. Can you find an element with an order larger that the last example? Perhaps we need to study the puzzle further to answer that question. When we know more about groups in general we will not only be able to answer this question, but also build up some tools that will help us to solve the puzzle.

Proofs:

Proof of Proposition 2.1:

Suppose that g is a generator of Z_n. Then 1 is able to be expressed as a power of g, so we have that

g^v = 1 in Z_n

for some v. Since the group action of Z_n is addition, raising to a power is equivalent to repeated addition, or standard multiplication.

Thus, we have that

g v ≡ 1 (mod n).

By Proposition 1.7, there is such a v if, and only if, g is coprime to n.

Now suppose that g is coprime to n. By Proposition 1.7, there is a v such that

g v ≡ 1 (mod n), hence g^v = 1 in Z_n.

So 1 can be expressed as a power of g. But 1 is a generator of Z_n, and so every element of Z_n can be expressed as a power of 1, say 1^w. Then that element can be written as g^{(v w)} = (g^v)^w = 1^w. So every element can be expressed as a power of g, hence g is a generator of Z_n.

Return to text

Proof of Theorem 2.1:

To begin, let us show that if p is a prime, then ϕ(p^r) = (p − 1)p^r⁻¹.

Note that the only numbers that are not coprime to p^r will be multiples of p. So of the numbers between 1 and p^r, exactly 1/p of them will be multiples of p. The remaining (1 − 1/p)p^r will be coprime, and this can be simplified to (p − 1)p^r⁻¹.

Next we want to show that if n and m are coprime, then ϕ(n m) = ϕ(n) ϕ(m). Let A denote the set of numbers that are less than n, but coprime to n. Let B denote the set of numbers that are less than m, but coprime to m.

Then for any number x coprime to n·m, x mod n must be in the set A, while x mod m must be in B. Yet for every a in A and b in B, there is, by the Chinese remainder theorem, a unique number less than n m that is equalivalent to a (mod n) and b (mod m). This number will be coprime to both n and m, and hence will be coprime to n m.

Therefore, we have a one-to-one correspondence between ordered pairs (a, b), where a ∈ A, and b ∈ B, and numbers coprime to n m. Thus, we have

ϕ(n m) = ϕ(n)·ϕ(m).

Finally, we can combine these results together. By simply noting that if

n = p₁^r¹ · p₂^r² · p₃^r³ ··· p_k^rₖ,

then p₁^r¹, p₂^r², p₃^r³, …, p_k^rₖ will all be coprime. Hence, we can find ϕ for each of these terms, and multiply them together, giving us our formula.

Return to text

Proof of Proposition 2.2:

First of all, we need to see that if H is a subgroup, then x·y^-1 is in H whenever x and y are in H. By property (3), y^-1 is in H, and so by property (1), x·y^-1 is in H.

Conversely, let us suppose that H ⊆ G, H ≠ {}, and whenever x, y ∈ H, then x·y^-1 ∈ H. We need to see that properties (1) through (3) are satisfied.

Since H is not the empty set, there is an element x in H, and so x·x^-1 = e is in H. Thus property (2) holds.

Next, we have that if y is in H, then e·y^-1 = y^-1 is in H, and so property (3) holds.

Finally, if x and y are in H, then y^-1 is in H, and so x·(y^-1)^-1 = x·y is in H. Thus, property (1) holds.

Return to text

Proof of Proposition 2.3:

First of, note that H is not the empty set, since the identity element is in each H in the collection. We now can apply Proposition 2.2. Let x and y be two elements of H. Then for every H ∈ L we have x, y ∈ H. Since H is a subgroup of G, we have x·y^-1 ∈ H. Therefore, x·y^-1 is in H, and so H is a subgroup of G.

Return to text

Proof of Proposition 2.4:

Since [x] is finite, not all of the elements {x⁰, x¹, x², x³, x⁴, … } can be distinct. Suppose that x^a = x^b for two integers a and b, with b > a. Then x⁽^b⁻^a⁾ = e and (b − a) > 0. So there exists a positive integer c such that x^c = e. We can let n be the smallest such integer. We want to prove that

[x] = {e = x⁰, x¹, x², x³, …, xⁿ⁻¹}

with these elements distinct. Indeed, if

x^a = x^b with 0 ≤ a < b ≤ n − 1,

then x^b−a = e, and 0 < b − a < n, which contradicts the definition of n. Therefore, the elements in

{ e = x⁰, x¹, x², x³, …, xⁿ⁻¹}

are all distinct.

Finally, we need to show that if y is in [x], then there exists a r such that

x^r = y, with 0 ≤ r ≤ n − 1.

But y = x^k for some k ∈ ℤ. We can define r = k mod n. Then 0 ≤ r ≤ n − 1, and furthermore, there is an integer q such that k − r = n q. Thus,

y = x^k = x^{(n q + r)} = (xⁿ)^q·x^r = e^q·x^r = x^r.

So every element of [x] is of the form x^r, with 0 ≤ r ≤ n − 1.

Return to text

Proof of Proposition 2.5:

Suppose that xⁿ = e for some nonzero n. It suffices to consider the case n > 0, for if xⁿ = e, then x⁻ⁿ = e.

By exactly the same reasoning as was used to prove Proposition 2.4, we see that

[x] = {e = x⁰, x¹, x², x³, …, xⁿ⁻¹}.

But this contradicts the fact that [x] was infinite. Therefore, xⁿ = e only if n = 0.

Moreover, if x^a = x^b, then x^b⁻^a = e, and so b − a = 0 by what we have just proved. Thus, the powers of x are all distinct.

Return to text

Proof of Proposition 2.6:

Let g be a generator of the cyclic group G. The trivial subgroup {e} is considered cyclic, so let S be a non-trivial subgroup. Then every element of S can be written as gⁱ for some i. Since both gⁱ and g⁻ⁱ would then be in S, we see that gⁱ is in S for some positive i. Let k be the smallest positive integer such that g^k is in S. Then g⁽^mk⁾ is in S for all integers m.

If there were some other element in S not in [g^k], then this element is g^y for some integer y. Then y = q k + r for some 0 < r < k. Then g^r = g^y·(g^k)⁻^q ∈ S, but we chose k to be the smallest positive integer for which g^k ∈ S. Thus, S = [g^k], and so S is cyclic.

Return to text

Proof of Proposition 2.7:

First of all, notice that if

x =	a·n	,
	gcd(n, k)

then

x·k =	a·n·k	= a·n·	k	,
	gcd(n, k)		gcd(n, k)

and since gcd(n, k) is a divisor of k, we see that x · k is a multiple of n. Thus,

x k ≡ 0 (mod n).

Now suppose that x·k is a multiple of n. We want to show that

a =	x·gcd(n, k)
	n

is in fact an integer. By the greatest common divisor theorem (1.2), there exist integers u and v such that gcd(n, k) = u·n + v·k. Then

a =	x·(u·n + v·k)	= x·u +	x·k·v	.
	n		n

Since x · k is a multiple of n, we see that a is an integer. Thus,

x =	a·n
	gcd(n, k)

for some integer a.

Return to text

Proof of Corollary 2.1:

Let g be a generator of G, and let x = g^y be an element of G. Then x^k = (g^y)^k = g^y^·^k, which is equal to the identity if and only if

y·k ≡ 0 (mod n).

By Proposition 2.7, this is true if and only if

y =	a·n
	gcd(n, k)

for some integer a. Hence, the number of possible values of y between 0 and n − 1 for which g^y·k = e is

n	= gcd(n, k).
n / gcd(n, k)

Each such value of y between 0 and n − 1 produces a different solution x = g^y, so there are exactly gcd(n, k) solutions.

Return to text

Sage Interactive Problems

§2.1 #23)
Use Sage's circle graph to find all of the generators of the group Z₂₁.

§2.1 #24)
Use Sage to see if there an element of Z₂₅^* that generates Z₂₅^*. If so, how many such elements are there?

§2.1 #25)
By using Sage's Generators() command, determine whether Z_n^* is cyclic for n = 9, 27, 81, 243, 5, 25, 125. Make a conjecture about when Z_n^* is cyclic if n is a power of an odd prime.

§2.1 #26)
By using Sage's Generators() command, determine whether Z_n^* is cyclic for n = 18, 54, 162, 486, 50, 250, 98, 686. Make a conjecture about when Z_n^* is cyclic if n is twice the power of an odd prime.

§2.1 #27)
By using Sage's Generators() command, see if you can find an n for which Z_n^* is cyclic, and n doesn't fit into the categories of Problems 25 or 26.

§2.2 #18)
Use Sage to define a group that has two elements, a and b, for which a⁵ = b⁴ =e, and b · a = a² · b. How many elements does this group have?

§2.2 #19)
Find all of the generators of the group Z₂₄. Then have Sage construct a multiplication table for the group Z₂₄^*.

§2.2 #20)
Since the elements b and c could generate the octahedral group, define this group in Sage using only b and c.

Hint: Besides b³ = e and c⁴ = e, Sage will need one more equation. What is the order of b²·c?

§2.2 #21)
Define a group in Sage that is generated by two elements a and b, with a³ = b⁵ = (a·b)² = e. How big is the group?

§2.3 #21)
Use Problem 18 from §2.2 to find the subgroup generated by the elements a and b². How many elements does this have?

§2.3 #22)
Use Sage to investigate the relationship between the order of an element, and the order of its inverse. First we pick a large group:

In [0]:

G = ZStar(360)
len(G)

The following command selects a random element from the group.

In [0]:

a = G[randint(1, len(G)) - 1]; a

Then compare the results of the following operations.

In [0]:

Order(a)

In [0]:

Order(a^-1)

What do you observe? Try this with several random elements. Can you make a conjecture?

§2.3 #23)
Repeat Problem 22, only using the octahedral group.

In [0]:

InitGroup("e")
AddGroupVar("a", "b", "c")
Define(a^2, e); Define(b^3, e); Define(c^4, e)
Define(b*a, a*b^2); Define(c*a, a*b*c); Define(c*b, a*c^2)
G = ListGroup()

§2.3 #24)
Use Sage to find the order of the elements b·f, b·f·r·f·f and f·b·r in the Pyramix™ group.

§2.3 #25)
Can you use Sage to find an element of the Pyramix™ group that has order 30?
(Hint: Exactly five of the six edges must be moved out of place. The sixth edge must flip as well.)

Generators of Groups

Defining Finite Groups in Sage

Subgroups

Proofs:

Sage Interactive Problems

Product

Resources

Company

n	ϕ(n)	n	ϕ(n)	n	ϕ(n)
1	1	13	12	25	20
2	1	14	6	26	12
3	2	15	8	27	18
4	2	16	8	28	12
5	4	17	16	29	28
6	2	18	6	30	8
7	6	19	18	31	30
8	4	20	8	32	16
9	6	21	12	33	20
10	4	22	10	34	16
11	10	23	22	35	24
12	4	24	8	36	12

n	ϕ(n)	n	ϕ(n)	n	ϕ(n)
1	1	13	12	25	20
2	1	14	6	26	12
3	2	15	8	27	18
4	2	16	8	28	12
5	4	17	16	29	28
6	2	18	6	30	8
7	6	19	18	31	30
8	4	20	8	32	16
9	6	21	12	33	20
10	4	22	10	34	16
11	10	23	22	35	24
12	4	24	8	36	12

n	ϕ(n)	n	ϕ(n)	n	ϕ(n)
1	1	13	12	25	20
2	1	14	6	26	12
3	2	15	8	27	18
4	2	16	8	28	12
5	4	17	16	29	28
6	2	18	6	30	8
7	6	19	18	31	30
8	4	20	8	32	16
9	6	21	12	33	20
10	4	22	10	34	16
11	10	23	22	35	24
12	4	24	8	36	12