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

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.35in}
\setlength{\evensidemargin}{-0.35in}
\setlength{\topmargin}{-0.6in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.8in}
\setlength{\textwidth}{7.2in}

\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{\color{red}\Large\sc Answer Key}\\
Don't merely state answers, prove your statements. {\bf Be sure to show your work!}

\vspace{0.2in}

\noindent
{\bf  \large 1. (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{0.1in}

Yes. Suppose that $x,y \in S$. This means that $x$ and $y$ are non-zero real numbers. Thus $x^{-1}=1/x$ is a non-zero real number
and so $x \star y = x^{-1}y$ is a non-zero real number (a non-zero real times a non-zero real is a non-zero real). Thus $x \star y \in S$.

\vspace{0.1in}

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

\vspace{0.1in}

To show $\star$ fails to be associative, we need to find a single example where associativity does not work. Let's try (somewhat randomly)
$3,2,1 \in S$. Then $(3 \star 2)\star 1 = (3^{-1}2)\star 1 = (2/3) \star 1 = (2/3)^{-1}1 = 3/2$ whereas $3 \star (2 \star 1) = 3 \star (2^{-1}1) = 3 \star (1/2) = 3^{-1}(1/2)=1/6$. Thus $(3 \star 2) \star 1 \not= 3 \star (2 \star 1)$. Thus $\star$ is not associative.

{\it Note:} In general, $x \star y = x^{-1}y=y/x$ so $x \star (y \star z) = x \star (z/y) = (1/x)(z/y) = z/(xy)$ whereas $(x \star y) \star z = (y/x) \star z = (x/y)z = (zx)/y$. Thus any numbers $x,y,z$ where $x\not= \pm1$ would have worked.

\vspace{0.1in}
\end{enumerate}

\noindent
{\bf\large 2. (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{0.1in}

A partition is a collection of non-empty, disjoint subsets, which when unioned together give the whole set. Notice that 
$\{ -1,-2,\dots \} \cup \{ 1^2,2^2,\dots \} = \{ \dots, -3,-2,-1,1,4,9,16,\dots \}$ is missing a lot of integers [In particular, $0$ is missing]. So these sets do not form
a partition of $\mathbb{Z}$. 
\vspace{0.1in}
   
   \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{0.1in}

If these sets are unioned together we get all of the integers. They are certainly non-empty sets. Finally, they are disjoint (they do not share
any elments). Thus these sets partition $\mathbb{Z}$. 

Although I did not expect this from anyone taking the test, I will give a more detailed proof.

First, it is obvious that all three sets are non-empty: $0,1,2$ are elements of each of the respective sets.

Next, suppose $m \in \mathbb{Z}$. Then the division algorithm states that there are {\bf unique} integers $q,r \in \mathbb{Z}$ such that
$m =3q+r$ where $0 \leq r <3$. Thus $m=3q$, $3q+1$, or $3q+2$. So $m$ belongs to one of these sets. Finally, since the remainder, $r$, is unique
$m$ belongs to {\bf exactly one} of these sets (i.e. they are disjoint). 

\vspace{0.1in}

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

\vspace{0.1in}

Although the union of these sets is all of $\mathbb{Z}$, the sets are not disjoint (both contain $0$). Thus these sets 
do not partition $\mathbb{Z}$.

\vspace{0.1in}

\end{enumerate}

\noindent
{\bf\large 3. (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:

\hfill   i. $f$ is injective (i.e. one-to-one). \hfill     ii. $g$ is surjective (i.e. onto). \hfill \hfill

\vspace{0.1in}

Proof of i.  Suppose that $f(x)=f(y)$. Then $g(f(x))=g(f(y))$ so that $g \circ f(x) = g \circ f(y)$. However, $g \circ f$ is bijective. Thus 
it is one-to-one (injective). Therefore, $x=y$. Thus $f$ is one-to-one as well.

\vspace{0.1in}

Proof of ii. Suppose that $y \in A$ (the codomain of $g$). We know that $g \circ f$ is bijective. Thus $g \circ f$ is onto (surjective). Therefore,
there exists some $z \in A$ such that $g \circ f(z)=y$. Let $x=f(z) \in B$. We have that $g(x)=g(f(z))=g \circ f(z)=y$. Therefore, $g \circ f$ is
onto.

\vspace{0.1in}


   \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{0.1in}

Suppose $h(x)=h(y)$ for some integers $x,y$. Then $2x=2y$ and so $x=y$. Thus $h$ is one-to-one. 

On the other hand, $h$ is not onto. Notice that the range of $h$ is all {\bf even} integers (not all integers) so the range 
is not equal to the codomain. OR more concretely, suppose $h(x)=1$. Then $2x=1$ and so $x=1/2$. But $1/2 \not\in \mathbb{Z}$.
Therefore, $1$ is not in the range of $h$. Thus $h$ is not onto.

{\it Note:} $h(x)=2x$ is both one-to-one and onto if we change its domain and codomain to $\mathbb{R}$ (the real numbers).

\vspace{0.1in}

\end{enumerate}

\noindent
{\bf\large 4. (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{0.1in}

Base case $n=0$: $0<1=2^0$ thus the inequality holds for $n=0$ (the smallest {\bf non-negative} integer).

Inductive step: Suppose that $n<2^n$ for some non-negative integer $n$. Then $n+1<2^n+1$ since we assumed $n<2^n$.
Then $n+1<2^n+1<2^n+2^n=2(2^n)=2^{n+1}$ since $1<2^n$ for all non-negative integers $n$ (we will just use this fact,
however, it too can be proven using induction). 

Thus we showed that $n<2^n$ for $n=0$ and that $n<2^n$ implies $n+1<2^{n+1}$ for each non-negative integer
$n$. Therefore, by induction, $n<2^n$ for all non-negative integers $n$.

\vspace{0.1in}

   \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)$.

\vspace{0.1in}

Suppose $x \in f(S_1) \cup f(S_2)$. Then either $x \in f(S_1)$ or $x \in f(S_2)$. This means that either there exists some
$s \in S_1$ such that $x=f(s)$ or there exists some $s \in S_2$ such that $x=f(s)$. Therefore, there exists some $s \in S_1$ or $s \in S_2$
such that $x=f(s)$. Thus there exists some $s \in S_1 \cup S_2$ such that $x=f(s)$. Therefore, by definition, $x \in f(S_1 \cup S_2)$.

So we have shown that all the elements in $f(S_1) \cup f(S_2)$ are also in $f(S_1 \cup S_2)$. Therefore, $f(S_1) \cup f(S_2) \subseteq f(S_1 \cup S_2)$.

\vspace{0.1in}
\end{enumerate}

\noindent
{\bf\large 5. (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{0.1in}

$11$ divided by $4$ is $2$ remainder 3: $11=(2)4+3$. Next, $4$ divided by $3$ is 1 remainder $1$: $4=(1)3+1$. Finally, $3$ divided by $1$ is $3$ remainder $0$.
The Euclidean algorithm says that the last non-zero remainder is the GCD. Thus the GCD of $4$ and $11$ is $1$.

Next, we will use the facts: $(-1)3+4=1$, $(-2)4+11=3$ to find a linear combination of $4$ and $11$ which gives us $1$. Start with $(-1)3+4=1$ and replace $3$ with $(-2)4+11$. This gives us $(-1)[(-2)4+11]+4=1$ so that $(3)4+(-1)11=1$.

\vspace{0.1in}

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

\vspace{0.1in}

We have a theorem which states (for $a,b \in \mathbb{Z}$ not both 0): $\{ ax+by \;|\; x,y \in \mathbb{Z} \} = \{ kd \;|\; k \in \mathbb{Z} \}$ where $d$ is the GCD of $a$ and $b$. In  words, every linear combination of $a$ and $b$ is a multiple of the GCD and conversely every multiple of the GCD can be written as a linear combination of $a$ and $b$. 

Therefore, $6$ must be a multiple of the gcd of $a$ and $b$. Thus we can conclude that the GCD of $a$ and $b$ is $1,2,3,$ or $6$.

\vspace{0.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$.

\vspace{0.1in}

Since $a$ and $b$ are relatively prime (i.e. their GCD is $1$), there exists $x,y \in \mathbb{Z}$ such that $ax+by=1$. Next, since $a$ and $b$ divide $c$,
there exists $k,\ell \in \mathbb{Z}$ such that $ak=c$ and $b\ell=c$. Thus $c=c \cdot 1 = c(ax+by) = cax+cby = (\ell b)ax + (k a)by = ab(\ell x+ ky)$. 
Thus $ab$ divides $c$ since $\ell x+ky \in \mathbb{Z}$.

\vspace{0.1in}
\end{enumerate}

\noindent
{\bf\large 6. (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
\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 & 2 & 3 & 4 & 5 & 0 \\ \hline
2 &  2 & 3 & 4 & 5 & 0 & 1 \\ \hline
3 &  3 & 4 & 5 & 0 & 1 & 2 \\ \hline
4 &  4 & 5 & 0 & 1 & 2 & 3 \\ \hline
5 &  5 & 0 & 1 & 2 & 3 & 4 \\ \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 & 4 & 0 & 2 & 4 \\ \hline 
3 &  0  &  3 & 0 & 3 & 0 & 3 \\ \hline 
4 &  0  &  4 & 2 & 0 & 4 & 2 \\ \hline 
5 &  0  &  5 & 4 & 3 & 2 & 1 \\ \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} = \mathrm{DNE}$} &
   \parbox[c][0.5in]{0.75in}{$1^{-1} = 1$} &
   \parbox[c][0.5in]{0.75in}{$2^{-1} = \mathrm{DNE}$} &
   \parbox[c][0.5in]{0.75in}{$3^{-1} = \mathrm{DNE}$} &
   \parbox[c][0.5in]{0.75in}{$4^{-1} = \mathrm{DNE}$} &
   \parbox[c][0.5in]{0.75in}{$5^{-1} = 5$}  \\ \hline
   \end{tabular}
   
\vspace{0.1in}

For example, there is no number such that $2x=1$ mod $6$, so $2$ has no multiplicative inverse. On the other hand, $5 \cdot 5=1$ mod $6$ so $5$ is its own
multiplicative inverse.

\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 = 0$} &
   \parbox[c][0.5in]{0.75in}{$-1 = 5$} &
   \parbox[c][0.5in]{0.75in}{$-2 = 4$} &
   \parbox[c][0.5in]{0.75in}{$-3 = 3$} &
   \parbox[c][0.5in]{0.75in}{$-4 = 2$} &
   \parbox[c][0.5in]{0.75in}{$-5 = 1$}  \\ \hline
   \end{tabular}
   
\vspace{0.1in}

Every number has an additive inverse (mod anything). For example, $2+4=0$ mod $6$ so $2$ is the additive inverse of $4$ and $4$ is
the additive inverse of $2$.

\vspace{0.1in}

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

This is undefined since $2$ has no multiplicative inverse mod 6 (i.e. $2^{-1}$ does not exist).

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

\vspace{0.1in}

$5^{-1}(3+4)-2 = 5(3+4)-2 = 5(1)-2=5-2=3$ (using $5^{-1}=5$ and $3+4=1$ mod 6). 

Alternatively $5^{-1}(3+4)-2 =5(7)-2=35-2=33=3$ mod 6. We can perform the all of the operations (with the exception of division) using regular integer arithmetic.

\vspace{0.1in}

\end{enumerate}

\end{document}
