\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{graphicx}

\usepackage{tikz}

\usepackage{color}

% for \sout to strike through text
\usepackage{ulem}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.50in}
\setlength{\evensidemargin}{-0.50in}
\setlength{\topmargin}{-0.50in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.4in}
\setlength{\textwidth}{7.5in}

\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}
\newcommand{\divides}{\,\Big|\,}
\newcommand{\myspace}{\mbox{\parbox[c][0.35in]{0.3in}{\hfill}}}
\newcommand{\myspacea}{\mbox{\parbox[c][0.35in]{0.65in}{\hfill}}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}

\newcommand{\force}{{$\mbox{\;}$}}

\begin{document}

%\pagestyle{empty}

\noindent
\parbox{2in}{\bf Math 3110} 
\hfill {\Large \bf Test \#1} \hfill
\parbox{2in}{\bf \hfill February $9^{\mathrm{th}}$, 2022}

\vspace{0.15in}

\noindent {\large\bf Name:} \underline{\Large\color{red}\sc\qquad Answer Key \qquad} \hfill {\bf Be sure to show your work!}

\vspace{0.1in}

\noindent {\bf\large 1. (20 points)} Definition and Basics

\begin{enumerate}[(a)]
   \item Suppose that $G$ is a non-empty set equipped an operation. What 4 things do I need to check to see if $G$ is a group? 

          \begin{enumerate}[1:] \setlength\itemsep{0em}
             \item Closure: $\forall x,y \in G$, we have $xy \in G$

             \item Associativity: $\forall x,y,z \in G$, we have $(xy)z = x(yz)$

             \item Identity: $\exists e \in G$  such that $\forall x \in G$, $xe = x = ex$

             \item Inverses:  $\forall x \in G$,  $\exists y \in G$ such that $xy = e = yx$

%\vspace{0.05in}

           \force\hspace{-0.35in} What additional property needs to hold for $G$ to be an {\bf Abelian} group?

%\vspace{0.05in}

           \item Commutivity:  $\forall x,y \in G$, $xy = yx$
\end{enumerate}   
      
   \item The closed interval $I=[-1,1]=\{x \in \mathbb{R} \;|\; -1 \leq x \leq 1 \}$ does not form a group under addition. Why?\\ \force\hfill [{\bf BE CONCRETE.}]

While associativity, identity (i.e., 0), and inverses (i.e., negations) all seem to check out, the real problem is that we lack closure. Notice that $1 \in I$ but $1+1 =2\not\in I$. Thus $I$ is not a group under addition because addition is not closed. 

   \item This same interval $I=[-1,1]$ does not form a group under multiplication either. Why? \force\hfill [{\bf BE CONCRETE.}]

Now closure is ok here. Associativity and identity (i.e., 1) also check out. However, inverses give us problems. For example, $0^{-1}=1/0$ just doesn't exist! Even discarding $0$, we still have a problem. Notice that $(1/2)^{-1}=2 \not\in I$, so $I$ is not closed under taking inverses. In any case, this is not a group because we lack closure under (multiplicative) inverses.

   \item Equip $\mathbb{Q}_{\not=0}$ (the non-zero rational numbers) with the operation of {\bf division}. Is $1$ an identity for this set equipped with this operation? Why or why not? \hfill [{\bf BE CONCRETE.}]

Once again we fail to have a group. In fact, associativity fails: $1/(2/3)=3/2$ whereas $(1/2)/3=1/6$. However, we are being asked about the identity axiom. Notice that $x/1=x$ for all $x\in \mathbb{Q}_{\not=0}$ so $1$ is a right identity. However, $1/x \not= x$ unless $x=\pm 1$. In particular, $1/2 \not= 2$. Therefore, $1$ is a right identity but it is not a left identity. Thus $1$ is not a (two-sided) identity for division.

\end{enumerate}

\noindent {\bf\large 2. (20 points)} Arithmetic mod 12. {\it Note:} The positive integers divisors of 12 are 1, 2, 3, 4, 6, and 12.

   \begin{enumerate}[(a)]
      \item Make a list of all of the cyclic subgroups of $\mathbb{Z}_{12}$ along with their contents (for example: $\langle 0 \rangle = \{0\}$).

As discussed in class, we have one subgroup per divisor of 12. Since there are 6 divisors, we will have 6 distinct (cyclic) subgroups. Although, we were not asked to, I will provide each distinct subgroup {\it  and} display {\it all} generators.

\begin{itemize}
\item $\langle 0 \rangle = \{ 0 \}$
\item $\langle 6 \rangle = \{ 0,6 \}$
\item $\langle 4 \rangle = \{ 0,4,8 \}$ \quad ($=\langle 8 \rangle$)
\item $\langle 3 \rangle = \{ 0,3,6,9 \}$ \quad ($=\langle 9 \rangle$)
\item $\langle 2 \rangle = \{ 0,2,4,6,8,10 \}$ \quad ($=\langle 10 \rangle$)
\item $\langle 1 \rangle = \{ 0,1,2,3,4,5,6,7,8,9,10,11 \}$ \quad ($=\langle 5 \rangle =\langle 7 \rangle =\langle 11 \rangle$)
\end{itemize}      


      \item Fill out the following table referring to the operations of addition and multiplication modulo 12:
      
      {\it Note:} Just put an {\large\bf X} if something is undefined / does not exist.

%      \hspace{-0.75in}      
      \begin{tabular}{|r|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
                     Element $x=$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \large\strut \\ \hline
      Additive Inverse $-x=$ & 0 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \large\strut \\ \hline
      Order (in $\mathbb{Z}_{12}$) $|x|=$ & 1 & 12 & 6 & 4 & 3 & 12 & 2 & 12 & 3 & 4 & 6 & 12 \large\strut \\ \hline 
      Multiplicative Inverse $x^{-1}=$ & {\large\bf X} & 1 & {\large\bf X} & {\large\bf X} & {\large\bf X} & 5 & {\large\bf X} & 7 & {\large\bf X} & {\large\bf X} & {\large\bf X} & 11 \Large\strut \\ \hline
      Order (in $U(12)$) $|x|=$ & {\large\bf X} & 1 & {\large\bf X} & {\large\bf X} & {\large\bf X} & 2 & {\large\bf X} & 2 & {\large\bf X} & {\large\bf X} & {\large\bf X} & 2 \Large\strut \\ \hline
      \end{tabular}

      \item Compute $5^{-2}(1-4)+8$ mod $12$ or explain why this is undefined.

Notice that $5^{-1}=5$ and so $5^{-2}=(5^{-1})^2=5^2=1$. Thus $5^{-2}(1-4)+8=1(-3)+8=$ \fbox{5}.

      \item Compute $2^{-5}(1-4)-8$ mod $12$ or explain why this is undefined.
      
Notice that $2^{-1}$ does not exist (since $\mathrm{gcd}(2,12)=2\not=1$). Thus this is \fbox{undefined}.

\end{enumerate}

\noindent {\bf\large 3. (20 points)} More Modular Arithmetic.

\begin{enumerate}[(a)]

      \item List the elements of \qquad $U(9)=\{ x \in \mathbb{Z}_9 \;|\; \mathrm{gcd}(x,9)=1 \} = \{1,2,4,5,7,8\}$

Notice that $1^1=1$;\quad $2^1=2$, $2^2=4$, $2^3=8$, $2^4=7$, $2^5=5$, $2^6=1$;\quad $4^1=4$, $4^2=7$, $4^3=1$;\quad $5^1=5$, $5^2=7$, $5^3=8$, $5^4=4$, $5^5=2$, $5^6=1$;\quad $7^1=7$, $7^2=4$, $7^3=1$;\quad $8^1=8$, $8^2=1$. \qquad Of course, we could save time by noting that the identity (i.e., 1) always has order 1; inverses have the same order $6=|2|=|2^{-1}|=|5|$ and $3=|4|=|4^{-1}|=|7|$; Arithmetic is easier when we swap out for smaller representatives like $8=-1$ so $8^2=(-1)^2=1$.
           
      \force \hspace*{0.45in} List each element's order: \underline{$|1|=1$, $|2|=6$, $|4|=3$, $|5|=6$, $|7|=3$, and $|8|=2$}
      
\vspace{0.05in}
      
      Is $U(9)$ cyclic (circle the correct answer)? \quad {\Large \fbox{Yes}} \quad since $\langle 2 \rangle = \{1,2,4,8,7,5\}=U(9)$ (also $=\langle 5\rangle$).

\vspace{0.05in}

Alternatively, we could just note that there are elements of order $|U(9)|=6$, so our group must be cyclic.

\vspace{0.05in}      

      \item Draw the subgroup lattice for $\mathbb{Z}_{77}$. [$77 = 7 \cdot 11$]

\vspace{-0.35in}

\force \hfill \hfill \hfill
\begin{tikzpicture}[node distance=1.5cm]
\node(77){$77$};
\node(11)[below right of = 77]{$11$};
\node(7)[below left of = 77]{$7$};
\node(1)[below right of = 7]{$1$};

\draw(77)--(11);
\draw(77)--(7);
\draw(11)--(1);
\draw(7)--(1);
\end{tikzpicture}
\qquad \qquad
\begin{tikzpicture}[node distance=1.5cm]
\node(77){$\mathbb{Z}_{77}=\langle 1 \rangle$};
\node(11)[below right of = 77]{$\langle 7 \rangle$};
\node(7)[below left of = 77]{$\langle 11 \rangle$};
\node(1)[below right of = 7]{$\langle 0 \rangle$};

\draw(77)--(11);
\draw(77)--(7);
\draw(11)--(1);
\draw(7)--(1);
\end{tikzpicture}
\hfill \force
   \item Find $10^{-1}$ mod 47 using the extended Euclidean algorithm [Don't just guess and check].

Divide $47$ by $10$ and get $47=(4)10+7$ so $7=(1)47+(-4)10$. Next, divide $10$ by $7$ and get $10=(1)7+3$ so $3=(1)10+(-1)7$. Next, divide $7$ by $3$ and get $7=(2)3+1$ so $1=(1)7+(-2)3$. Finally, divide $3$ by $1$ and get $3=(3)1+0$. Thus the last non-zero remainder is $1$ (i.e., $\mathrm{gcd}(47,10)=1$ so $10^{-1}$ mod $47$ does in fact exist).

Now run through our facts backwards. We have $1=(1)7+(-2)3$. Substitute in $3=(1)10+(-1)7$ for $3$ and get $1=(1)7+(-2)[(1)10+(-1)7]=(3)7+(-2)10$. Finally, substitute $7=(1)47+(-4)10$ for $7$ and get $1=(3)[(1)47+(-4)10]+(-2)10=(3)47+(-14)10$. Therefore, $10^{-1}=-14=$ \fbox{$33$} working mod 47.

\end{enumerate}

\noindent {\bf\large 4. (20 points)} Recall $D_n = \{1,x,\dots,x^{n-1},y,xy,\dots,x^{n-1}y \} = \langle x,y \;|\; x^n=1, y^2=1, (xy)^2=1 \rangle$.

\begin{enumerate}[(a)]
   \item Use the relations for $D_{9}$ to simplify $y^{-3}x^{14}y^{22}x^{-2}yx$.
      
Keep in mind that exponents of $x$ work mod 9 and exponents of $y$ work mod 2, so we immediately have: $yx^5\cdot 1\cdot x^{-2}yx$. This is $yx^3yx=x^{-3}yyx=x^{6}y^2x=x^6\cdot 1\cdot x =$ \fbox{$x^7$}.
   
   \item Fill out the following table for $D_4$.  
   
%      \hspace{-0.75in}      
      \begin{tabular}{|r|c|c|c|c|c|c|c|c|} \hline
      Element $g=$ & $1$ & $x$ & $x^2$ & $x^3$ & $y$ & $xy$ & $x^2y$ & $x^3y$ \Large\strut \\ \hline
      Inverse $g^{-1}=$ & $1$ & $x^3$ & $x^2$ & $x$ & $y$ & $xy$ & $x^2y$ & $x^3y$ \Large\strut \\ \hline
      Order $|g|=$ & 1 & 4 & 2 & 4 & 2 & 2 & 2 & 2 \Large\strut \\ \hline
      \end{tabular}
   
   
   \item What is $\langle x^8 \rangle$ in $D_{10}$?

Remember that exponents of $x$ work mod 10 in $D_{10}$. We compute powers of $x^8$ and find: $(x^8)^2=x^{16}=x^6$, $(x^8)^3=x^{24}=x^4$, $(x^8)^4=x^{32}=x^2$, and $(x^8)^5=x^{40}=1$. Thus \fbox{$\langle x^8 \rangle = \{ 1, x^2, x^4, x^6, x^8 \}$}. Alternatively, if we noticed $\langle x^8 \rangle = \langle (x^8)^{-1} \rangle = \langle x^2 \rangle$ (since elements and their inverses generate the same cyclic subgroup), this would have been an easier computation.   
  
   \item Fill in the following rows of the Cayley table for $D_5$:
  
%  \hspace*{-0.25in} 
   \begin{tabular}{c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|} 
              &  $1$ & $x$ & $x^2$ & $x^3$ & $x^4$ & $y$ & $xy$ & $x^2y$ & $x^3y$ & $x^4y$ \\ \hline \hline  
$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\ \hline
$x^4$ &  $x^4$ & $1$ & $x$ & $x^2$ & $x^3$ & $x^4y$ & $y$ & $xy$ & $x^2y$ & $x^3y$ \Large\strut \\ \hline \hline  
$y$ &  $y$ & $x^4y$ & $x^3y$ & $x^2y$ & $xy$ & $1$ & $x^4$ & $x^3$ & $x^2$ & $x$ \Large\strut \\ \hline \hline  
$\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\ \hline
   \end{tabular}
  
  For example, $x^4\cdot x^3y = x^7y = x^2y$ since exponents of $x$ work mod 5 in $D_5$. As another example, $y\cdot x^4=x^{-4}y=xy$.
 
 \item Is $H = \{ 1, y, xy \}$ a subgroup of $D_3$? Why or why not?

Non-empty {\it finite} subsets are subgroups if and only if they are closed under the operation. Notice that $xy\cdot y=xy^2=x \not\in H$, so \fbox{\large\bf No}, this is not a subgroup. 
 
\end{enumerate}

\noindent {\bf\large 5. (20 points)} Proofs!

\begin{enumerate}[(a)]
   \item Choose one of the following:  \qquad \underline{Assume $G$ is a group under multiplication with identity $1$.}
   \begin{enumerate}[I.] 
   \item Suppose that $(ab)^{-1}=a^{-1}b^{-1}$ for all $a,b \in G$. Prove that $G$ is Abelian.  

Let $a,b \in G$. Then by assumption $(a^{-1}b^{-1})^{-1}=(a^{-1})^{-1}(b^{-1})^{-1}$. By socks-shoes, the left hand side is $(b^{-1})^{-1}(a^{-1})^{-1}$. Therefore, we have $ba=ab$. Thus $G$ is Abelian.

Alternatively, we could take our assumption: $(ab)^{-1}=a^{-1}b^{-1}$ and multiply it on the left by $ab$ and on the right by $ba$. This gives us: $(ab)(ab)^{-1}ba=(ab)a^{-1}b^{-1}ba$ so that $1\cdot ba=aba^{-1}\cdot 1\cdot a$ so $ba=ab\cdot 1$ and thus $ba=ab$. Therefore, $G$ is Abelian.

   \item Suppose that $g \in G$. Prove that $|g|=|g^{-1}|$ (elements and their inverses have the same order).

Notice that $g^n=1$ if and only if $(g^n)^{-1}=1^{-1}$ which is $(g^{-1})^n=1$. Therefore, the same powers $n$ take both $g$ and $g^{-1}$ to the identity. Thus (if there is one) the same smallest positive power takes them back to the identity. Therefore, they have the same order.

Alternatively, $\langle g \rangle = \{ g^k \;|\; k \in \mathbb{Z}\} = \{ g^{-\ell} \;\; -\ell \in\mathbb{Z}\} = \{ (g^{-1})^\ell \;|\; \ell \in \mathbb{Z}\} = \langle g^{-1}\rangle$ since a number ranging over all integers means its negation ranges over all integers (and vice-versa). Finally, $|g|=|\langle g\rangle|=|\langle g^{-1}\rangle|=|g^{-1}|$.

   \end{enumerate}   
   

   \item Choose one of the following:  \qquad (You {\bf must} use a subgroup test in your proof.)
   \begin{enumerate}[I.] 
   \item Let $G$ be an Abelian group. Prove that $H = \{ g \in G \;|\; g^2=e\}$ is a subgroup of $G$.
   
   Notice that $e^2=e$ so $e \in H$ ($H$ is a non-empty subset of $G$). We check closures. Let $a,b \in H$ so that $a^2=e$ and $b^2=e$. Notice $(ab)^2=abab=aabb=a^2b^2=ee=e$ (we used commutativity -- $G$ is Abelian -- to get the second equality). Thus $ab \in H$. Notice that since $a^2=e$, we have $a^{-1}=a \in H$. {}[Alternatively, $(a^{-1})^2=(a^2)^{-1}=e^{-1}=e$. Thus $a^{-1} \in H$.] Therefore, $H$ is closed under the operation and inverses. Thus $H$ is a subgroup of $G$.
   
   We note that if $G$ is not Abelian, $H$ may fail to be a subgroup. For example, in $D_3$, $H$ would be the set of reflections. These are not closed under the operation.
   
   \item Prove that $K = \left\{ \begin{bmatrix} a & a \\ 0 & 2b \end{bmatrix} \;\Bigg|\; a,b \in \mathbb{R} \right\}$ is a subgroup of $\mathbb{R}^{2\times 2}$.\\
   \force\hfill {}[{\it Caution:} What operation makes the set of {\bf all} $2 \times 2$ matrices a group?]
   
   Notice that the zero matrix belongs to $K$ so it is non-empty. Also, the zero matrix belongs to $\mathbb{R}^{2\times 2}$. This reminds us that our operation is addition of matrices (not multiplication). Let $A,B \in K$. Say $A =\begin{bmatrix} a & a \\ 0 & 2b \end{bmatrix}$ and $B=\begin{bmatrix} x & x \\ 0 & 2y \end{bmatrix}$ for some $a,b,x,y \in \mathbb{R}$. Then $A+B = \begin{bmatrix} a+x & a+x \\ 0 & 2(b+y) \end{bmatrix} \in K$ (since $a+x,b+y \in \mathbb{R}$ and $A+B$ has the right form to belong to $K$). Likewise, $-A = \begin{bmatrix} -a & -a \\ 0 & 2(-b) \end{bmatrix} \in K$ (again since $-a,-b \in \mathbb{R}$ and $-A$ has the right form to belong to $K$). Therefore, $K$ is closed under addition and negation (i.e., inverses). Thus $K$ is a subgroup of $\mathbb{R}^{2\times 2}$.
   
   \end{enumerate}
   
   
   


\end{enumerate}


\end{document}


