\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{ifthen}
\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.4in]{0.4in}{\hfill}}}
\begin{document}

\pagestyle{empty}

\noindent
\parbox{2in}{\bf Math 3110} 
\hfill {\Large \bf Test \#1} \hfill
\parbox{2in}{\bf \hfill September 30$^{\mbox{th}}$, 2009}

\vspace{0.3in}

\noindent {\large\bf Name:} \underline{\hskip 3.0 truein}\\
\hfill 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}/18 points)] Define a binary operation
   ``$\star$'' on $\mathbb{Z}$, as follows $x \star y = x+xy+y$ (for all $x,y\in\mathbb{Z}$).\\ 
   So, for example, $(-2) \star (-3) = (-2)+(-2)(-3)+(-3)=1$.
\begin{enumerate}[(a)]
      \item Show $\star$ is associative.

\vspace{1in}

      \item Show $0$ is the identity for $\star$.

\vspace{1in}

      \item Is the set of negative integers $\mathbb{Z}_{<0}$ closed with respect  to $\star$? Why or why not?

\vspace{1in}
   \end{enumerate}

   \item[\large 2. (\underline{\hskip 0.35 truein}/20 points)] Consider the set $S = \{ a,b,c,d,e,f,g \}$.
   Recall that $\mathcal{P}(S) = \{ A \,|\, A \subseteq S \}$ is the {\it power set} of $S$ (i.e. the set of all subsets).
\begin{enumerate}[(a)]
      \item Which of the following are true? ({\bf circle} true statements and {\bf cross out} false ones)
      
   \begin{enumerate}[i.]
   \item \quad $\{ a,b,c \} \in \mathcal{P}(S)$
   \vspace{0.1in}
      
   \item \quad $a,b,c \in \mathcal{P}(S)$
   \vspace{0.1in}

   \item \quad $\phi = \{ \} \in \mathcal{P}(S)$
   \vspace{0.1in}

   \item \quad $\phi = \{ \} \subset \mathcal{P}(S)$
   \vspace{0.1in}

   \item \quad $\{ a,b,c \} \subseteq \mathcal{P}(S)$
   \vspace{0.1in}

   \item \quad $\{ \{a,b\}, \{d,e,f\} \} \subseteq \mathcal{P}(S)$
   \vspace{0.1in}

   \end{enumerate}

      \item Define a relation on $\mathcal{P}(S)$ by $A$ is related to $B$ if and only if $A \subseteq B$. Is this an equivalence
                relation? Why or why not?
\end{enumerate}

\newpage
   \item[\large 3. (\underline{\hskip 0.35 truein}/22 points)] Let $f:A \rightarrow A$
   and $g:A \rightarrow A$ for some (non-empty) set $A$.
\begin{enumerate}[(a)]
      \item Suppose that $f$ and $g$ are both onto. Prove that $f \comp g$ is onto.

\vspace{4in}

      \item Let $h:\mathbb{Z} \rightarrow \mathbb{Z}$ where $\displaystyle{h(x)=\left\{ \begin{array}{cc} x/2 & x \mbox{ is even} \\ x & x \mbox{ is odd} \end{array}\right.}$. \\
            Is $h$ one-to-one? Is $h$ onto?

   \end{enumerate}

\newpage
   \item[\large 4. (\underline{\hskip 0.35 truein}/12 points)] Let $f:A \rightarrow B$. Also, let $S_1,S_2 \subseteq A$ and $T \subseteq B$. Prove {\bf one}
   of the following:
   \[  f(S_1 \cap S_2) \subseteq f(S_1) \cap f(S_2)  \qquad \qquad \mbox{\Large OR } \qquad \qquad f(f^{-1}(T)) \subseteq T \]
     
 \vspace{4in}
 
   \item[\large 5. (\underline{\hskip 0.35 truein}/12 points)] Prove by induction that $5$ divides $6^n-1$ for all positive integers $n$.\\
   {\bf YOU MUST USE INDUCTION.}
 
   
\newpage
   \item[\large 6. (\underline{\hskip 0.35 truein}/16 points)] Division and Euclid.
\begin{enumerate}[(a)]
      \item Let $a,b,c,d \in \mathbb{Z}$. Prove that if $\displaystyle{a \divides b}$ and 
            $\displaystyle{c \divides d}$, then $\displaystyle{ac \divides bd}$.

\vspace{3in}

      \item Use the Euclidean Algorithm to compute the $d = (96,42)$ (the GCD of 96 and 42).  Then use the Euclidean Algorithm (running it backwards)
                to find $x,y \in \mathbb{Z}$ such that $42x+96y=d$.

   \end{enumerate}

\end{description}
\end{document}
