group03.ipynb

Kernel: SageMath (stable)

[r

Abstract Algebra: An Interactive Approach, 2e

©2015 This notebook is provided with the textbook, "Abstract Algebra: An Interactive Approach, 2nd Ed." by William Paulsen. Users of this notebook are encouraged to buy the textbook.

Chapter 3
Patterns Within the Cosets of Groups

Initialization: This cell MUST be evaluated first:

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

Left and Right Cosets
How to Write a Secret Message
Normal Subgroups
Quotient Groups
Sage Interactive Problems

Left and Right Cosets

We introduced subgroups in the last chapter, but left many questions unanswered. For example, is there any relationship between the size of the group and the size of one of its subgroups?

In this chapter we will introduce the tool of cosets to determine many of the properties of subgroups, including what possible sizes the subgroups could be. To understand cosets, let us begin by looking at some cases where an element does not generate the group, in hopes of finding some patterns in the circle graphs.

Let us look at the example Z₁₀. The generaters were 1, 3, 7, and 9, so let us pick an elements besides these, such as 4. Here is the circle graph of Add(4):

Z = ZGroup(10)
CircleGraph(Z, Add(4))

We see that 4 is not a generator, for there are arrows of two colors. The red arrows connect the points {0, 2, 4, 6, 8}, while the green arrows connect the points {1, 3, 5, 7, 9}. Thus, the group is partitioned into two sets, and no arrow connects these two.

We can immediately see some patterns in the way that Z₁₀ is partitioned. One of the two sets, {0, 2, 4, 6, 8} is actually a subgroup of Z₁₀, and is the subgroup generated by the element 4. We can check this with the command:

Group(Z[4])

The other set is obtained by adding 1 to each element of this subgroup. Let us look at another example to see if this pattern continues. Here is the circle graph of Add(5):

CircleGraph(Z, Add(5))

Here we have five different colored arrows, so the group is partitioned into five sets: {0, 5}, {1, 6}, {2, 7}, {3, 8}, and {4, 9}. One of these sets is the subgroup generated by the element 5:

Group(Z[5])

The others are obtained by adding some constant to every element in this subgroup.

EXPERIMENT:
Replace the Add(5) in the above circle graph with either Add(0), Add(2), Add(6), or Add(8). (These are the other elements of the group which are not generators.) Do we obtain any new partitions of the group?

By doing this experiment, you probable noticed that the partition of the group depends only on the subgroup generated by the element. Of course this is an abelian group, so it is natural to ask if these patterns we have noticed carry over to non-abelian groups. Let us look at Terry's group.

G = InitTerry(); G

This group does not have any generators, so any element of the group will produce a partition of the group. Consider the circle graph that sends every element to that element multiplied by Spin.

Because this group is non-abelian, we have a choice as to how to do this. Do we multiply the element x to the left of Spin, giving x·Spin, or do we multiply on the right, giving Spin·x? These two options yield different circle graphs. The former is obtained by the command

CircleGraph(G, LeftMult(Spin))

The latter is given by the command

CircleGraph(G, RightMult(Spin))

Notice that these two circle graphs produce different partitions of the group! The first gives the partition {Stay, Spin}, {RotRt, FlipLft}, and {RotLft, FlipRt}. The second circle graph gives us the partition {Stay, Spin}, {RotRt, FlipRt}, and {RotLft, FlipLft}. In both cases, one of the sets in the partition is the subgroup generated by Spin:

H = Group(Spin); H

We still see some patterns the two partitions. In the first case every set in the partition is obtained by multiplying an element such as RotRt or RotLft by each element of the subgroup H. In the second partition, every set is obtained by multiplying each element of the subgroup H by an element such as RotRt or RotLft.

EXPERIMENT:
Change the element Spin in the last two circle graphs to the other elements of Terry's group. Do all partitions follow the pattern mentioned above?

To define these partitions mathematically, we will use the pattern that we have been observing: that every set in the partition is obtained by multiplying every element of a subgroup H by an element x, either on the right or on the left.

DEFINITION 3.1
Let G be a group, and let H be a subgroup of G. If x is an element of G, we define the set

x H={ x·y | y ∈ H }.

The set x H is called a left coset of H.

We could just have easily considered multiplication the other way. This would give us the set

H x = { y·x | y ∈ H }

which is called a right coset of H.

These definitions are very easy to work with mathematically, but it is not apparent that the right cosets and the left cosets form the partitions of the group that we have been observing. This has to be proved!

Sage has been programed to mimic this notation. Thus, we can form right cosets by multiplying each element in H by an element in the group, say RotRt.

H = Group(Spin); H

H * RotRt

Notice that Sage multiplies every element in the set H by RotRt. In a sense, it distributes RotRt throughout the set.

We can find a left coset with respect to H in the same way:

RotRt * H

The left and right cosets are different, as we observed in the circle graphs.

We will denote the set of all left cosets of H by G/H, and will denote the set of all right cosets of H by H<em>G. Albeit the notation is strange, but it reminds us which side the element of G is multiplied on.

Sage can help us to find all left and right cosets of G with respect to H. The commands are

LftCoset(G, H)

RtCoset(G, H)

Note that in both commands, the first argument is the group or list of elements in the group, and the second argument is the subgroup. These give us a list of cosets. (Since each coset is displayed as a list of elements we find ourselves with a "list of lists.") These are exactly the partitions we observed in the circle graphs of LeftMult(Spin) and RightMult(Spin). In fact, we begin to see some patterns in the cosets. First of all, all of the cosets are the same size. Also, every element of the group appears once, and only once, in each of the two coset lists. However, we have yet to prove these patterns persist. The next two lemmas do this for us. We begin by showing that all cosets of H are of the same length.

LEMMA 3.1
Let G be a group and H be a finite subgroup of G. Then all left and right cosets of H contain |H| elements.

Click here for the proof.

Next we must show that every element of G is in exactly one left coset and one right coset. This can be worded as follows:

LEMMA 3.2
If two left or two right cosets have any elements in common, they are in fact the same coset. That is,

H x ∩ H y ≠ { } implies that H x = H y,

and

x H ∩ y H ≠ { } implies that x H = y H.

Click here for the proof.

EXAMPLE:
Find all of the left and right cosets of the subgroup {1, 11} of the group Z₁₅^*.

Since Z₁₅^* is abelian, the left and right cosets are the same. By Lemmas 3.1 and 3.2, the cosets will be disjoint, and all have 2 elements. One of the cosets will be the subgroup {1, 11}. We pick an element not in the subgroup, say 2, and multiply each element of the subgroup by 2, producing the coset {2, 7}. We pick another element not yet in a coset, and repeat the process. To find the coset containing 4, we multiply the subgroup by 4, to product the coset {4, 14}. At this point, only 2 elements are unaccounted for, so they must be in their own coset, {8, 13}. So the list of cosets are {{1, 11}, {2, 7}, {4, 14}, {8, 13}}.

These last two proofs were called lemmas instead of propositions, since they lead to an important theorem.

THEOREM 3.1: Lagrange's Theorem
Let G be a finite group, and H a subgroup of G. Then the order of H divides the order of G. That is, |G| = k·|H| for some positive integer k.

Click here for the proof.

Lagrange's theorem has many important consequences. We call the applications of an important theorem Corollaries.

COROLLARY 3.1
Let G be a finite group, and let x be an element of G. Then the order of x divides |G|.

Click here for the proof.

COROLLARY 3.2
Let G be a finite group of order n and let x be an element of G. Then xⁿ = e.

Click here for the proof.

COROLLARY 3.3
A group of prime order is cyclic.

Click here for the proof.

COROLLARY 3.4
Let n be a positive integer, and x a number coprime to n. Then

x^ϕ(n) ≡ 1 (mod n)

where ϕ(n) is Euler's totient function.

Click here for the proof.

When n = p is prime then ϕ(p) = p − 1, and Corollary 3.4 says that

x^p−1 ≡ 1 (mod p).

This result is known as Fermat's little theorem. Fermat had proved this without the help of group theory, which was a real challenge! Yet this result becomes a trivial consequence of a larger theorem when we look at the supporting group structure.

DEFINITION 3.2
If H is a subgroup of G,we can define the index of H in G, denoted [G:H], to be the number of right cosets in H<em>G. Of course this is the same as the number of left cosets in G/H.

Notice that when G is a finite group we have by the argument in Lagrange's theorem (3.1) that |G| = |H|·[G:H].

How To Write a Secret Message

In this section, we will learn of one important application of Lagrange's Theorem. We will learn how to write a message that no one can read except for the person to whom the message is sent, even if everyone in the world knows the code! This sounds like an impossibility, but we will see that it can be done with group theory. This code has applications in internet security and secure data transmissions.

EXAMPLE
To introduce this code, we begin by considering the group Z₃₃^*, formed by all of the generators of Z₃₃. The order of this group is ϕ(33). We can either look at the table in the previous notebook, or use Sage's built in EulerPhi function

EulerPhi(33)

to see that there are 20 elements. It isn't hard to determine the generators of Z₃₃:

{1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32}.

This is the set of elements in Z₃₃^*.

G = ZStar(33); G

Let us consider making a circle graph that maps each element to that element raised to a certain power. For example, we can map each element to its square by the command

CircleGraph(G, Pow(2))

This yields a rather perplexing graph, since some elements have many arrows point to them, for example 4 is obtained by squaring either 2, 13, 20, or 31 in this group. Those elements that have "square roots" seem to have four of them, while the majority of the elements do not have "square roots" at all. Of course a "square root of x" is defined as any element whose square is x. Although there are some other interesting patterns to explore here, let us look at the circle graphs of different powers. This graph maps every element to its cube:

CircleGraph(G, Pow(3))

This graph has a very different behavior. No two arrows heads are at the same element, indicating that no two elements have the same cube. Also, every element has some arrow that points to it. Thus, we see from the figure that the cube function is both one-to-one and onto. Hence, every element has a unique cube root.

EXPERIMENT:
Form different circle graphs by replacing the 3 in the last graph with higher numbers. Look at all of the circle graphs from Pow(4) to Pow(21). In these 18 circle graphs, which ones form one-to-one and onto functions? Why does Pow(20) behave the way it does? (Hint: see Corollary 3.4.) Why does Pow(21) behave like Pow(1)?

Here is one explanation as to why x → x³ is one-to-one and onto. Let us plot both Pow(3) and Pow(7) on the same graph:

CircleGraph(G, Pow(3), Pow(7))

The green arrows representing Pow(7) go in the opposite direction as the red arrows representing Pow(3). This indicates that to take a cube root of a number modulo 33, we take its seventh power! This is because ϕ(33) = 20, so using Corollary 3.4,

(x³)⁷ = x²¹ = x²⁰·x = e·x = x.

Here we used the observation that Pow(21) behaved like Pow(1) because of Corollary 3.4. We say that the function Pow(7) is the inverse of the function Pow(3). The difference between this examples and the first example Pow(2) is that 3 is coprime to ϕ(33) = 20, whereas 2 is not. See if you can use this idea to prove the following generalization:

PROPOSITION 3.1
Suppose G is a finite group of order m, and that r is some integer which is coprime to m. Then the function f(x) = x^r is one-to-one and onto. In other words, we can always find the unique root of any element of G.

Click here for the proof.

EXAMPLE:
Let us try another experiment. Rather than using the elements in Z₃₃^*, suppose we considered all of the numbers from 0 to 32. This will no longer by a group, since we have included some non-invertable elements. But we can still take the cube of any number, and can still plot the circle graph. Here it is:

R = MultMod(33); R

CircleGraph(R, Pow(3))

This function is still one-to-one and onto, even with the extra elements. What about Pow(7)? Is this still the inverse of Pow(3) for this new set? Let's check by graphing both Pow(3) and Pow(7) on the same graph again:

CircleGraph(R, Pow(3), Pow(7))

We can see that Pow(7) is still the inverse of Pow(3), even with the extra elements. This will happen in general whenever n is a product of two distinct primes, as seen by the following proposition.

PROPOSITION 3.2
Suppose n is a product of two distinct primes and r·s ≡ 1 (mod ϕ(n)). Then for all values of x less then n,

(x^r)^s ≡ x (mod n).

Click here for the proof.

The function x → x³ is not only one-to-one and onto, but also mixes up most of the numbers 0 through 32 fairly well. This suggests an encryption scheme. For example, we could let

A = 1	J = 10	S = 19
B = 2	K = 11	T = 20
C = 3	L = 12	U = 21
D = 4	M = 13	V = 22
E = 5	N = 14	W = 23
F = 6	O = 15	X = 24
G = 7	P = 16	Y = 25
H = 8	Q = 17	Z = 26
I = 9	R = 18	Space = 0

Now any message can be converted to a sequence of numbers:

CAN YOU READ THIS

becomes

3, 1, 14, 0, 25, 15, 21, 0, 18, 5, 1, 4, 0, 20, 8, 9, 19

We replace each number with its cube, modulo 33. Using the above circle graph, we get

27, 1, 5, 0, 16, 9, 21, 0, 24, 26, 1, 31, 0, 14, 17, 3, 28

To decipher this, one would take the seventh power of each number in the sequence modulo 33, and convert back to letters in the alphabet. Voilà!

There are two main drawbacks with this "modulo 33" code. The first is that, for longer messages, the letter E which encodes to 26 would appear most frequently in the encoded string. Even someone who didn't know the code might deduce that 26 stands for E even if they didn't know anything about algebra.

The second problem is that anyone who knew how to encrypt the message could use Proposition 3.2 and the fact that Z₃₃ is of order 20 to come up with the inverse of 3 in Z₂₀ being 7, and thereby could decode the message. What we would like is a code in which anyone could encrypt a message, but only the person who originated the code could decipher.

We can solve both of these problems just by picking n to be a larger value! Rather than picking n = 33, suppose that n was the product of two very large prime numbers p and q, say 80 digits each. Then n would have about 160 digits! (We will not be able to draw circle graphs on this large of a group.) By the totient function theorem, ϕ(n) would be (p − 1)·(q − 1). Rather than picking r = 3, we would pick some large value of r which is coprime to (p − 1)·(q − 1). A four digit number would be sufficient. Our code will be

x → y = x^r mod n.

Even though r and n are large, this computation is a piece of cake for Sage.

We decode this by finding the inverse of r in the group Z_ϕ(n)^*, and call this s. In our modulo 33 code s = 7, but here s could be almost as large as n. By Proposition 3.2, we can decode the message by the operation

y → x = y^s mod n.

This operation "undoes" the encryption, since we know that

(x^r)^s ≡ x (mod n) if r·s ≡ 1 (mod ϕ(n)).

How does this solve both of the problems of the modulo 33 code? First of all, instead of encrypting a letter at a time, n is large enough for us to encrypt an entire line at a time. For example, the message

CAN YOU READ THIS

can be encrypted by the single number

0301140025152100180501040020080919.

Notice that every two digits of this number represent one letter, according to the same code we had before. This eliminates the problem of one number having a higher occurance frequency, as in the modulo 33 code.

The other problem with the modulo 33 code is that everyone who knew how to encrypt the message could also decode a message. Is the the case when n is large? In order to decode a message, one must know the value of s, which is given by the inverse of r (mod ϕ(n)). This is easy to do with Sage once ϕ(n) is known, but how difficult it is to find ϕ(n)! One needs to know the prime factorization of n, which would be about 160 digits long. In fact, adding two digits to p and q makes the factorization 10 times harder. So by making the prime numbers even larger, we can be assured that the factorization connot be done within one's lifetime. Thus, only the person who originated the prime numbers p and q could come up with the value of s.

This encyption scheme is called the RSA encyption, which is an abbreviation of Rivest-Shamir-Adleman, the three mathematicians who came up with this code. There are Sage routines set up in this notebook that allow us to experiment with RSA encyption.

EXAMPLE:
Suppose that a friend wishes to send a completely confidential message, but that all correspondance between you and your friend were being monitored.

The first step is for you to come up with 2 very large primes of 80 digits or more. Even though Sage cannot factor large numbers, it does have a secret way of testing whether a number is prime. The function

NextPrime(n)

uses this feature to find the next prime number after n. So by entering two large random numbers, Sage can find two large random primes. Say you pick p to be

p = NextPrime(12345678901234567890123456789012345678901234567890123456789012345678901234567890); p

and pick q to be

q = NextPrime(98765432109876543210987654321098765432109876543210987654321098765432109876543210); q

These numbers aren't too random, but they will do. The backslash in the output shows that the line is continued, so we have one large number. However, the backslash will not work on the input line. Note that clicking on the left side of the output toggles the format from a line that is broken to a single line with a scrollbar.

Sage uses a variation of the Agrawal, Kayal, and Saxena primality test to find the next prime number. This test can definitely determine whether a number is prime, in a time that is a polynomial function of the number of digits in p and q. Hence, we can quickly know for certain that the numbers p and q will be prime.

Next, multiply the two numbers together, and tell your friend the product n.

n = p*q; n

Also give your friend a 4 digit number r which happens to be coprime to both (p−1) and (q−1). Simply find a 4 digit prime which does not happen to be a factor of (p−1) and (q−1).

Here is a random (or maybe not so random) four digit prime number:

r = NextPrime(1234); r

Now check to make sure this is not a factor of (p−1) and (q−1):

gcd((p-1)*(q-1), r)

Since the gcd is 1, r is coprime to (p−1) and (q−1). Even if this communication is monitored, only the value of n, not the p and q which generated it, would be known to any spies.

Next tell your friend to convert the message to a number. There are routines in this notebook for converting messages numbers quickly. They are

MessageToNumber("Message")

and

NumberToMessage(Number)

Note we put the message in quotation marks. Therefore, we can find the number corresponding to "HERE IS A MESSAGE" by typing

x = MessageToNumber("HERE IS A MESSAGE"); x

We can then convert this back to a message with the command

NumberToMessage(x)

Encripting this messege is accomplished by raising x to the r^th power modulo n. This is done by the Sage command PowerMod. The format for this command is

PowerMod(a, b, n) = a^b mod n

It can compute such powers very quickly.

y = PowerMod(x, r, n); y

Suppose your friend has done this operation with a different message, giving you the answer

y = 695574051470244068706114266574256043827756065440747032387700788446830783525388331288538827113160595765080505966693143199918635215093570816224139063616551830794

How do you decode this message?

First, find the number s which is the inverse of r modulo (p−1)·(q−1). This is given by

s = PowerMod(r, -1, (p-1)*(q-1) ); s

This is the secret key to the code. Because the spies only know the values of n and r, there is no way for them to factor n to come up with p and q. So this value s will still be a secret.

Next, compute y^s mod n using the command

x = PowerMod(y, s, n); x

Finally, the command

NumberToMessage(x)

puts the message into readable form. With Sage, this code becomes easy to use!

There are many other applications to this code besides sending secret messages. For example, suppose to get an account at the Electronic Bank, you are asked to pick two large random prime numbers, p and q. The bank then gives you the account number [removed]n = p·q, and a number r, and publishes these. The bank then gives you the number s which will be the inverse of r in Z_ϕ(n)^*. Now you can use the number s to decode a message such as

y = MessageToNumber("Check 1034: Pay to the order of John Brown $43.50"); y

x = PowerMod(y, s, n); x

You can send this number to John Brown, along with your account number. Then he, his bank, and anyone else who needs to know, can verify what this says as follows:

y = PowerMod(x, r, n)

NumberToMessage(y)

What does this prove? The only person knowing the number s sent this message, which would be the owner of the account. The fact that the message was so encoded becomes a signature to the check. Using this method, one can send an "electronic check" (even through the e-mail) that is impossible to forge.

Normal Subgroups

When we defined left cosets and right cosets, we were in essence defining how we could take an element of a group G and multiply it with a subgroup of G. But this definition can apply to any subset of G. That is, if X is any subset of G, we can define

X u = { x·u | x ∈ X},
u X = { u·x | x ∈ X}.

We can also, using the same idea, multiply two subsets of G together.

DEFINITION 3.3
If X and Y are two subsets of a group G, we can define

X·Y = { x·y | x ∈ X and y ∈ Y}.

We find that {u}·X is the same thing as u X, so this definition is consistent with the previous definitions.

Since multiplication is associative, we also have

X·(Y·Z) = (X·Y)·Z.

This raises some interesting questions. If X and Y are subgroups of G, will X·Y be a subgroup? Suppose X and Y are cosets of G with respect to a subgroup H. Will X·Y be a coset of G?

EXAMPLE:
One way to answer these questions is to experiment! If we have two subsets of G, (which Sage represents as a list of elements in brackets), we can multiply the sets together using the command Mult(G, X, Y).

Let's pick a group large enough to see some patterns. Execute the following command to load the octahedral group.

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

Recall that this group has order 24. There are many subgroups in this group. Let us find a few.

H = Group(c); H

K = Group(b*c); K

L = Group(a*b*c*c); L

Unfortunately, these are not displayed in their standard form because SetReducedMult was not enabled. Alternatively, we can conform the list of elements to appear as they do in the group G by using the Conform command.

Conform(K,G)

Conform(L,G)

We can now explore what happens when we multiply two subgroups together.

Conform(H*K, G)

Looks like a lot of elements! Let's count them.

len(_)

So H·K has 16 elements. Apparently, each element of H, when multiplied by an element in K, produces a unique element.

Is H·K a subgroup of G? Lagrange's theorem (3.1) quickly tells us no! Since 16 does not divide 24, H·K is not a subgroup of G, in spite of the fact that H and K are.

EXPERIMENT:
Try working multiplying two other subgroups of G. Consider for example K·H, H·L, L·H, K·L, or L·K. Do any of these form subgroups of G?

EXAMPLE:
Suppose instead that X and Y are both cosets of G with respect to a subgroup H. We can let again let H be the group generated by the element c.

H = Group(c); H

Here are the right and left cosets:

RtCoset(G, H)

LftCoset(G, H)

As expected, the left and right cosets are different, since the group is not commutative. Let's pick two right cosets:

X = Conform(H*b, G); X

Y = Conform(H*a*c, G); Y

Now, let's see if the product gives us anything useful.

Conform(X * Y, G)

Let's find the length of this mess.

len(_)

Not only can this fail to be a subgroup, but this cannot be a coset of a subgroup. Do we have any better luck with left cosets? Let's try it.

Z = Conform(a*H, G); Z

W = Conform(b*H, G); W

Well, here goes nothing!

Conform(Z * W, G)

len(_)

That didn't seem to produce anything useful either. But before we give up completely, suppose we multiply a left coset by a right coset.

Conform(W * Y, G)

That looks more promising. In fact, this is a subgroup! Compare this with

Conform(Group(a*c^2),G)

to see that they are the same.

EXPERIMENT:
Try other combinations of a left coset times a right coset, such as Z·X, Z·Y, and W·X. How many elements do these have? Are any of them subgroups? Are any or them cosets of some subgroup?

This experiment indicates that there might be some promise in exploring the products of left cosets times right cosets. Let's try another example to see if we can determine a pattern.

EXAMPLE:
Enter in the group

M = Group(a*b^2*c, c^2); M

This is also a group of order 4. Let's find the right and left cosets of G with respect to this group.

RtCoset(G, M)

LftCoset(G, M)

There is more of a pattern in the cosets with this subgroup. Look carefully. The right and left cosets are the same!

This particular subgroup allows us to explore more patterns. Because any left coset is also a right coset, they are interchangeable. We saw before that a left coset times a right coset produced something that looked like a coset. But in this case, left and right cosets are the same so let's try multiplying two of these together. Here are three of the cosets:

H = a * M; H

K = Conform(b*M, G); K

L = Conform(c*M, G); L

Here is the product of the first two:

Conform(H * K, G)

Look carefully. This is one of the cosets of M. Will this always happen?

EXPERIMENT:
Try other multiplications of H, K, and L, such as K·H, H·L, L·H, K·L, and L·K. Do all of these products form cosets?

Because the subgroup M has such special properties, we will give a special name for this type of group.

DEFINITION 3.4
A subgroup H of the group G is said to be normal if all left cosets are also right cosets, and conversely, all right cosets are also left cosets. That is, H is normal if G/H = H<em>G.

We need a quick way to check whether a subgroup is normal, and the following propositions provides us with one.

PROPOSITION 3.3
A subgroup H is a normal subgroup of G if, and only if, g H g^-1 = H for all elements g in G.

Click here for the proof.

This gives us a way to determine if a subgroup is normal, but we can improve on this test.

PROPOSITION 3.4
Let H be a subgroup of G. Then H is normal if, and only if,

g·h·g^-1 ∈ H

for all elements g ∈ G and h ∈ H.

Click here for the proof.

We have already seen one example of a normal subgroup, but there are many others. For example, if G is any group, then the subgroups {e} and G are normal. These normal subgroups are said to be trivial.

If, on the other hand, G is commutative, then any subgroup will be a normal subgroup.

We conclude this section with a simple observation.

PROPOSITION 3.5
If H is a subgroup of G with index 2, then H is a normal subgroup.

Click here for the proof.

When we have a normal subgroup, the set of cosets will possess more properties than for standard subgroups. We will explore these in the next section.

Quotient Groups

When we were experimenting with multiplying cosets together, it seemed that if the subgroup N was a normal subgroup of G, then the products of two cosets gave us another coset. We will now examine why this is true.

LEMMA 3.3
If N is a normal subgroup of G, then the product of two cosets of N produces a coset of N. In fact,

a N·b N = (a·b)N.

Click here for the proof.

This proposition is very suggestive. Since we can multiply two cosets together, can the set of all cosets form another group? This is, in fact, exactly what happens.

THEOREM 3.2: The Quotient Group Theorem
Let N be a normal subgroup of G. Then the set of all cosets is a group, which is denoted by G/N, called the quotient group of G with respect to N.

Click here for the proof.

EXAMPLE:
One of the easiest groups to consider is the group of integers ℤ, under addition. A subgroup of ℤ would consist of all multiples of k, for some non-negative k. (k = 0 and k = 1 give us the two trivial subgroups.) Since ℤ is commutative, these subgroups are normal. What would the cosets look like? Each coset would consist of all numbers equivalent modulo k. So there would be k cosets of k ℤ (except when k = 0). Thus, ℤ/k ℤ is essentially the same group as Z_k.

In the case of Z_k, we used modulo arithmetic as the group operator. In essence, the notation

x ≡ y (mod k)

means that x and y belong in the same coset of ℤ/k ℤ.

We can extend this notation to any normal subgroup. We say that "x is equivalent mod N to y," or

x ≡ y (mod N)

to mean that x and y belong in the same coset of N. It is easy to see that

x ≡ y (mod N) if, and only if, x·y^-1 ∈ N

In §1.2, we defined a equivalence relation as a relation satisfying the three properties

1) (Reflexive) Every element x is equivalent to itself.
2) (Symmetric) If x is equivalent to y, then y is equivalent to x.
3) (Transitive) If x is equivalent to y, and y in turn is equivalent to z, then x is equivalent to z.

