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

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{8.9in}
\setlength{\textwidth}{6.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{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}

\begin{document}

\pagestyle{empty}

\noindent
\parbox{2in}{\bf Math 3110} 
\hfill {\Large \bf Test \#1} \hfill
\parbox{2in}{\bf \hfill February $22^{\mathrm{nd}}$, 2010}

\vspace{0.3in}

\noindent {\large\bf Name:} \underline{\hskip 3.0 truein}\\
Don't merely state answers, prove your statements. {\bf Be sure to show your work!}

\begin{description}
   \item[\large 1. (\underline{\hskip 0.35 truein}/10 points)] Let $S=\mathbb{R}-\{0\}$ (the set of non-zero reals).
   For $x,y \in S$, define $x \star y = x^{-1}y$. [Example: $5 \star 10 = 10/5 = 2$]
\begin{enumerate}[(a)]
   \item Is $S$ closed with respect to $\star$?

\vspace{4in}

   \item The operation $\star$ is {\bf not} associative. Give a example which shows this.

\end{enumerate}

\newpage
   \item[\large 2. (\underline{\hskip 0.35 truein}/15 points)] Here are 3 collections of subsets of $\mathbb{Z}$. 2 of these collections are
   {\bf not} partitions -- {\bf explain why they fail to be partitions}. 1 of these collections is a partition -- {\bf describe the corresponding equivalence relation}.
\begin{enumerate}[(a)]

   \item $\{-1,-2,-3,\dots \}$ and $\{ 1^2, 2^2, 3^2, 4^2, \dots \}$
   
\vspace{3in}   
   
   \item $\{\dots,-6,-3,0,3,6,9,\dots\}=\{3k \,|\, k \in \mathbb{Z} \}$,\\
            $\{\dots,-5,-2,1,4,7,\dots\}=\{3k+1 \,|\, k \in \mathbb{Z} \}$, and\\ 
            $\{\dots,-4,-1,2,5,8,\dots\}=\{3k+2 \,|\, k \in \mathbb{Z} \}$.

\vspace{3in}   

   \item $\{\dots,-3,-2,-1,0\}$ and $\{0,1,2,3,\dots \}$

\vspace{3in}

\end{enumerate}

\newpage
   \item[\large 3. (\underline{\hskip 0.35 truein}/15 points)] One-to-one and onto.
\begin{enumerate}[(a)]

   \item Let $f : A \rightarrow B$ and $g : B \rightarrow A$. Suppose that $g \circ f$ is bijective. Prove {\bf ONE} of the following:
   \begin{enumerate}[i.]
      \item $f$ is injective (i.e. one-to-one).
      \item $g$ is surjective (i.e. onto).

\vspace{4in}

   \end{enumerate}

   \item Let $h:\mathbb{Z} \rightarrow \mathbb{Z}$ be defined by $h(x)=2x$. Is $h$ one-to-one? Is $h$ onto?
             {\bf Prove your answers.}

\vspace{3in}

\end{enumerate}

\newpage
   \item[\large 4. (\underline{\hskip 0.35 truein}/20 points)] Quick Proofs
\begin{enumerate}[(a)]

   \item Using induction, show that $n < 2^n$ for all {\bf non-negative} integers $n$.
             {\it Hint:} $1+ 2^n \leq 2^n + 2^n$.\\ {\bf YOU MUST USE INDUCTION!}

\vspace{3.5in}

   \item Let $f:A \rightarrow B$ and $S_1,S_2 \subseteq A$. 
            Show that $f(S_1) \cup f(S_2) \subseteq f(S_1 \cup S_2)$.

\end{enumerate}

\newpage
   \item[\large 5. (\underline{\hskip 0.35 truein}/20 points)] Divisibility
\begin{enumerate}[(a)]

\item Use the Euclidean algorithm to find $(4,11)=d$ (i.e. GCD of 4 and 11). Then use your work to backtrack through the algorithm
          and find integers $x$ and $y$ such that $4x+11y=d$

\vspace{3in}

\item Suppose $ax+by=6$ for some integers $a,b,x,y$. What are the possible value(s) of $(a,b)$?

\vspace{1in}

\item Let $a,b,c \in \mathbb{Z}$ such that $a$ and $b$ are relatively prime, $a \,\Big| \, c$, and $b \,\Big|\, c$. Show that
$ab \,\Big|\, c$.

\end{enumerate}

\newpage
   \item[\large 6. (\underline{\hskip 0.35 truein}/20 points)] Workin' mod 6
\begin{enumerate}[(a)]

   \item Finish filling out the following addition and multiplication tables for $\mathbb{Z}_6$ (operations are addition and multiplication
   ``mod 6''):

\vspace{0.1in}

\noindent
\mbox{} \hspace{-0.6in}
\begin{tabular}{|c|||c|c|c|c|c|c|} 
\hline
 $+$ &  0  &  1 & 2 & 3 & 4 & 5 \\ \hline \hline \hline
0 & 0  &  1 & 2 & 3 & 4 & 5 \\ \hline 
1 &  1 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
2 &  2 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
3 &  3 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
4 &  4 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
5 &  5 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
\end{tabular} 
\hspace{0.2in}
\begin{tabular}{|c|||c|c|c|c|c|c|} 
\hline
 $\times$ &  0  &  1 & 2 & 3 & 4 & 5 \\ \hline \hline \hline
0 &  0  &  0 & 0 & 0 & 0 & 0 \\ \hline 
1 &  0  &  1 & 2 & 3 & 4 & 5 \\ \hline 
2 &  0  &  2 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
3 &  0  &  3 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
4 &  0  &  4 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
5 &  0  &  5 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline
\end{tabular} 

\vspace{0.1in}

   \item For each $x \in \mathbb{Z}_6$, either find $x^{-1}$ or write ``DNE'' (if the multiplicative inverse does not exist).
   
   \begin{tabular}{|l|l|l|l|l|l|} \hline
   \parbox[c][0.5in]{0.75in}{$0^{-1} = $} &
   \parbox[c][0.5in]{0.75in}{$1^{-1} = $} &
   \parbox[c][0.5in]{0.75in}{$2^{-1} = $} &
   \parbox[c][0.5in]{0.75in}{$3^{-1} = $} &
   \parbox[c][0.5in]{0.75in}{$4^{-1} = $} &
   \parbox[c][0.5in]{0.75in}{$5^{-1} = $}  \\ \hline
   \end{tabular}
   
\vspace{0.1in}

   \item For each $x \in \mathbb{Z}_6$, either find $-x$ or write ``DNE'' (if the additive inverse does not exist).
   
   \begin{tabular}{|l|l|l|l|l|l|} \hline
   \parbox[c][0.5in]{0.75in}{$-0 = $} &
   \parbox[c][0.5in]{0.75in}{$-1 = $} &
   \parbox[c][0.5in]{0.75in}{$-2 = $} &
   \parbox[c][0.5in]{0.75in}{$-3 = $} &
   \parbox[c][0.5in]{0.75in}{$-4 = $} &
   \parbox[c][0.5in]{0.75in}{$-5 = $}  \\ \hline
   \end{tabular}
   
\vspace{0.1in}

   \item Compute $2^{-1}(5-1)+3$ or explain why this is undefined.
   
\vspace{2in}
   
   \item Compute $5^{-1}(3+4)-2$ or explain why this is undefined.

\end{enumerate}

\end{description}

\end{document}
