Please Login to access more options.


Today

« October 2025 »

Sun

Mon

Tue

Wed

Thu

Fri

Sat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

Seen in class on previous days

Problem 65 (Subgroups Of Cyclic Groups Are Cyclic)

Suppose that $G$ is a cyclic group generated by $a$. Suppose that $H$ is a subgroup of $G$. Prove that there exists $k\in\mathbb{Z}$ such that $H = \left<a^k\right>$. In other words, prove that $H$ is itself a cyclic group.

Click to see a hint.

How can you get the smallest positive integer $k$ such that $a^k\in H$?

Not Yet Seen In Class - Feel Free To Work Ahead

To find these problems, generally you can just look at the next day's material. You can also find problems on the In Progress page.

Challenge Problems - For Fun

These problems will never appear on the problem set. However, if you want to work on them and come up with your own solutions, I would love to see your work. If you want to tackle these, and want them to count towards part of your grade, I'm open to suggestions. Mostly, these problems are just fun puzzles.

Problem.The order of $GL(2,\mathbb{Z}_p)$

Let $p$ be a prime. Prove that the order of $GL(2,\mathbb{Z}_p)$ is $|GL(2,\mathbb{Z}_p)|=(p^2-1)(p)(p-1)$ and that the order of the corresponding special linear group is $|GL(2,\mathbb{Z}_p)|=(p^2-1)(p)$. You may assume that a matrix is invertible if and only if the rows of the matrix are linearly independent, a fact that you proved in linear algebra.

Problem.The order of $GL(n,\mathbb{Z}_p)$

Let $p$ be a prime and let $n\in\mathbb{N}$. Obtain a formula for the number of elements of $GL(n,\mathbb{Z}_p)$ and prove that your result is correct.

Problem.The collection of nonempty subsets of a group is not a not a group

Give an example of a group $G$ so that the collection $\mathscr{C}$ of nonempty subsets of $G$ using the set product as a binary operation is not a group. (Previous problems have shown that $\mathscr{C}$ is a monoid, which means that the set product satisfies three of the four conditions to be a group. Come up with a counterexample to the remaining condition.)

Solved

Problem 64 ($\langle a^i \rangle = \langle a^j \rangle$ iff $\gcd(i,n)=\gcd(j,n)$)

Let $G$ be a group. Suppose that $a\in G$ has order $n>1$. Prove the following two facts:

  1. If $G$ is a cyclic group, then the order of $a$ divides the order of the group.
  2. We have $\langle a^i \rangle = \langle a^j \rangle$ if and only if $\gcd(i,n)=\gcd(j,n)$.

Click for a hint.

  1. If $G$ is cyclic, then pick a generator, say $b$. This means $G=\langle b\rangle$. Why does this mean $a=b^k$ for some $k$? Use this to show that $b$ has finite order, say $m$. Then use problem 63 with $b^k$, where $|b|=m$, rather than $a^k$ and $|a|=n$.
  2. Problem 63 will get you one direction, and problems 62 will get you the other.

The second fact proves the following three corollaries by letting $i=1$.

  • We have $\langle a \rangle = \langle a^j \rangle$ if and only if $\gcd(n,j)=1$.
  • A simple shift permutation $\phi_j$ on $n$ letters generates all simple shift permutations on $n$ letters if and only if $\gcd(n,j)=1$.
  • An integer $j\in \mathbb{Z}_n$ is a generator of $\mathbb{Z}_n$ if and only if $\gcd(n,j)=1$.

What does this have to do with the problem When Does An Integer Have A Modular Multiplicative Inverse? You should see a connection between this problem and elements of $U(n)$.

See Sam's proof for a solution. We may come back to this one in class, or may not, depending on time.

Problem 84 (Properties Of Cosets Part Two)

Let $H$ be a subgroup of $G$. Let $a,b\in G$. Prove the following facts about cosets.

  1. We have $Ha=Hb$ if and only if $ab^{-1}\in H$.
  2. We must have $Ha=Hb$ or $Ha\cap Hb=\emptyset$.
  3. We have $Ha=aH$ if and only if $aHa^{-1}=H$.

We've already seen all of these properties before when studying modular arithmetic. Let $G=\mathbb{Z}$ and let $H=n\mathbb{Z}$ for some $n\in\mathbb{N}$. The cosets of $H$ are $r+n\mathbb{Z}$ for $0\leq r<n$.

  • The first property above states that $a+n\mathbb{Z}=b+n\mathbb{Z}$ if and only if $a-b\in n\mathbb{Z}$. Wait, this just says two numbers have the same remainder if and only if their difference is a multiple of $n$.
  • The second property above states that either $a$ and $b$ have the same remainder, or they don't. It basically states that remainders are unique.
  • The third property is trivial for $\mathbb{Z}$ because $\mathbb{Z}$ is an Abelian group and we always know $a+n\mathbb{Z}=n\mathbb{Z}+a$.

Click if you want a hint.