Because of the fact the two elements are equivalent if they are in the same coset, it is clear that x ≡ y (mod N) is an equivalence relation. The equivalence classes would be the cosets of N for which the relation is defined.

EXAMPLE:
Consider the octahedronal group:

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 found one normal subgroup to this group, namely

M = Group(a*b^2*c, c^2); M

The cosets, or equivalence classes, with respect to this subgroup are:

Q = LftCoset(G, M); Q

We can use the MultTable command on the quotient group:

MultTable(Q)

Notice that since the names of the elements are too long to enter them into each square, Mathematica uses a color code for the elements. Nonetheless, we can determine much information from this table.

The first thing we can observe from this table is that this group is not commutative. For example,

{a, a·c², b²·c, b²·c³} · {b, a·b·c, b·c², a·b·c³}

does not give the same thing as

{b, a·b·c, b·c², a·b·c³} · {a, a·c², b²·c, b²·c³}

We have already seen a non-commutative group of order 6, namely S₃. In fact, there is a copy of S₃ sitting inside of the group G, which could be seen by the command

H = Conform(Group(a, b), G); H

We can compare the multiplication table of this subgroup with that of the quotient group Q:

MultTable(Q)

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

The color patterns are not the same, but this doesn't mean that these two groups are not equivalent. There might be some way to rearrange the elements in the last command so that the color patterns in the two tables match.

