\magnification=\magstep1
\def\Sol{\item{}{\it Solution:}}
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Solutions fo Exam 2, November 1, 2006}
\bigskip
\noindent
I.  Think of ${\bf R}^2$ (the set of ordered pairs of real
numbers) as the ordinary Cartesian coordinate plane.
Let $R$ be the relation on ${\bf R}^2$ defined by 
$$(x_1,y_1)R(x_2,y_2) \Leftrightarrow 3x_1 + y_1 = 3x_2 + y_2$$
\item{A)} (15) Show that $R$ is an equivalence relation on ${\bf R}^2$.
\Sol
$R$ is transitive because for all points $(x,y) \in {\bf R}^2$,
$3x + y = 3x + y$, hence $(x,y)R(x,y)$.

\item{} $R$ is symmetric because if $(x_1,y_1)R(x_2,y_2)$, 
then $3x_1 + y_1 = 3x_2 + y_2$, so $3x_2 + y_2 = 3x_1 + y_1$,
and $(x_1,y_1)R(x_2,y_2)$. 

\item{} $R$ is transitive because if $(x_1,y_1)R(x_2,y_2)$
and $(x_2,y_2)R(x_3,y_3)$, then $3x_1 + y_1 = 3x_2 + y_2$ 
and $3x_2 + y_2 = 3x_3 + y_3$, so $3x_1 + y_1 = 3x_3 + y_3$.
\bigskip
\item{B)} (5) Draw a picture of the equivalence class $[(2,3)]$ for 
this relation.
\Sol The equivalence class of the point $(2,3)$ is the 
set of all points $(x,y)$ such that $(x,y)R(2,3)$, so 
$3x + y = 9$.  This is the {\it line} $y = -3x + 9$ with 
slope $-3$ and $y$-axis intercept at $(0,9)$.
\bigskip
\noindent
II. (20) Prove by mathematical induction:  For all $n \ge 1$,
$$1^3 + 3^3 + 5^3 + \cdots + (2n-1)^3 = n^2(2n^2-1).$$
\bigskip
\noindent
III.  
\item{A)} (15) Give the precise statement of the division algorithm
in ${\bf Z}$, and prove the existence part. 
\bigskip
\item{B)} (15) Use the Euclidean algorithm to find the integer
$d = \gcd(576,99)$ and express $d$ in the form 
$d = m\cdot 576 + n\cdot 99$
for some integers $m,n$.
\bigskip
\noindent
IV.  (10)  Let $a,b,c$ be integers. 
Show that if $\gcd(a,b) = 1$ and $a|(bc)$, then $a|c$.  
\bigskip
\noindent
V.  
\item{A)} (10) Find a solution $x$ of the congruence 
$31 x \equiv 2 \bmod 64$ with $0 \le x < 64$.
\bigskip
\item{B)} (10) For which $[b] \in {\bf Z}_{16}$ do solutions 
$[x] \in {\bf Z}_{16}$ of the equation $[12][x] = [b]$ exist?  
Explain how you can tell.
\bye


