\magnification=\magstep1
\centerline{Mathematics 243, section 3 -- Algebraic Structures}
\centerline{Final Examination -- December 15, 2012}
\bigskip
\noindent
{\it Directions}
\bigskip
You have {\it until 2:00 p.m.\/} to work on this exam.
Do problems I - VIII in the blue exam booklet.  There are 200 possible regular points
and 20 Extra Credit points.  
\bigskip
\noindent
I. 
Let $\varphi, \psi : {\bf Z} \to {\bf Z}$ be the mappings defined
$$\eqalign{\varphi(x) &= \cases{3x + 1 & if $x$ is odd\cr x/2 & if $x$ is even\cr}\cr
           \psi(x) &= \cases{x - 1 & if $x$ is odd\cr
                             x + 1 & if $x$ is even\cr}\cr}$$ 
\bigskip
\item{A)} (10) What is the set $\varphi(\{1,2,3,4\})$?
\bigskip
\item{B)} (10) What is the mapping $\varphi \circ \psi$?    
\bigskip
\noindent
II.  Let $A = \{1,2\}$ and let ${\cal P} = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$
(the collection of all subsets of $A$).  Let $*$ be the binary operation on
${\cal P}$ defined by $B*C = B - (B \cap C)$.  For instance,
$\{1,2\} * \{1\} = \{1,2\} - \{1\} = \{2\}$.  
\bigskip
\item{A)}  (15) Compute the rest of the operation table for $*$ on
${\cal P}$.
\item{B)}  (10) Is $*$ a commutative operation?  Is it associative?
\bigskip
\item{C)}  (5)  Is there an identity element for $*$ in ${\cal P}$.  If so,
what is the identity element?
\bigskip
\noindent
III.
\item{A)} (15) Let $a, b$ be integers, at least one of which is nonzero.  Show that 
there is an integer $d$ satisfying the definition of $\gcd(a,b)$ that is contained
in the set $S = \{ma + nb \mid m,n \in {\bf Z}\}$.  
\bigskip
\item{B)} (15)  Find the integer $d = \gcd(535,410)$ and express 
$d$ in the form $d = 535 m  + 410 n$ for some integers $m, n$.
\bigskip
\item{C)}  (15)  Assume that $a,b,c$ are integers, 
$d = \gcd(a,b)$, $a|c$ and $b|c$.  Prove that $(ab)|(cd)$. 
\bigskip 
\item{D)}  (15) An RSA public key cryptographic system has $m = 187$ and encryption
exponent $e = 31$.  What is the corresponding decryption exponent $d$?
\bigskip
\noindent
IV.  (15)  Prove by mathematical induction:  for all real numbers $a,b$ and all $n \ge 1$:
$$\pmatrix{a & 0 \cr b & a}^n = \pmatrix{a^n & 0 \cr na^{n-1} b & a^n}.$$
\bigskip
\noindent
V. (15) Consider the set of all $2\times 2$ matrices with real entries:
$$M_{2\times 2}({\bf R}) = 
\left\{\pmatrix{a&b\cr c&d\cr} \mid a,b,c,d \in {\bf R}\right\},$$ 
which is a group under matrix {\it addition\/}.  Show that 
$$H = \left\{\pmatrix{0 & a\cr 0 & b\cr} \mid a,b \in {\bf R}\right\}$$
is a subgroup of $M_{2\times 2}({\bf R})$.  
\bigskip
\noindent
VI.  All parts of this question refer to the group $G = {\bf Z}_{36}$,
in which the operation is addition mod 36.
\bigskip
\item{A)} (5) Find all generators for $G$.
\bigskip
\item{B)} (5) Find the elements of the cyclic subgroup $\langle [21] \rangle$
in $G$.  
\bigskip
\item{C)} (5) Find all elements of $G$ of order $9$.
\bigskip
\noindent
VII. (10)  Let $G$ be a group with operation $*$ and let $a \in G$. 
Let $\ell_a : G \to G$ be the mapping defined by $\ell_a(x) = a*x$.  
Show that $\ell_a$ is always a one-to-one and onto mapping.  
\bigskip
\noindent
VIII.  Let $G$ and $H$ be groups with identity elements
$e_G$ and $e_{H}$ respectively, and let 
$\varphi : G \to H$ be a group homomorphism.
\bigskip
\item{A)} (15)  Show that $\ker(\varphi)$ is a subgroup of $G$.
\bigskip
\item{B)} (5)  Let $c\in H$, and let $a,b\in \varphi^{-1}(\{c\})$, 
(the inverse image under the mapping $\varphi$). Prove that $a*_G b^{-1} \in \ker(\varphi)$.
\bigskip
\item{C)} (15)  Let $G$ be a group and let $H$ be a subgroup of $G$.  Define a 
relation called {\it congruence modulo } $H$ on $G$ by this rule:
$$x \equiv y \bmod H \Leftrightarrow xy^{-1} \in H.$$
Show that congruence mod $H$ is an equivalence relation.  
\bigskip
\bigskip
\noindent
{\it Extra Credit}  (20)  From the 2012 Putnam Exam:  Let $*$ be a commutative and
associative binary operation on a set $S$.  Assume that for every $x,y \in S$, there
exists some $z \in S$ such that $x*z = y$.  (The $z$ may depend on $x$ and $y$.)  Show that
if $a,b,c \in S$ and $a*c = b*c$, then $a = b$.  

\bigskip
\centerline{\it Have a peaceful and joyous holiday season!}
\bye