EXPERIMENT:
Can you rearrange the elements {e, b, b², a, a·b, a·b²} in the last command so that the color patterns in the two tables match? Those who enjoy logic puzzles should find this an easy excercise. (There is more than one solution.)

Proofs:

Proof of Lemma 3.1:

It is clear from the definitions that H u and u H each contains at most |H| elements. In order to prove that the number is exactly |H| we need to show that two distinct elements of H produce two different elements in the cosets. Suppose that this were not the case in a right coset. We would have two different elements x and y for which

x·u = y·u,

which multiplying on the right by u^-1 gives x = y, a contradiction. Similar reasoning works for left cosets. If

u·x = u·y,

multiplying on the left by u^-1 shows that x = y.

Return to text

Proof of Lemma 3.2:

We begin with right cosets. Suppose there is an element g ∈ H x ∩ H y. Then there are elements h and k in H such that

g = h·x = k·y.

Therefore,

x = h^-1·k·y,

and so

(*)

H x = H h-1·k·y.

Since H is a subgroup, h^-1·k ∈ H, so that H h^-1·k ⊆ H. Moreover, if u is in H, then

u = (u·k^-1·h)·(h^-1·k) ∈ H h^-1·k.

Therefore,

H ⊆ H h^-1·k,

and we have shown that H = H h^-1·k. Combining this with (*) gives us H x = H y.

