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

\usepackage{color}

\usepackage{tikz}

% 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.5in}
\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.35in}{\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 $11^{\mathrm{th}}$, 2015}

\vspace{0.3in}

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

\vspace{0.2in}

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

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

%\vspace{-0.05in}

          \begin{enumerate}[1:]
             \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.1in}

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

\vspace{0.1in}

           \item Commutivity:  $\forall x,y \in G$, $xy = yx$

\vspace{0.05in}
          \end{enumerate}   
      
   \item Let $G = \mathbb{Z}_{\geq 0}$ be the set of non-negative integers. It can be shown that $x \star y = \mbox{max} \{ x,y \}$ (example: $3 \star 1 = \mbox{max} \{3,1\} = 3$)  is an associative, commutative (closed) binary operation on $G$ with identity $0$. However, $G$ is not a group. Why? [Use a concrete counterexample.]

\vspace{0.05in}

The only thing that keeps $G$ from being a group is its lack of {\it inverses}. Notice that $2 \in \mathbb{Z}_{\geq 0}$ but $\mbox{max} \{ 2, x \} \ne 0$  for all $x \in \mathbb{Z}_{\geq 0}$  since $\mbox{max}\{2,x\}$ $\ne 0$. Thus $2$ has no inverse. In fact, the only element that {\it does} have an inverse is $0$ itself: $\mbox{max}\{0,0\}=0$. 

\vspace{0.05in}

{\it Note:} A non-empty set equipped with a closed associative binary operation which also has an identity is called a {\it monoid}. Thus even though $G$ isn't a group, it is a {\it commutative monoid}.

\vspace{0.1in} 

   \item Let $G = \mathbb{R} - \mathbb{Q} = \{ x \in \mathbb{R} \;|\; x \mbox{ is irrational }\}$. Prove $G$ is {\bf not} a group under addition.

\vspace{0.05in}

There are several ways to see that $G$ is not a group. For example: $G$ is not closed under addition. Notice that $\pm\sqrt2 \in G$  but $\sqrt2 + (-\sqrt2) = 0 \notin G$. 

Alternatively, $G$ isn't a group since it has no identity. $0$ would be the identity, but $0$ is rational (not irrational). Since $0 \not\in G$, $G$ has no identity!

\vspace{0.1in} 

\end{enumerate}

\noindent {\bf\large 2. (20 points)} Some modular arithmetic.

   \begin{enumerate}[(a)]

      \item What is the inverse of $10$ in the group $\mathbb{Z}_{15}$? What operation makes $\mathbb{Z}_{15}$ a group?

\vspace{0.05in}
      
		Addition makes this an abelian group. The inverse of 10 in $\mathbb{Z}_{15}$ is $-10=5$. 

\vspace{0.05in}

      \item Is $10$ an element of $U(15)$? If not, why not? If so, why so \& what is its inverse?

\vspace{0.05in}

		No,  $10\notin U(5)$  since $\mathrm{gcd}(10,15) = 5 \neq 1$. 

\vspace{0.05in}

      \item List all of the {\it distinct} cyclic subgroups, $\langle x \rangle$, of $\mathbb{Z}_{15}$. 
			
\vspace{0.05in}

            Notice that 1, 3, 5, 15 are the divisors of 15. We get a unique subgroup associated with each of these numbers:
		
	\begin{itemize}
	\item $\langle 0\rangle = \{0\}$
            
	\item $\langle 5 \rangle = \{ 0,5,10\}$
            
	\item $\langle 3 \rangle=\{0,3,6,9,12\}$
            
	\item $\langle 1 \rangle = \{0,1,2,\dots,14\} = \mathbb{Z}_{15} $
	\end{itemize}

      \item What is the order of $10$ in $\mathbb{Z}_{15}$?
		
\vspace{0.05in}

        $(1)10 = 10$ , $(2)10 = 10+10=5$ , $(3)10 = 10+10+10=0$ and therefore $|10| = 3$  
        
        Alternatively, notice that $\langle 10 \rangle =\mbox\{0,5,10\}$  and so $|10| =|\langle 10 \rangle| = 3$