For part 2, you need to prove that one or the other of these things MUST happen. This is generally done with a two case proof. Either $Ha\cap Hb=\empty$ or $Ha\cap Hb\neq \empty$. If we know $Ha\cap Hb=\empty$, then we're done. Otherwise, assume $Ha\cap Hb\neq \empty$, and then use the fact that there must exist some $c\in Ha\cap Hb$ to prove that $Ha=Hb$.

For the other parts, you have to prove that sets are equal. We have a standard way to do this. However, if you first show that $(Ha)b=H(ab)$, then this is a lot easier because then you can use the fact that $ab^{-1}\in H$ if and only if $H(ab^{-1})=H$, which is true if and only if $H(ab^{-1})b=Hb$, and then simplify. This idea can make both part 1 and 3 trivial, but you first need to explain WHY $(Ha)b=H(ab)$. It's not hard to show, but should be shown.

Problem (Identification Graphs Using Normal Subgroups Are Cayley Graphs)

Let $G$ be a group and suppose that $N$ is a normal subgroup of $G$. Let $a,b\in G$ and suppose that $ba\in Nc$, meaning we have an arrow from $Na$ to $Nc$ that is colored by $b$.

  1. Why does $Nc=N(ba)=(ba)N$? This should follow immediately from the properties of cosets and definition of normal. Be prepared to explain.
  2. Prove that if $x\in Na$, then $bx\in Nc$. (This shows that following arrow $b$ from anything in $Na$ will get you an element in $Nc$.)
  3. Extend your result to prove that if $y\in Nb$, then we also have $yx\in Nc$.

Click if you want a hint.

You've got to make use of the fact that $Na=aN$ for every $a\in G$. So we have $Nb=bN$, $Nc=cN$, $Nx=xN$, etc. Why is this useful? Any time you see $na$ in your work for some $n\in N$, you know that $na\in Na$ which means $na\in aN$ which means there exists some $n'\in N$ with $na=an'$. You don't have the ability to commute as we may not have $na\neq an$, but we get ALMOST commutativity. We can write $na=an'$ for some different $n'\in N$. The $'$ symbol just means that it's a different element. It's not a derivative.

So in your work if you ever see $bn_1a$, you can instead either write $bn=n_2b$ or you could write $na=an_3$ for some $n_2,n_3\in N$, and then you have $bn_1a = n_2ba=ban_3$. Similarly, if you see $n_1yn_2x$, then you should be able to write this, after some work, in either the form $n_3yx$ or the form $yxn_4$ (you'll need to use the closure of the operation in $N$ to combine elements in $N$).

You can't use the commutative law, but you have something pretty close.

Problem 85 (The Set Product Is A Binary Operation On Cosets Of Normal Subgroups)

Suppose that $N$ is a normal subgroup of $G$. Let $a,b\in G$, and consider the two cosets $Na$ and $Nb$. Show that the set product $(Na)(Nb)$ is again a coset of $N$, and that we have $(Na)(Nb)=N(ab)$.

This shows that the set product is a binary operation on right cosets (and left cosets) of a normal subgroup $N$.

Click if you want a hint.

You've got to make use of the fact that $Na=aN$ for every $a\in G$. So we have $Nb=bN$, $Nc=cN$, $Nx=xN$, etc. Why is this useful? Any time you see $na$ in your work for some $n\in N$, you know that $na\in Na$ which means $na\in aN$ which means there exists some $n'\in N$ with $na=an'$. You don't have the ability to commute, but we get ALMOST commutativity. We can write $na=an'$ for some different $n'\in N$. The $'$ symbol just means that it's a different element. It's not a derivative.

So in your work if you ever see $bn_1a$, you can instead either write $bn=n_2b$ or you could write $na=an_3$ for some $n_2,n_3\in N$, and then you have $bn_1a = n_2ba=ban_3$. Similarly, if you see $n_1an_2b$, then you should be able to write this, after some work, in either the form $n_3ab$ or the form $abn_4$ (you'll need to use the closure of the operation in $N$ to combine elements in $N$).

You can't use the commutative law, but you have something pretty close.

Click if you want a hint.

You've got to make use of the fact that $Na=aN$ for every $a\in G$. So we have $Nb=bN$, $Nc=cN$, $Nx=xN$, etc. Why is this useful? Any time you see $na$ in your work for some $n\in N$, you know that $na\in Na$ which means $na\in aN$ which means there exists some $n'\in N$ with $na=an'$. You don't have the ability to commute as we may not have $na\neq an$, but we get ALMOST commutativity. We can write $na=an'$ for some different $n'\in N$. The $'$ symbol just means that it's a different element. It's not a derivative.

So in your work if you ever see $bn_1a$, you can instead either write $bn=n_2b$ or you could write $na=an_3$ for some $n_2,n_3\in N$, and then you have $bn_1a = n_2ba=ban_3$. Similarly, if you see $n_1an_2b$, then you should be able to write this, after some work, in either the form $n_3ab$ or the form $abn_4$ (you'll need to use the closure of the operation in $N$ to combine elements in $N$).

You can't use the commutative law, but you have something pretty close.

For more problems, see AllProblems