We can do left cosets in the same way. Suppose we have g ∈ x H ∩ y H. Then we have elements h and k in H such that

g = x·h = y·k.

Therefore,

x = y·k·h^-1,

and so

x H = y·k·h^-1 H = y H.

Return to text

Proof of Theorem 3.1:

We can use either left cosets or right cosets to prove this, so let us use right cosets. Every element of x in G is contained in at least one right coset. For example, x is contained in H x. Let k be the number of distinct right cosets. Then, if the right cosets are

H x₁, H x₂, H x₃, …, H x_k,

we can write

G = H x₁ ∪ H x₂ ∪ H x₃ ∪ ··· ∪ H x_k.

The ∪'s represent the union of the cosets. But by Lemma 3.2, there are no elements in common among these sets, and so this union defines a partition of G. By Lemma 3.1, each cosets contains |H| elements. So |G| = k·|H|.

Return to text

Proof of Corollary 3.1:

The order of x equals the order of the subgroup [x] of G. Therefore, by Lagrange's theorem (3.1), the assertion follows.

Return to text

Proof of Corollary 3.2:

Let m denote the order of x. By Corollary 3.1, n = m k for some integer k. Then we have xⁿ = x^m·k = (x^m)^k = e^k = e.

Return to text

Proof of Corollary 3.3:

