Section 1 Problem Set 1

Due: Friday March 26, 5:00PM CST.

You should upload your assignment under the PS1 link on Moodle.
You can hand write your solutions and scan them, or typeset them in R or LaTex. But you should upload the assignment in a single PDF or a single HTML file.
Ideally, submit the problems in order, but if that is not possible, the problems should be clearly labeled.
You should justify all answers, unless the assignment is to compute something. Then you should clearly display your computed work.
All assignments will be out of 30 points. For example, this assignment has six 5-point problems.
Late work: assignments will be lowered by 10% each day they are late. The solution will be posted on Tuesday. From that point on, I will still accept assignment write-ups, but you can earn a maximum of half of the points.
Collaboration is encouraged. In fact, it has been shown that people who form study groups, and talk about assignments, learn more and perform better. However, you should write up your own work in your own words (blatent copying is not acceptable), and if you receive substantial help from a classmate, you should give that person credit in your write-up (no pentalty for this!).

1.1 Modular Multiplication

Make the multiplication tables of the following sets and determine which of them are groups under multiplication. You can do this by hand (encouraged to get the feel for it) or using the R commands in Modular Arithmetic.

$\{1,2,3\}$ using multiplication mod 4
$\{1,2,3,4\}$ using multiplication mod 5
$\{1,5,7,11\}$ using multiplication mod 12
$\{5,15,25,35\}$ using multiplication mod 40

1.2 Group of Units $U(n)$ mod n

Let $U(n) = \{1 \le k < n \mid 1 = \gcd(k,n) \}$. These are the elements of $\mathbb{Z}_n$ that are relatively prime to $n$. In this problem, we will explore this set and prove that it is a group. Notice: by definition $U(n)$ has the multiplicative identity 1, since $gcd(1,n) = 1$. And, multiplication mod n is associative. So, we need to make sure it is a binary operation on $U(n)$ and that $U(n)$ is closed under taking inverses.

Compute the sets $U(6),U(7),U(8)$.
Use the R-code in Modular Arithmetic to do the following (you can do it by hand if you prefer).
1. Make the multiplication tables of $\mathbb{Z}_8$ and $U(8)$ mod 8.
2. Make the multiplication table of $U(9)$.
3. Make the multiplication table of $U(14)$.
Show that if $a \in U(n)$ then $a$ has a multiplicative inverse in $U(n)$. Hint: use the Extended GCD from Chapter 0, the cyclic groups voicethread, and Modular Arithmetic.
Show that $U(n)$ is closed under multiplication. That is if $a, b \in U(n)$, then $ab \in U(n)$. This shows that multiplication mod $n$ is a binary operation on $U(n)$. Hint 1: if $a$ is invertible mod n and $b$ is invertible mod n, then must $ab$ be invertible mod $n$. Hint 2: think about your shoes and socks.
Are $U(8)$, $U(9)$, and/or $U(14)$ cyclic? Justify your answers.

1.3 Two-by-two mod 2

The group $GL_2(\mathbb{Z}_2)$ is the group of all invertible $2\times 2$ matrices with entries from $\mathbb{Z}_2 = \{0,1\}$ and all arithmetic done mod 2. That is, \[ GL_2(\mathbb{Z}_2) = \left\{ A=\begin{pmatrix} a & b \\ c & d \end{pmatrix} \mid a,b,c,d \in \{0,1\} \hbox{ and $A$ is invertible} \right\}. \] The operation is usual matrix multiplication with arithmetic done mod 2 so that: 0+0 = 0, 0+1 = 1+0 = 1, 1+1 = 0.

There are 16 matrices of this form (two choices 0 or 1 for each of the four matrix entries), determine which of these are invertible (you can use the determinant mod 2).
Let $A$ and $B$ be the matrices below \[ A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \qquad\hbox{and}\qquad B = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}. \] Show that every element in this group is of the form $A^i B^j$ for some powers $i$ and $j$ (these powers can be 0).
Since $BA$ is in the group, it must be equal to $A^i B^j$ for some $i$ and $j$. Find $i$ and $j$.

1.4 Outer Cancellation

A group $\mathsf{G}$ has the special property that for all $x,y,z \in G$, if $xy = zx$ then $y = z$. Prove that $\mathsf{G}$ is abelian.

1.5 Distributing Powers

Prove that for $a, b$ in a group $\mathsf{G}$ we have \[ (ab)^2=a^2b^2 \quad \hbox{ if and only if } \quad ab=ba. \]

1.6 Cyclic Subgroups

If $g \in \mathsf{G}$, then $\langle g \rangle \le \mathsf{G}$ is the smallest subgroup of $\mathsf{G}$ that contains $g$. We will show in class that \[ \begin{array}{rcll} \langle g \rangle &=& \{ g^k \mid k \in \mathbb{Z}\}, & \hbox{if $|g| = \infty$}.\\ \langle g \rangle &=& \{1, g, g^2, \ldots, g^{n-1}\}, \quad & \hbox{if $|g| = n$}.\\ \end{array} \] Compute the elements of the following cyclic subgroups.

$\langle 5 \rangle \le \mathbb{Z}$
$\langle 5 \rangle \le \mathbb{Z}_{30}$
$\langle 5 \rangle \le \mathbb{R}^\ast$
$\langle 5 \rangle \le U({28})$
$\langle (\frac{\sqrt{2}}{2} + \frac{\sqrt{2}}{2}i) \rangle \le \mathbb{C}^\ast$

MATH 376: Algebraic Structures