\vspace{0.05in}

      \item Draw the subgroup lattice of $\mathbb{Z}_{15}$.

\vspace{-0.25in}

\begin{center}
\begin{minipage}{2in}
\begin{tikzpicture}[node distance=1cm]
 % 15's divisibility lattice
 \node(grp){15};
 \node(placeholder)[below of = grp]{ };   % blank space
 \node(sg5)[left of = placeholder]{3};
 \node(sg3)[right of = placeholder]{5};
 \node(trivial)[below of = placeholder]{1};

 % Lines between 1st and 2nd rows
 \draw(grp)--(sg5);
 \draw(grp)--(sg3);
 % Lines between 2nd and 3rd rows
 \draw(sg5)--(trivial);
 \draw(sg3)--(trivial);
\end{tikzpicture}

\vspace{0.15in}

\force \hspace{-0.15in} Divisibility Lattice
\end{minipage}
\begin{minipage}{3in}
\begin{tikzpicture}[node distance=2cm]
 % Z_15's subgroup lattice
 \node(grp){$\mathbb{Z}_{15} = \langle 1 \rangle$};
 \node(placeholder)[below of = grp]{ };   % blank space
 \node(sg5)[left of = placeholder]{$\langle 5 \rangle = \{ 0,5,10 \}$};
 \node(sg3)[right of = placeholder]{$\langle 3 \rangle = \{0,3,6,9,12 \}$};
 \node(trivial)[below of = placeholder]{$\langle 0 \rangle = \{ 0 \}$};

 % Lines between 1st and 2nd rows
 \draw(grp)--(sg5);
 \draw(grp)--(sg3);
 % Lines between 2nd and 3rd rows
 \draw(sg5)--(trivial);
 \draw(sg3)--(trivial);
\end{tikzpicture}

\vspace{0.15in}

\force \hspace{0.65in} Subgroup Lattice
\end{minipage}
\end{center}

\vspace{-0.2in}

\end{enumerate}

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

\begin{enumerate}[(a)]

   \item Draw a Cayley table for $U(5)$.

\vspace{0.05in}

\force \hspace*{1in}
\begin{minipage}{3in}
\begin{tabular}{c||cccc}
  & 1 & 2 & 3 & 4 \\ \hline\hline
1 & 1 & 2 & 3 & 4 \\
2 & 2 & 4 & 1 & 3 \\
3 & 3 & 1 & 4 & 2 \\
4 & 4 & 3 & 2 & 1
\end{tabular}
\end{minipage}

\vspace{0.05in}

   \item List the elements of $U(5)$. Then find their {\bf order}s and the list the elements in {\bf cyclic subgroup} generated by that element. [{\it Note:} There may be more spaces than you need.]

\vspace{0.1in}

\force %\hspace{-0.45in}
\begin{tabular}{c||c|c|c|c|c|c|} 
$x=$ & 1 & 2 & 3 & 4 \\ \hline\hline
$|x|=$ & 1 & 4 & 4 & 2 \large\strut \\ \hline
$\langle x \rangle=$ & $\{ 1 \}$ &  $\{1,2,3,4\}$ &  $\{1,2,3,4\}$ &  $\{1,4\}$ \large\strut \\ \hline
\end{tabular}

\vspace{0.05in}

%   \item Is $U(8)$ cyclic? \qquad {\bf\Large Yes \quad / \quad No} \qquad (Circle the correct answer.)

%\vspace{0.15in}

   \item Find $\displaystyle \left\langle A \right\rangle = \left\langle \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} \right\rangle$ in $\mathrm{GL}_2(\mathbb{Z}_6)$. What is the order of $A$? What is $A^{-1}$?

\vspace{0.05in}

$A^2=\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1&2\\0&1\end{bmatrix}=\begin{bmatrix}1&4\\0&1\end{bmatrix}$ \quad
$A^3=A^2A=\begin{bmatrix} 1&4\\0&1\end{bmatrix} \begin{bmatrix} 1&2\\0&1 \end{bmatrix}=\begin{bmatrix} 1&0\\0&1\end{bmatrix}$ 