Suppose G is of order p, which is prime. Then the only positive divisors of p are 1 and p, so by Lagrange's theorem (3.1) any subgroup must be of order 1 or p. If x is any element of G besides the identity, then [x] contains x as well as the identity. Thus, G = [x] so G is cyclic.

Return to text

Proof of Corollary 3.4:

We simply apply Corollary 3.2 to the group Z_n. This group has ϕ(n) elements, and if x is coprime to p then x is a generator of Z_n, so x is in Z_n.

Return to text

Proof of Proposition 3.1:

Since G is of order m, we have by Corollary 3.2 that x^m = e for all x in G. If r and m are coprime, then r is a generator in the additive group Z_m. But this means that r is an element of the group Z_m, and so there is an inverse element s = r^-1. Thus, s·r = 1 in Z_m. Another way we could say this is

s r = k m + 1

for some integer k. Now we are ready to take the r^th root of an element. If y is an element of G, then the r^th root of y in G is merely y^s. To see this, note that

(y^s)^r = y^s·r = y^{(k m+1)} = (y^m)^k·y = e^k·y = y.

So y^s is one r^th root of y. But y^s must be a different element for every y in G, since the r^th power of y^s is different. Since the r^th root of every element of G is accounted for, by the pigeonhole principle there cannot be two r^th roots to any element. Thus, y^s gives the unique r^th root of y in G.

