Homework Assignments

Homework will be due once a week. This page will be updated every time a new problem set is posted. Solutions for each problem set will be posted on this page after the assignment is due.

The overall guiding principle in your writing is to remember that your work is meant to be read by a skeptical peer; your job is to write a (logically) convincing argument to this audience. Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Though you are welcomed to collaborate with the instructor or your classmates on problems, you are not permitted to reference outside sources or people when completing homework problems. For example, it is a violation of the Honor Code to use any of the following resources to find a solution to a problem: using a search engine to mine the internet for a solution, visiting an online mathematics discussion group, or collaborating with students not registered for this course.

Starting with assignment 2, your homeworks will typically be submitted in two parts, "Part A" and "Part B"). The two parts of this assignment will be submitted in separate folder, and will be graded by separate graders. Please be sure you've written your solutions in a way that allow you to submit your solutions for Part A separate from your solutions for Part B!

assignments

Assignment 1 (due Friday, Sept 8 at 4pm)

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

Part A

Read the syllabus in its entirety. After you've done this, you can write the sentence ``I read the syllabus" as your answer to this problem and receive full credit.
We're about to embark on 3 months of mathematics together. Although this is the start of our mathematical journey together, each of us comes to this class with our own mathematical past. To help seat this semester's work in the larger story of your mathematical journey, I'd like you to write a 300-400 word mathematical autobiography. This autobiography will not be shared with other students (unless you choose to do so). After reading autobiographies I might share some summary information; I might also want to post excerpts from some people's essays, but I'd only do this after receiving permission to do so.

In your autobiography, you might choose to explore some of the following:
- An example of a successful/satisfying mathematical experience in your past, as well as an example of an unsuccessful/disheartening mathematical experience.
- An accounting of the skills which facilitate your mathematical work, as well as a reflection on the obstacles which make working on mathematics more difficult for you.
- What qualities of mathematics do you find fun? (or boring, or scary, or dull, or mystical, etc.)
- How does this class fit into your mathematical journey? your overall academic journey? your overall life journey?
Given the word limitation, it's unlikely that you can pursue all of these prompts. Instead, focus on whatever questions speak the most to you, or chart your own path if you prefer.
[NB. It's probably easiest for you to write your autobiography electronically and then print it out. You can just submit the printed version.]
Stop by Andy's office (during office hours or at another convenient time) and introduce yourself to Andy. You can do this as a part of a larger group if you like. After you've done this, you can write the sentence ``I met with Andy at his office" as your answer to this problem and receive full credit. If you can't make it during office hours, or for some other reason aren't able to drop by during the first week of classes, email Andy to set up some other time to meet.
Here's a picture of a watermelon my family and I enjoyed this summer. (It was delicious!) Pretend you took a circular cross section of this watermelon, and also pretend that the watermelon is idealized (perfectly circular, no annoying seeds, etc.). Argue that this cross section has 6 symmetries. What does the Cayley table look like? (It might be convenient to be inspired by our discussion of $D_4$ when you're trying to create suitable names for your symmetries.)

Here are the solutions to this homework assignment.

Assignment 2 (due Friday, Sept 15 at 4pm)

Part A