\vspace{0.05in}

Thus the cyclic subgroup generated by $A$ is $\langle A \rangle =\{I, A, A^2\}=\left\{\begin{bmatrix} 1&0\\0&1 \end{bmatrix}, \begin{bmatrix} 1&2\\0&1 \end{bmatrix},\begin{bmatrix} 1&4\\0&1 \end{bmatrix}\right\}$ and so $|A|=3$.

To find $A^{-1}$, note that the order of A is 3, so $A^{-1}=A^2=\begin{bmatrix} 1&4\\0&1 \end{bmatrix}$

It can also be found directly:

$A^{-1}=(\mathrm{det}(A))^{-1} \begin{bmatrix} 1&-2\\0&1 \end{bmatrix}=1^{-1} \begin{bmatrix} 1&-2\\0&1 \end{bmatrix}=\begin{bmatrix} 1&4\\0&1 \end{bmatrix}$

\vspace{0.05in}

   \item \sout{Find $99^{-1}$ mod 123 using} {\color{red}Run} the extended Euclidean algorithm {\color{red}on 99 and 123}.

\vspace{0.05in}

Note that 123 divided by 99 is 1 with a remainder of 24. Then 99 divided by 24 is 4 with a remainder of 3. Finally, 24 divided by 3 is 8 with no remainder. Thus the last non-zero remainder is 3 so that $\mathrm{gcd}(99,123)=3$.

We have $123=(1)(99)+24$ and $99=(4)24+3$. Thus $3=(1)99+(-4)24$ and so $3=(1)99+(-4)[123+(-1)99]$. Therefore,
\fbox{$3=(5)99+(-4)123$}.

Of course, the original problem (computing $99^{-1}$ mod 123) is impossible since 99 and 123 aren't relatively prime. $99 \not\in U(123)$ so $99^{-1}$ (mod 123) does not exist!

\end{enumerate}