Return to text

Proof of Proposition 3.2:

The proposition is trivial if x = 0, so we will assume that x > 0.

If x is coprime to n, then proposition is true by Proposition 3.1. Suppose x is not coprime to n = p·q, where p and q are the two distinct primes. By the totient function theorem (2.1), ϕ(n) = (p − 1)·(q − 1). The number x would be a multiple of either p or q, say p. Then x = p·a for some integer a, and so

x^r·s = (p·a)^r·s = p^r·s·a^r·s

will be a multiple of p.

Also, x is not a multiple of q since x is less than n. Since r·s ≡ 1 (mod (p − 1)(q − 1)), r·s ≡ 1 (mod (q − 1)). Thus, by Proposition 3.1 again, we have

x^r·s ≡ x (mod q).

Since we also have x^r·s ≡ x (mod p), by the Chinese remainder theorem (1.3), we have, since p and q are coprime,

x^r·s ≡ x (mod p·q = n).

Return to text

Proof of Proposition 3.3:

First of all, suppose H is normal, and let g be an element of G. Then g H and H g both contain the element g. Since the left and right cosets are the same, we have

g H = H g

Multiplying both sides on the right by g^-1 gives

g H g^-1 = H g·g^-1 = H

Now, suppose that g H g^-1 = H for all elements g in G. Then