Let $G$ be the set of $2 \times 2$ matrices, and let $\star$ be matrix multiplication. Prove that $(G,\star)$ is not a group.
Prove that function composition is associative. That is, if you are given functions $f:A \to B$, $g:B \to C$ and $h:C \to D$, prove that $h \circ (g \circ f) = (h \circ g) \circ f$.
[NB. To do this problem, you'll need to recall what function composition means, and what it means for two functions to be equal. In case you don't remember, here are those definitions. If $k:X \to Y$ and $\ell:Y \to Z$ are two functions, then the composition $\ell \circ k$ is the function with domain $X$ and codomain $Z$ defined by $(\ell \circ k)(x) = \ell(k(x))$. If $\alpha:U \to V$ and $\beta: U \to V$ are two functions, then we say that $\alpha = \beta$ iff for all $u \in U$ we have $\alpha(u) = \beta(u)$.]
($\star$) For each of the following values of $a$ and $n$, find the remainder $r$ upon dividing $a$ by $n$. You are not allowed to use a calculator. (Hint: If you do these problems in a clever way, none should be too computationally taxing.)
1. $a=110\cdot 74$ and $n=115$
2. $a=-184$ and $n=13$
3. $a=3^{20}$ and $n=24$
[Note: this problem involves some content that we'll discuss in class on Monday, Sept 11; you might wait to attempt this problem until after that class.]

Part B

In this part, be fastidious about your use of parentheses and your acknowledgement of the use of associativity every time it's put into play. You will not always be asked to be so careful about associativity for the duration of the course, but since we're just getting started on our journey we're going to bask in its splendor for a while.

Show that the set $\mathbb{R}$ under the operation $x \triangle y = (x + y) + 1$ is a group. (Note: the right hand side of this expression is the "usual" real addition. You are allowed to use familiar properties of real addition, provided you cite them explicitly and use them carefully.)
($\star$) Suppose you are told that $G$ is a group of six elements from $GL_2(\mathbb{R})$ under the operation of matrix multiplication. Suppose you are also told that $$\left(\begin{array}{cc}0&1\\1&0\end{array}\right) \in G \quad \mbox{ and } \quad \left(\begin{array}{rr}-1&-1\\0&1\end{array}\right) \in G.$$
1. What are the other elements in $G$? Be sure to fully justify each of your claims using the appropriate axioms and/or theorems.
2. Write out a Cayley table for $G$.
Suppose that $G = \{5,15,25,35\}$, and that $\star$ is multiplication modulo $40$. Is $(G,\star)$ a group? Prove your assertion. [Note: this problem involves some content that we'll discuss in class on Monday, Sept 11; you might wait to attempt this problem until after that class.]

Here are the solutions to this assignment.

Assignment 3 (due Friday, Sept 22 at 4pm)

Part A

Prove that for any integer $n$, the numbers $4n+1$ and $11n+3$ are relatively prime.
Suppose that $a$ and $b$ are nonzero integers. Prove that every element of $$S = \{ka+\ell b: k,\ell \in \mathbb{Z} \mbox{ and }ka+\ell b>0\}$$ is a multiple of $\gcd(a,b)$.
For each of the following, determine if the statement is true or false. If it's true, give a proof. If it's false, given an explicit counterexample.
1. If $a,b \in \mathbb{Z}$ have $d = \gcd(a,b)$, with $a = dx$ and $b = dy$, then $\gcd(x,b) = 1$.
2. If $a,b \in \mathbb{Z}$ have $d = \gcd(a,b)$, with $a = dx$ and $b = dy$, then $\gcd(x,y)= 1$.

Part B

Suppose that $n$ and $k$ are integers with $n$ positive and so that $\gcd(k,n)=d$. Prove that if $a \in \mathbb{Z}$ has $a \equiv k \pmod{n}$, then $\gcd(a,n)=d$ as well.
Suppose that $a,b,n \in \mathbb{Z}$ with $n>0$, and also that $n \mid ab$ and $\gcd(a,n)=1$. Prove that $n \mid b$.
[Hint: Bezout.]
Suppose that $(G,\star)$ is a group which satisfies the property that for all $g \in G$ one has $g\star g=e_G$. Prove that for all $a,b \in G$, we have $a\star b = b\star a$.

Here are the solutions to this assignment.

Assignment 4 (due Friday, Sept 29 at 4pm)

Part A

Suppose that $(G,\star)$ and $(\hat G,*)$ are both groups. Define $$G\oplus \hat G = \{(g,\hat g): g \in G, \hat g \in \hat G\},$$ and define the operation $\boxdot$ on $G \oplus \hat G$ by $$(g_1,\hat g_1) \boxdot (g_2,\hat g_2) = (g_1 \star g_2,\hat g_1 * \hat g_2).$$ Prove that $(G \oplus \hat G,\boxdot)$ is a group. (This group is called the "direct sum" of $G$ and $\hat G$. We will continue to study direct sums and their properties as the semester unfolds.)
Suppose that $(G,\star)$ is a group and $g \in G$. Prove that $|g|=|g^{-1}|$.
Let $(G,\star)$ be a group, and let $n$ be a positive integer. Define $$G[n] = \{g \in G: g^n = e_G\}.$$ (As usual, we use $g^n$ to denote the $n$-fold operation of $g$ against itself.)
1. Prove that if $G$ is abelian, then $G[n]\leq G$. [Hint: you may want to prove that for any $a,b \in G$ and $k$ a positive integer, we have $(ab)^k = a^kb^k$.]
2. Give a specific example of a group $G$ and a positive integer $n$ so that $G[n] \not\leq G.$ Be sure to explicitly exhibit the failure of one of the group axioms to justify your claim.

Part B

Suppose that $G$ is a group, $g \in G$ is given, and $K$ is a subgroup of $G$. The $g$-conjugate of $K$ is defined to be $$gKg^{-1} = \{gkg^{-1}: k \in K\}.$$
1. Prove that $gKg^{-1}$ is a subgroup of $G$.
2. Let $G = D_4$. Compute the $R_{90}$-conjugate of the subgroup $\{R_0,V\}$, as well as the $D'$-conjugate of the rotation subgroup $\{R_0,R_{90},R_{180},R_{270}\}$.
($\star$) Suppose that $G$ is a group, and you are told that $a,b \in G$ satisfy $|a| = 4$ and $|b| = 2$. If $a^3b = ba$, what is the order of $ab$? As ever, be sure to justify your assertion.
Suppose that $G$ is a group and $g \in G$. Suppose you also know that $g^2 \neq e_G$ and $g^5 \neq e_G$, but that $g^{10}=e_G$. Prove that $|g| = 10$. (Note: For this problem you cannot use the ``order divides" lemma, even if we've stated it in class.)

Additional optional exercises

In class we used that fact that if $g \in G$, then $(g^{-1})^{-1} = g$. Prove it. [Hint: waddle waddle.]
Suppose that $(G,\star)$ is a group and $g \in G$. We have already established notation for positive powers of $g$. For example, $g^2$ means $g \star g$, and $g^1$ means $g$. When $n>1$, there are two natural ways to interpret what $g^{-n}$ might mean: as $(g^n)^{-1}$, or as $(g^{-1})^n$. Show that these two interpretations coincide. [Hint: show that the latter expression walks like a duck.]
[NB: The standard convention is to interpret $g^0$ as $e_G$. The reason this is a good convention is that it allows us to use familiar exponent rules when describing powers of group elements. For instance, we can say that for all $n,m \in \mathbb{Z}$ we have $g^{n+m} = g^n\star g^m$.]
Suppose that $g,h$ are elements of an abelian group $G$, and let $\ell = \text{lcm}(|g|,|h|)$.
- Show that $(g\star h)^\ell = e_G$.
- Give an example of an abelian group $G$ and elements $g,h \in G$ so that $|g\star h| \neq \text{lcm}(|g|,|h|)$.
- Give an example of a group $G$ and elements $g,h\in G$ so that $(g \star h)^\ell \neq e_G$.

Here are the solutions to this assignment.

Assignment 5 (due Friday, Oct 6 at 4pm)

Part A

On your second homework assignment, you considered $G = \left\{I,A,B,AB,BA,ABA\right\} \subseteq GL_2(\mathbb{R})$ which had the following Cayley table: $$ \begin{array}{c|cccccc} &I&A&B&AB&BA&ABA\\ \hline I&I&A&B&AB&BA&ABA \\ A&A&I&AB&B&ABA&BA \\ B&B&BA&I&ABA&A&AB \\ AB&AB&ABA&A&BA&I&B \\ BA&BA&B&ABA&I&AB&A \\ ABA&ABA&AB&BA&A&B&I \\ \end{array} $$
1. Compute $Z(G)$.
2. For each $g \in G$, compute $|g|$. Make sure you explain your conclusions.
3. Compute $C(A)$ and $C(AB)$.
Let $a,b \in G$, and suppose you know that $|a| = k$ and $|b| = \ell$ with $\gcd(k,\ell)=1$. Prove that $\langle a \rangle \cap \langle b \rangle = \{e\}$. [Note: this question deals with the intersection of two sets. In general, if $A$ and $B$ are sets within a larger set $X$, then $A \cap B$ is the set of all $x \in X$ which satisfy both $x \in A$ and $x \in B$.]
Suppose that $G = \langle a \rangle$, and that $|a| = 24$.
1. Find (with proof) all generators of $G$.
2. Give a subgroup of $G$ with $6$ elements. Find all generators of this subgroup.

Part B

Suppose that $G$ is a group and $a \in G$. Suppose further that $|a|=5$. Prove that $C(a) = C(a^3)$.
Suppose that $G$ is abelian, and that $|a|=k$ and $|b|=\ell$ with $\gcd(k,\ell)=1$. Prove that $|ab|=k\ell$. [Hint: You can use problem 2 from this pset if you like, as well as the hint from problem 3(a) from last week's pset.]
Let $n$ be a positive integer that is at least $3$. Show that $U(2^n)$ has at least three elements of order $2$. Then explain why this proves $U(2^n)$ is not cyclic. [Hint for the first part: For a few small values of $n$, find a few $g \in U(2^n)$ which satisfy $g^2 = 1$. Use these cases to make a conjecture about values in an arbitrary $U(2^n)$ which have order $2$, and then prove your conjecture. For the second part: you might want to wait until Monday's class when we cover some additional theory that is useful for arguing that a group is not cyclic.]

Here are the solutions to this assignment.

Assignment 6 (due Monday, Oct 16 at 4pm)

permutation worksheet

Part A

Prove that the composition of surjections is again surjective. (I.e., prove that if $f:X \to Y$ and $g:Y \to Z$ are both surjections, then $g \circ f: X \to Z$ is surjective.)
Let $i \in \{1,2,\cdots,n\}$ be given, and define $\textrm{stab}(i) = \{\sigma \in S_n : \sigma \mbox{ fixes }i\}.$ (The ``stab" here stands for ``stabilizer.") Prove that $\textrm{stab}(i)$ is a subgroup of $S_n$.
[Note: usually when we talk about a function $f$ acting on an element $x$, we use the notation $f(x)$ to indicate the corresponding output. Since cycle representations for functions in $S_n$ already use parenthetical notation, the problem is that it's not quite clear how to interpret $\sigma(i)$ when $\sigma \in S_n$ and $k \in \{1,2,\cdots,n\}$; is it $\sigma$ times the $1$-cycle $(k)$? or $\sigma$ acting on $k$? We can circumvent this problem by using the notation ``$\sigma[k]$'' to denote the output under the function $\sigma$ that corresponds to the input $k \in \{1,2,\cdots,n\}$. With this notation, $\text{stab}(i)$ becomes $\{\sigma \in S_n: \sigma[i]=i\}$.]
Complete problems (4), (5), and (7) from the permutation worksheet.

Part B

Prove that $Z(S_n) = \{\varepsilon\}$ for all $n \geq 3$. [Hint: if $\alpha$ is a non-identity element of $S_n$, then there exists some $k \in \{1,2,\cdots,n\}$ so that $\alpha[k] \neq k$.]
Suppose that $\alpha \in S_9$ has the property that $\alpha^5 = (3,1,4,6,7,2,8,9,5)$. Determine $\alpha$. [Note: For this problem you can use the fact that every element in $S_9$ has order at most $20$.]
In class we defined the notation of the inverse of a function $f:A \to B$ as some function $g:B \to A$ so that $f \circ g = \text{id}_B$ and $g \circ f = \text{id}_A$. Some folks would instead call this a ``$2$-sided inverse" for $f$, since it has desirable properties when composed either before or after $f$. There are, however, ways to define ``one-sided inverses" for certain functions.
A function $h:B \to A$ is called a left-inverse for $f:A \to B$ if $h \circ f = \text{id}_A$, and it's called a right-inverse for $f$ if $f \circ h = \text{id}_B$$.
1. Show that if $f$ has a left inverse, then $f$ is injective.
2. Show that if $f$ has a right inverse, then $f$ is surjective.
[Note: it turns out that $f$ is injective if and only if it has some left inverse, and $f$ is surjective if and only if it has some right inverse. It's also true that if a function has a left inverse, that left inverse might not be unique. (In the same way, if a function has a right inverse, that right inverse might not be unique.)]

Here are the solutions to this assignment and solutions to the handout.

Fake Assignment 7 (due never at 4pm)

This problem set is "fake" in the sense that you will not be submitting your work on these problems to be graded. On the other hand, it is very much "real" in the sense that it covers topics that are relevant for the first midterm. You should spend some time thinking about these problems. Solutions will be posted as soon as they can be written up (but hopefully by Monday at the latest).

Suppose that $H \leq S_n$. Prove that $|A_n \cap H|$ is either $|H|$ or $\frac{|H|}{2}$.
Prove that if $\sigma \in S_n$ has odd order, then $\sigma \in A_n$.
Find specific elements $\alpha,\beta \in S_6$ so that $\alpha$ and $\beta$ have even order, and so that $\alpha \in A_6$ and $\beta \not\in A_6$.
Suppose that $(G,\star)$ is a group, and let $g \in G$. Define the function $\mu_g:G \to G$ by $\mu_g(h) = g \star h$ for all $h \in G$.
1. Show that $\mu_g \in S_G$.
2. Show that $\mu_g \circ \mu_h = \mu_{g \star h}$
What are the possible orders for elements in $S_9$?
Prove that $(1234)$ is not expressible as a product of $3$-cycles.

Here are the solutions to this assignment.

Assignment 8 (due Friday, Oct 27 at 4pm)

Part A

Prove that the composition of two homomorphisms is a homomorphism. That is, prove that if $(G,\star)$, $(\hat G,\bullet)$, and $(\tilde G,\boxdot)$ are groups, and if $f:G \to \hat G$ and $\varphi: \hat G \to \tilde G$ are homomorphisms, then $\varphi \circ f$ is a homomorphism.
Suppose that $G$ is a group, and that $g \in G$. Define a function $\varphi_g:G \to G$ by $\varphi_g(h) = ghg^{-1}$ for all $h \in G$. Prove that $\varphi_g$ is a bijective homomorphism.
In the previous problem we associated each element $g \in G$ to a bijective homorphism $\varphi_g$.
1. Prove that $\{\varphi_g: g \in G\}$ is a subgroup of $S_G$. [This subgroup is called the "inner automorphism group of $G$", and is denote $\text{Inn}(G)$.]
2. Our method for associating elements of $G$ to inner automorphisms can be interpretted as a function from $G$ to $\text{Inn}(G)$. Namely, let's define $\Psi:G \to \text{Inn}(G)$ by letting $\Psi(g) = \varphi_g$. Prove that $\Psi$ is a homomorphism.
3. Determine (with proof) $\ker(\Psi)$.

Part B

You have two friends (Friend A and Friend B) who know a little bit of abstract algebra, and so the three of you strike up a conversation about homomorphisms. Friend A says "I built an operation preserving function $f$ with domain $\mathbb{Z}_3$ and codomain $\mathbb{Z}_6$ by defining $f([k]_3) = [2k]_6$." Friend B says "I built an operation preserving function $g$ with domain $\mathbb{Z}_3$ and codomain $\mathbb{Z}_6$ by defining $g([k]_3) = [3k]_6$."
Have your friends really done what they asserted? (Each friend has really made two assertions: that they have built a function, and that their function preserves the relevant operation. In analyzing each friend's statement, you must first determine whether their first assertion holds; only then is it sensible to ask if their second assertion holds too.)
Prove that the function $f:G \to G$ given by $f(g) = g^{-1}$ is a homomorphism if and only if $G$ is abelian.
Suppose that $\phi:G \to D_4$ is a surjective homomorphism with $|\ker(\phi)|=6$.
1. Prove that $G$ has at least two (distinct) subgroups of order $12$, and at least one subgroup of order $24$. [Hint: what do you know about subgroups of $D_4$?]
2. Can you make any conclusions about whether $G$ is abelian or not? Justify your answer.
3. Suppose we drop the assumption that $\phi$ is surjective. Give an explicit example of a group $G$ and a homomorphism $\phi:G \to D_4$ so that $|\ker(\phi)|=6$, and yet $G$ does not contain any subgroups of order $12$ or $24$.
[Note: This problem uses ideas that we will discuss in class on Monday, Oct 23.]

Here are the solutions to this assignment.

Assignment 9 (due Friday, Nov 3 at 4pm)

Part A

Let $H \leq G$ and $x \in G$. Prove that $H \simeq xHx^{-1}$.
Prove that $U(24)$ is not isomorphic to $U(15)$.
Last homework we considered the function $\Psi:G \to \text{Inn}(G)$ defined by $\Psi(g) = \varphi_g$.
1. Give an example of a group $G$ for which $\Psi$ is an isomorphism. (As ever, be sure to prove your assertion.)
2. Give an example of a group $G$ for which $\Psi$ is not an isomorphism. (Again, be sure to prove your assertion.)
3. In class we saw that if $f:H \to \hat H$ is a homomorphism, then for any $h \in H$ we have $|f(h)| \mid |h|$. With this in mind, find a specific group $G$ and a specific $g \in G$ so that $|\varphi_g|$ is a proper divisor of $|g|$. [Note: a "proper divisor" of a number $n$ is a divisor of $n$ that is neither $1$ nor $n$.]

Part B

Suppose that $\phi \in \text{Aut}(D_4)$ satisfies $\phi(R_{90}) = R_{90}$ and $\phi(H) = V$. Prove that $\phi$ must be the inner automorphism defined by $R_{90}$. [Hint: You need to show that for each $g \in D_4$, we have $\phi(g) = \varphi_{R_{90}}(g)$.]
Suppose that $G \simeq Q$. Prove that $\text{Aut}(G) \simeq \text{Aut}(Q)$.
Suppose that $(G_1,\star) \simeq (Q_1,\dagger)$ and that $(G_2,\bullet) \simeq (Q_2,\odot)$. Prove that $G_1 \oplus G_2 \simeq Q_1 \oplus Q_2$. [Note: we defined the notion of direct sum in problem 1 of assignment 4.]

Here are the solutions to this assignment.

Assignment 10 (due Friday, Nov 10 at 4pm)

Part A

Find all $n \neq 20$ so that $U(n) \simeq U(20)$. Justify your answer.
($\star$) Is it always true that $\text{Aut}(G \oplus H) \simeq \text{Aut}(G) \oplus \text{Aut}(H)$? Prove or give a specific counterexample. [Hint: to get some intuition going, you might try thinking about some small groups $G$ and $H$ to see if this statement holds.]
For each of the following groups $G$ and subgroups $H$, list all the distinct left cosets of $H$ in $G$. (Be sure that your list does not contain any repeats!)
1. $H = \langle (1234)\rangle$ and $G = S_4$
2. $H = \langle (123) \rangle$ and $G = A_4$

Part B

Compute the number of elements of order $15$ in $S_3 \oplus \mathbb{Z}_{30} \oplus U(9)$.
Find an explicit group $G$, subgroup $K$, and elements $a,b \in G$ so that $aK = bK$ but $ab^{-1} \not\in K$. Why does this result not contradict the "properties of cosets" theorem we discussed in class?
Prove that $U(n)$ is cyclic if and only if $n$ is either $1,2,4$, a power of an odd prime, or twice a power of an odd prime. [Hint: in this problem, you may use the fact that $n$ has a factorization into primes.]

Here are the solutions to this assignment.

Assignment 11 (due Friday, Nov 17 at 4pm)

Part A

In class we saw that if $n$ is a number for which there exists some $a \in \mathbb{Z}$ with $a^{n} \not\equiv a \pmod{n}$, then $n$ cannot be prime. There are, on the other hand, composite numbers $n$ so that for all $a \in \mathbb{Z}$, we have $a^{n} \equiv a \pmod{n}$. These numbers are called pseudoprimes, and they also go by the name Carmichael numbers.
Prove $n=561 = 3\cdot 11 \cdot 17$ is a Carmichael number. [Hint: what group is $\mathbb{Z}_{561}$ isomorphic to, and what is the isomorphism we described from $\mathbb{Z}_{561}$ to this group?]
($\star$) Suppose that $G$ is a group, that $H \lhd G$, and that $g \in G$. We now have two meanings for "the order of $gH$." One is in thinking of $gH$ as a set of elements, in which case $|gH|$ would be the number of elements in the set. The other in thinking of $gH$ as an element of the group $G/H$, in which case $|gH|$ is the smallest positive power of $gH$ which yields $e_{G/H}$. Between these two, the second interpretation is the one that is more interesting, since we already have some theory that tells us that the number of elements in any coset for $H$ is just the number of elements in $H$.
1. Consider $\langle [16]_{35} \rangle \lhd U(35)$. What is $|[3]_{35}\langle [16]_{35}\rangle|$? (I.e., what is the order of $[3]_{35}\langle [16]_{35}\rangle$ in the group $U(35)/\langle [16]_{35}\rangle$?)
2. Suppose that $G$ is a group and $H \lhd G$; suppose that $g \in G$ is given so that $g$ has finite order. Prove that the order of $gH$ (as an element of $G/H$) is finite and divides the order of $g$ (as an element of $G$).
Suppose that $|G| = n$ and that $G$ is abelian. Prove that for any $m \in \mathbb{Z}$ with $\gcd(m,n) = 1$, the function $f_m:G \to G$ given by $f_m(g) = g^m$ is an element of $\text{Aut}(G)$.

Part B

Let $\displaystyle H = \left\{\left(\begin{array}{cc}a&b\\0&c\end{array}\right): a,b,c \in \mathbb{R} \mbox{ and }ac \neq 0\right\}.$ Is $H \lhd \textrm{GL}_2(\mathbb{R})$?Justify your assertion.
Suppose that $N \lhd G$ and $H \leq G$, and define $NH = \{nh: n \in N, h \in H\}$. Prove that $NH \leq G$.
We say that a group $G$ is simple if the only normal subgroups of $G$ are $\{e_G\}$ and $G$.
1. Prove that if $p$ is prime, then $\mathbb{Z}_p$ is simple.
2. Prove that if $G$ is a finite, abelian group whose order is neither $1$ nor a prime number, then $G$ is not simple. [Hint: You may use, without proof, the following theorem (often called Cauchy's theorem for finite abelian groups): if $G$ is a finite abelian group and $q$ is a prime number with $q \mid |G|$, then $G$ contains an element of order $q$.]

Here are the solutions to this assignment.

Fake Assignment 12 (due never)

This problem set is "fake" in the sense that you will not be submitting your work on these problems to be graded. On the other hand, it is very much "real" in the sense that it covers topics that are relevant for the second midterm. You should spend some time thinking about these problems. Solutions will be posted as soon as they can be written up.

Problems marked with a ``$\dagger$" on this problem set indicate problems that are extra "fun." These are great problems to think about because they push our understanding of groups even further, but they aren't topics that we will get a chance to treat as deeply as we would like. While they represent great ways to test your understanding of what we have been doing, I do not expect you to be able to incorporate the ideas discussed in these problems on your work for the second midterm or final exam.

In our proof of Cauchy's theorem on finite abelian groups, we got to a point where we had an element $x^s \in G$ with $|x^s|=q$, where $q$ is some prime different from $p$. We then used induction to find some coset $y\langle x^s \rangle \in G/\langle x^s\rangle$ so that $|y\langle x^s\rangle|=p$. (UPDATED LANGUAGE!) Use this $y$ to find an element of order $p$, thereby finishing our proof of Cauchy's theorem.
Suppose $p$ is prime and that $|G| = p^3$, with $Z(G) \neq \{e\}$ and $Z(G) \neq G$. Prove that $Z(G) \approx \mathbb{Z}_p$.
Suppose that $f:G \to Q$ is a homomorphism and that $H \lhd G$ which satisfies $H \subseteq \ker(f)$. Prove that $$\tilde f: G/H \to Q$$ defined by $\tilde f\left(aH\right) = f(a)$ is well-defined and a homomorphism. [Note: you can describe this phenomenon in a couple of ways. Some people say $\tilde f$ is the homomorphism on $G/H$ induced by $f$; others say that $f$ descends to the homomorphism $\tilde f$ on $G/H$.]
In our proof of the first isomorphism theorem, we created a function $\phi:G/\ker(f) \to f(G)$ by setting $\phi(g\ker(f)) = f(g)$. We showed this function was well-defined, and that it preserved the group operation. Show that $\phi$ is a bijection, thereby completing our proof of the first isomorphism theorem.
Suppose that $\phi: G \to \mathbb{Z}_6 \oplus \mathbb{Z}_2$ is a surjective homomorphism, and that $|\ker(\phi)| = 5$. Prove that $G$ has normal subgroups of order $5, 10, 15, 20, 30$ and $60$. Prove that $G$ has at least two normal subgroups of order $30$.
Prove the second isomorphism theorem: If $K \leq G$ and $N \lhd G$, then $$K/(K\cap N) \approx KN/N.$$ (Note: The set $KN$ is defined as $$KN = \{kn : k \in K \mbox{ and }n \in N\}.$$ This is much like the subgroup $NK$ from the last assignment, so don't bother with showing that $KN$ is a subgroup. For this statement to make sense, though, you should check that $N \lhd KN$.)

[Hint: Use the fundamental theorem of homomorphisms.]
Prove the third isomorphism theorem: if $H,K$ are normal subgroups of $G$ with $H \leq K \leq G$, then $$\frac{G/H}{K/H} \approx G/K.$$[Hint: Use the fundamental theorem of homomorphisms.]
[NB: One of the benefits of using the fundamental theorem of homomorphisms in this problem is that one doesn't have to think about the group $(G/H)/(K/H)$. This is good, since even parsing out what elements in this group look like is quite subtle!]
Suppose that $k \mid n$. Prove that $\mathbb{Z}_n/\langle k \rangle \approx \mathbb{Z}_k$. [Note: On the left side of the isomorphism, the element $k$ is in $\mathbb{Z}_n$, and so $\langle k \rangle \subseteq \mathbb{Z}_n$ (as opposed to $k \in \mathbb{Z}$ and $\langle k \rangle \subseteq \mathbb{Z})$.]
[Hint: You could prove this with the fundamental theorem of homomorphisms, but another approach begins by proving that the quotient of a cyclic group is cyclic, and then considering orders. Also: to make sure your proof is valid, be sure you are explicit about how you're using the hypothesis $k \mid n$.]
($\dagger$) Suppose that $Q$ and $N$ are groups (with operations $*$ and $\star$, respectively) and that there is a homomorphism $\theta: Q \to \textrm{Aut}(N)$; we'll use the notation $\theta_q$ to stand for the automorphism of $N$ which $q$ maps to under $\theta$ (hence for each $q \in Q$ there exists a $\theta_q \in \textrm{Aut}(N)$). Now we'll define $N \rtimes_\theta Q$ to be the set $N \times Q$ equipped with operation $$(n_1,q_1)(n_2,q_2) = (n_1 \star \theta_{q_1}(n_2),q_1 * q_2).$$ Prove that this is a bona fide binary operation on $N \rtimes_\theta Q$, and that $N \rtimes_\theta Q$ forms a group under this binary operation. [This group is called the semi-direct product of $N$ and $Q$ relative to $\theta$.]
[NB: When $\theta:Q \to \textrm{Aut}(N)$ is the map defined by $\theta(q) = \text{id}_N$ for all $q$, the construction above shows that $N \rtimes_\theta Q = N \oplus Q$. Hence the semi-direct product is a generalization of direct sum.]
($\dagger$) Suppose that $A$ is a set and that $G$ is a subgroup of the permutation group $S_A$. For an element $a \in A$, we define $$\mathcal{O}_G(a) = \{g(a): g \in G\}.$$ (This set is called the orbit of $a$ under $G$. Note that $\mathcal{O}_G(a) \subseteq A$.) Prove that $\textrm{stab}(a) = \{g \in G: g(a) = a\}$ is a subgroup of $G$. Show that there is a bijection between $\mathcal{O}_G(a)$ and left cosets of $\textrm{stab}(a)$. Conclude that $$|G| = \left|\textrm{stab}(a)\right|\left|\mathcal{O}_G(a)\right|.$$ (This is often called the orbit-stabilizer theorem.)
($\dagger$) Let $G$ be a group and $g \in G$ be given. The conjugacy class of $g$ is the set $$[g] = \{xgx^{-1}: x \in G\}.$$ (The conjugacy classes are simply the equivalence classes given by the relation $a \sim b$ if and only if there exists some $x \in G$ so that $a = xbx^{-1}$.) Note that $[g] = \{g\}$ if and only if $g \in Z(G)$. (You don't have to prove this.)
Now suppose that $|G| = p^k$ for some prime $p$ and some positive integer $k$ . Prove that if $g \not\in Z(G)$, then $|[g]|$ is a power of $p$. [Hint: Use the orbit-stabilizer theorem above.] Use this to prove that $|Z(G)| \neq 1$ for such a group $G$.
($\dagger$) Prove that if $|G| = p^2$, then $G \simeq \mathbb{Z}_{p^2}$ or $G \simeq \mathbb{Z}_p \oplus \mathbb{Z}_p$. [Hint: Use the previous result.]
($\dagger$) If $G$ is a group, then if $a,b \in G$, we define the commutator $[a,b]$ of $a$ and $b$ to be the element $$[a,b]=aba^{-1}b^{-1}.$$ The commutator subgroup $[G,G]$ is the subgroup generated by commutators ; this means that $x \in [G,G]$ if and only if there exists some $n \in \mathbb{N}$ and some group elements $a_1,b_1,a_2,b_2,\cdots,a_n,b_n \in G$ with $$x = [a_1,b_1][a_2,b_2]\cdots[a_n,b_n].$$ It is a fact (that you don't have to prove) that $[G,G] \leq G$. Prove that $[G,G] \lhd G$, and that $G/[G,G]$ is abelian.

Here are the solutions to this assignment.

Fake Assignment 13 (due never)

This problem set is "fake" in the sense that you will not be submitting your work on these problems to be graded. On the other hand, it is very much "real" in the sense that it covers topics that are relevant for the second midterm. You should spend some time thinking about these problems. Solutions will be posted as soon as they can be written up.

Suppose that $G$ is an abelian group of order $2^n$. Determine (with proof) how many elements of order $2$ are in $G$; your answer should be expressed in terms of the number of summands in the primary decomposition of $G$.
For a finite group $G$, the exponent of $G$ is defined to be the smallest positive integer $k$ so that for all $g \in G$ we have $g^k = e$. For each of the possible (isomorphism classes of) abelian groups of order $100$, compute the exponent of the group. Make sure to prove your claims.
List (with proof) all the (isomorphism classes of) abelian groups of order $42917875$.

Here are the solutions to this assignment.

Assignment 14 (due Friday, Dec 8 at 4pm)

Part A

Let $F(\mathbb{R},\mathbb{R})$ be the set of all functions with domain and codomain $\mathbb{R}$. (For example, the function $f: \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2$ is an element of $F(\mathbb{R},\mathbb{R})$.)
We'll define addition on $F(\mathbb{R},\mathbb{R})$ by letting $f+g$ be the function given by $(f+g)(x) = f(x) + g(x)$, and we'll define multiplication by letting $fg$ be the function given by $(fg)(x) = f(x)g(x)$. With operations defined in this way, $F(\mathbb{R},\mathbb{R})$ is a ring. (You don't have to prove this fact.)
1. What is the additive identity in $F(\mathbb{R},\mathbb{R})$? What is the multiplicative identity in $F(\mathbb{R},\mathbb{R})$? (Include justifications for your responses, and remember: these elements are in $F(\mathbb{R},\mathbb{R})$, so they'll be functions.)
2. Characterize the functions in $U(F(\mathbb{R},\mathbb{R}))$ (i.e., what is the precise property an element from $F(\mathbb{R},\mathbb{R})$ must satisfy in order for it to be invertible?). Prove that every nonzero element in $F(\mathbb{R},\mathbb{R})$ is either a unit or a zero divisor.
[N.B.: Just to be clear, to say that $f$ and $g$ are equal as elements of $F(\mathbb{R},\mathbb{R})$ means that for every $x \in \mathbb{R}$ we have $f(x) = g(x)$; it is essential that one states the "for all $x \in \mathbb{R}$" when asserting that two functions are the same, since two functions can agree on some proper subset of $\mathbb{R}$ and still be distinct. Indeed, two functions could agree at all but one $x \in \mathbb{R}$, and yet they'd still be different functions!]
Suppose that $a$ and $b$ are elements of some commutative ring $R$. If $a \in U(R)$ and $b^2 = 0$, prove that $a+b \in U(R)$.
Suppose that $R$ is a ring. Let $U(R)$ be the set of units of $R$, and let $ZD(R)$ be the set of zero divisors of $R$. Prove that $U(R) \cap ZD(R) = \emptyset$.

Part B

Let $R$ be the set $\{a+bi: a,b \in \mathbb{Z}_3\}$ endowed with the operations $$(a+bi)+(c+di) = (a+c)+(b+d)i$$ $$(a+bi)(c+di) = (ac-bd)+(ad+bc)i.$$ It is a fact (that you don't have to prove) that $R$ is a commutative ring with these operations. The zero element in this ring is $[0]_3+[0]_3i$, and the multiplicative identity is $[1]_3+[0]_3i$. [You don't have to check these facts.]
1. Write out the multiplication table for $R$. Feel free to suppress the bracket notation to make things easier to write. (For instance, you can write $0+0i$ instead of $[0]_3+[0]_3i$.) You don't need to include justification for this part of the problem; just do the calculations.
2. List all elements that are in $U(R)$. (Be sure to justify your response.)
3. In class we saw that $U(R)$ is a group under the operation of multiplication. Since we're told that $R$ is commutative, this means that $U(R)$ is an abelian group. Of course, since $|R|< \infty$, we have that $U(R)$ is a finite abelian group. It follows, then, that $U(R)$ has a unique primary decomposition, as provided by the fundamental theorem of finite abelian groups. What is this primary decomposition? Justify your assertion.
Let $R$ be the ring whose set is $\{a+bi:a,b \in \mathbb{Z}_5\}$, with the operations $$(a+bi)+(c+di) = (a+c)+(b+d)i$$ $$(a+bi)(c+di) = (ac-bd)+(ad+bc)i.$$ It is a fact (that you don't. have to prove) that $R$ is a ring. Prove that $R$ is not an integral domain.
When $R$ is a ring, we define $R[x]$ to be the set of polynomials in $x$ with coefficients in $R$. This means that for a given element $f \in R[x]$, there exists an infinite sequence of ring elements $a_0,a_1,a_2,\cdots \in R$ whose terms eventually equal $0_R$ so that $f=a_0+a_1x+a_2x^2+\cdots$. (To say that the sequence $a_0,a_1,a_2,\cdots$ eventually equals $0_R$ means that there exists some $N \in \mathbb{N}$ so that for all $n \geq N$ we have $a_n=0_R$.) For any given $i \in \mathbb{N}$, we say that the coefficient of $x^i$ in $f$ is the element $a_i$; we write $\text{coef}_i(f)=a_i$. Two elements $f,g \in R[x]$ are equal if and only if for every $i \in \mathbb{N}$ we have $\text{coef}_i(f)=\text{coef}_i(g)$.
To turn $R[x]$ into a ring, we need addition and multiplication operations. We define $f+g$ to be the polynomial for which $$\text{coef}_i(f+g)=\text{coef}_i(f)+\text{coef}_i(g).$$ We define $fg$ to be the polynomial for which $$\text{coef}_i(fg)=\sum_{k=0}^i \text{coef}_k(f)\text{coef}_{i-k}(g).$$ (These might sound like fancy operations, but they are precisely the way we do the "usual" polynomial addition and multiplication.)
It is a fact (that you don't have to check) that $R[x]$ with these operations is a ring.
Prove that if $R$ has no zero divisors, then $R[x]$ has no zero divisors. [Hint: you need to do show that the product of any two nonzero polynomials is again a nonzero polynomial. If you take a product of two nonzero polynomials, what coefficient can you guarantee won't be $0$ in the product? You might want to do some experiments to get some intuition.]

Here are the solutions to this assignment.

OPTIONAL Assignment 15 (due Wednesday, Dec 13 at 4pm)

Note that this pset is optional. This means you can submit it if you want, but you are not obliged to do so. If you choose to submit the assignment, I'll include your grade as a part of your overall homework average if and only if it doing so improves your homework average.

Part A

Suppose that $R$ is a commutative ring, and $r \in R$ is given. The annihilator of $r$ --- written $\textrm{ann}(r)$ --- is the set $$\textrm{ann}(r) = \{x \in R: xr = 0\}.$$ Prove that $\textrm{ann}(r)$ is an ideal of $R$.
An integral domain $R$ is called a Euclidean domain if there is a function $v$ (known as a "valuation") on the nonzero elements of $R$ to the nonnegative integers that satisfies (1) $v(a) \leq v(ab)$ for all nonzero $a,b \in R$; and (2) if $a,b \in R$ with $b \neq 0$, then there exist elements $q$ and $r$ in $R$ such that $a = bq+r$, where either $r = 0_R$ or $v(r) < v(b)$.
Prove that if $R$ is a Euclidean domain and $I$ is a nontrivial ideal, then $I = \langle i \rangle$ for some $i \in I$.
[Hint: argue that there exists an element $i \in I$ with minimal valuation; then prove this element generates $I$. To do this, suppose you had some element $\hat i \in I$ with $\hat i \not \in \langle i \rangle$. What does $R$ being a Euclidean domain then tell you about how you can write an equation involving $\hat i$ and $i$?]
Recall that $\mathbb{Z}_2[x]$ is the set of polynomials with coefficients in $\mathbb{Z}_2$. (We will write elements from $\mathbb{Z}_2$ without the bracket notation for the sake of simplicity. So, for instance, $x+1 = x-1$ in $\mathbb{Z}_2[x]$, since $1=-1$ in $\mathbb{Z}_2$.) It is a fact (that you don't need to prove here) that since $\mathbb{Z}_2$ is a field, then the degree function is a valuation on $\mathbb{Z}_2[x]$. Let $I = (x^3+x+1)$.
1. Prove that $\mathbb{Z}_2[x]/I$ has eight elements.
  [Hint: argue that every element in the quotient is represented by a polynomial of "small" degree. The fact that we have a valuation will be quite useful!]
2. Compute the multiplicative inverse of every nonzero element.
  [Hint: if you can argue that $(f(x)+I)(g(x)+I) = 1+I$, then you'll have shown that $f(x) = g(x)^{-1}$ and that $g(x) = f(x)^{-1}$.]
($\star$) Determine all ring homomorphisms from $\mathbb{Z}\oplus\mathbb{Z}$ to itself.

Here are the solutions to this assignment.

An integral domain $R$ is called a principle ideal domain (aka, a PID) if for every ideal $I$ within $R$ there exists some $i \in I$ with $\langle i \rangle = I$. Prove that $\mathbb{Z}$ is a PID.
Let $\mathbb{F}$ be a field, and consider the ring of polynomials $\mathbb{F}[x]$ with coefficients in $\mathbb{F}$.
1. Argue that the degree function $\deg:\mathbb{F}[x]\setminus\{0\} \to \mathbb{N}\cup \{0\}$ makes $\mathbb{F}[x]$ into a Euclidean domain. [See assignment 13 for the definition of Euclidean domain. Furthermore, recall that if $f$ is a polynomial of the form $f = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$ and $a_n \neq 0$, then $\deg(f) = n$.]
2. Find a specific example which shows that the degree function on $\mathbb{Z}[x]$ does not satisfy the required properties to be a valuation on $\mathbb{Z}[x]$.
  (Note: one could argue that the degree function is not a valuation far more abstractly, as follows: if it were a valuation then $\mathbb{Z}[x]$ would be a Euclidean domain, and (by the previous problem) therefore a PID. But we stated in class that $\langle x,2 \rangle$ is not a principle ideal, and so $\mathbb{Z}[x]$ is not a PID. This argument has the benefit of not only showing that the degree function isn't a valuation, but that NO function is a valuation on $\mathbb{Z}[x]$.)
3. Suppose that $n$ is composite. Find a specific example which shows that the degree function on $\mathbb{Z}_n[x]$ does not satisfy the required properties to be a valuation on $\mathbb{Z}_n[x]$.

Here are the solutions to this assignment.