\newpage
\noindent {\bf\large 4. (15 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_{10}$ to simplify $x^{-3}y^2x^{15}yx^4y^{-22}$
      
\vspace{0.05in}
      
Recall $y's$ exponents ``work mod 2'', $x's$ ``work mod 10''. Also, $yx=x^{-1}y$  and $xy=yx^{-1}$. Therefore,
        
$$x^{-3}y^{2}x^{15}yx^{4}y^{-22}=x^{-3}x^{15}yx^{4}=x^{12}x^{-4}y=x^{8}y$$
        
   \vspace{-0.1in}
   
   \item Fill in the Cayley table for $D_3$:
   
\force \hspace{1in}
\begin{minipage}{3in}
   \begin{tabular}{c||c|c|c|c|c|c|} 
              &  $1$ & $x$ & $x^2$ & $y$ & $xy$ & $x^2y$ \\ \hline \hline  
       $1$ & $1$ & $x$ & $x^2$ & $y$ & $xy$ & $x^2y$ {\Large\strut} \\ \hline 
       $x$ & $x$ & $x^2$ &  $1$ & $xy$ & $x^2y$ & $y$ {\Large\strut} \\ \hline
       $x^2$ & $x^2$ & $1$ &  $x$ & $x^2y$ & $y$ & $xy$ {\Large\strut} \\ \hline
       $y$ & $y$ & $x^2y$ &  $xy$ & $1$ & $x^2$ & $x$ {\Large\strut} \\ \hline
       $xy$ & $xy$ & $y$ &  $x^2y$ & $x$ & $1$ & $x^2$ {\Large\strut} \\ \hline
       $x^2y$ & $x^2y$ & $xy$ &  $y$ & $x^2$ & $x$ & $1$ {\Large\strut} \\ \hline
   \end{tabular}
\end{minipage} 

  \vspace{0.1in}
  
 \item Do the {\bf reflections} form a subgroup of $D_3$? If so, why? If not, why not?
 
\vspace{0.05in}
 
No. The set of reflections are not closed under function composition. For example: $y^2=1$ but $1$ is not a reflection. In fact, the reflections {\it never} form a subgroup since a reflection composed with a reflection is a rotation (closure fails in an extreme way). Alternatively, we could see that the reflections don't form a subgroup since they lack an identity (1 is a rotation not a reflection).
\end{enumerate}

\vspace{0.05in}

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

\begin{enumerate}[(a)]
   \item Choose one of the following:
   \begin{enumerate}[I.] 
   \item Suppose that $(ab)^{-1}=a^{-1}b^{-1}$ for all $a,b \in G$. Prove that $G$ is abelian.
   
\vspace{0.05in}

   	Suppose $a,b \in G$ .  Then $(ab)^{-1} = b^{-1} a^{-1}$.  Therefore $b^{-1}a^{-1}=a^{-1}b^{-1}$ since we have assumed $(ab)^{-1}=a^{-1}b^{-1}$.  Thus $ab(b^{-1}  a^{-1})=ab(a^{-1}b^{-1})$. So that $e=aba^{-1}b^{-1}$.  Therefore, $e(ba)=aba^{-1}b^{-1}(ba)$.
 Thus $ba=ab$ and so $G$ is abelian.

Alternatively, we have $a^{-1}b^{-1}=(ab)^{-1}=b^{-1}a^{-1}$ so $(a^{-1})^{-1}(b^{-1})^{-1}=(a^{-1}b^{-1})^{-1}=(b^{-1})^{-1}(a^{-1})^{-1}$ thus $ab=ba$.

\vspace{0.05in}
   
   \item Let $G$ be a group and $g \in G$. Prove that $\langle g \rangle = \langle g^{-1} \rangle$ \quad (i.e. $g$ and its inverse generate the same cyclic subgroup).
  
   		 $$\langle g \rangle =  \mbox\{g^k \;|\;   k\in \mathbb{Z}\}  = \mbox\{g^{-k} \;|\; -k \in \mathbb{Z}\} = \mbox\{(g^{-1})^k \;|\; k \in \mathbb{Z} \} = \langle g^{-1} \rangle$$
   
   \end{enumerate}   

   \item Choose one of the following:  \qquad (You {\bf must} use a subgroup test in your proof.)
   \begin{enumerate}[I.] 
   \item Prove that $H = 6\mathbb{Z} = \{ m \in \mathbb{Z} \;|\; m \mbox{ is a multiple of 6 }\}$ is a subgroup of $\mathbb{Z}$.

\vspace{0.05in}

  		 Note $0 \in H$   (it is a nonempty subset of $\mathbb{Z}$).
    	Suppose $x,y \in H$.  Then there is some $k, \ell \in \mathbb{Z}$  such that $x = 6k$   and    $y = 6\ell$.
		So $x + y = 6k +6\ell = 6(k+\ell) \in H$       since $k+\ell \in \mathbb{Z}$  .
        Also, $-x=-6k=6(-k) \in H$       since   $-k\in\mathbb{Z}$
        Therefore, $H$ is closed under addition and inverses, and thus $H$ is a subgroup by the 2-step test.

\vspace{0.05in}


   \item Prove that $K = \left\{ \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix} \;\Bigg|\; a \in \mathbb{R} \right\}$ is a subgroup of $\mathrm{SL}_2(\mathbb{R})$.
  
\vspace{0.05in}  
  
Clearly $K$ is a non-empty subset of $\mathrm{GL}_2(\mathbb{R})$ (notice that elements of $K$ have determinant 1, so they are invertible matrices). 

Suppose $\displaystyle \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix},  \begin{bmatrix} 1 & b \\ 0 & 1 \end{bmatrix} \in K$.  Then $\displaystyle \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & b \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & a+b \\ 0 & 1 \end{bmatrix} \in K$. Also, $\begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & -a \\ 1 & 0 \end{bmatrix} \in K$. Thus $K$ is closed under matrix multiplication and inverses, so by the 2-step subgroup test, $K$ is a subgroup of $\mathrm{GL}_2(\mathbb{R})$.
        
\end{enumerate}
   
\end{enumerate}


\end{document}