H g = g H g^-1·g = g H e = g H.

Thus, every left coset is also a right coset, and vice versa.

Return to text

Proof of Proposition 3.4:

If H is a normal subgroup of G, then g·h·g^-1 ∈ g H g^-1, which is H by Proposition 3.3.

Let us suppose that for all g in G and h in H, g·h·g^-1 ∈ H. Then

g H g^-1 ⊆ H.

In particular, if we replace every g with g^-1, we get

g^-1H(g^-1)^-1 ⊆ H

Multiplying both sides of the equation by g on the left gives us H g ⊆ g H, and multiplying on the right by g^-1 gives us H ⊆ g H g^-1. Since we also have that , we can conclude that g H g^-1 = H. Then from Proposition 3.3, H is normal.

Return to text

Proof of Proposition 3.5:

Since H is a subgroup of G with index 2, there are two left cosets and two right cosets. One of the left cosets is e H, which is the set of elements in H. The other left coset must then be the set of elements not in H. But the same thing is true for the right cosets, so the left and right cosets are the same. Thus, H is normal.

Return to text

Proof of Lemma 3.3:

We simply observe that

a N·b N = a·(N b)·N = a·(b N)·N = (a·b)·(N·N) = (a·b)N.

Note that N b = b N because N is a normal subgroup.

Return to text

Proof of Theorem 3.2:

We simply have to check that G/N satisfies the four requirements in Definition 1.5. The closure property is given by Lemma 3.3. To check associativity,

a N·(b N·c N) = a N·(b·c) N = (a·(b·c)) N = ((a·b)·c) N = (a·b) N·c N = (a N·b N)·c N.

The identity element is e N = N, and we can check that

e N·a N = (e·a) N = a N, and  a N·e N = (a·e) N = a N.

Finally, the inverse of a N is a^-1N, since

a N·a^-1N = (a·a^-1) N = e N = N, and a^-1N·a N = (a^-1·a) N = e N = N.

Thus, the set of all cosets forms a group.

Return to text

Sage Interactive Problems

§3.1 #31)
Find the left and right cosets of the subgroup {e, c, c², c³} of the octahedral group, given by:

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

Are the left and right cosets the same?

§3.1 #32)
Find the left and right cosets of the subgroup {e, c², a·b²·c, a·b²·c³} of the octahedral group, given by:

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

Are the left and right cosets the same?

§3.2 #21)
This exercise is required in order to do the RSA encryption Problems 22 or 23. Using Sage's NextPrime command, find two large prime numbers p and q, at least 80 digits each. This is done by the two Sage commands

p = NextPrime( ...large number goes here... ); p

q = NextPrime( ...large number goes here... ); q

Before executing these commands, replace the "...large number goes here..." with two random numbers at least 80 digits long. We will use the value r = 10007. Verify that this number is coprime to (p − 1) and (q − 1) by executing the following:

gcd( (p - 1)*(q - 1), 10007)

If this command yields 10007 instead of 1, go back and find new values for p and q. Once the gcd is 1, compute n = p·q, and save this to a file. To do this, enter

n = p*q;
print 'n =', n

If the output is continued over several lines using backslashes, clicking on the left side of the output will convert it to a single line output. This line can then be copied and pasted into a text file, using a text editor such as Notepad or TextEditor. If you are using VirtualBox, make sure that the shared clipboard is set to "Bidirectional" in the Settings → General → Advanced tab.

Next, find the secret number s, which decyphers a message:

s = PowerMod(10007, -1, (p - 1)*(q - 1))

You will need to save this number for future reference. Enter

print 's =', s

and copy and paste the single line version output to the same text file. Save this file with a name of your choice.

Finally, copy and paste just the n number into the body of an e-mail message, sent to the professor. Do not send the value of the secret number s, but save it for a future exercise.

§3.2 #22)
Using the values of n and s from Problem 21, send an "electronic check" to your favorite professor for $100.00. This check will be in the form of a huge number, x.

Once this number is found, enter

print 'x =', x

then copy and paste the single line version of the output into the body of a letter.

§3.2 #23)
After doing Problem 21, your instructor will send you a response with a value of y. Copy and paste this line into the input cell below and evaluate it.

Also copy and paste the n and s lines from the text file you created in Problem 21, and execute these as well.

You can verify that these 3 values are entered correctly into Sage with the commands

n

s

y

Using these values of n and s, decode the messege y and hand in (on paper) what it says.

§3.2 #24)
B. L. User tried creating his encryption number with the two primes

p = NextPrime(71587027345719754873415671567856782163741561519737155752525673649286739584756092); p

q = NextPrime(p + 1); q

When he publicized the product n = p·q, along with the value r = 6367, he received a message from a friend:

y = 3092722521993064335403878476414515883199432204869058005976140725073546523106848249491531282456640454385678472107616521242043590910817888839981759972041752306977

What did this message say?

§3.3 #19)
Show that there is a group Q which is generated by two elements a and b, for which

a⁴ = e, b² = a², b·a = a³·b, a² ≠ e.

This can be entered into Sage with the command

InitGroup("e")
AddGroupVar("a", "b")
Define(a^4, e)
Define(b^2, a^2)
Define(b*a, a^3*b)
Q = Group(a, b); Q

Find all subgroups of this group, and show that all subgroups are normal, even though the group is non-abelian. (Write down the list of left cosets and right cosets for each subgroup found.)

§3.3 #20)
Use Sage, along with a bit of trial and error, to find a subgroup of order 12 of the octahedral group. Show that this subgroup is a normal subgroup. The following reloads the octahedronal group:

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

§3.4 #19)
Define in Sage the group

G = Z	*	.
	105

How many elements does this group have? Consider the subgroup H generated by the element 11. A circle graph demonstrating the cosets G/H can be obtained by the command

CircleGraph(G, Mult(11))

By looking at the circle graph, determine the cosets of G with respect to H. What is the order of the element 2·H in the quotient group G/H?

§3.4 #20)
Here is a group of order 20 from Problem 18 of §2.2:

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

Find a normal subgroup H of order 5, and form the quotient group G/H.