\magnification=\magstep1
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Final Examination -- December 13, 2006}
\bigskip
\noindent
{\it Directions}
\bigskip
You have {\it until 11:30 a.m.\/} to work on this exam.
Do problems I - IX in the blue exam booklet.  There are 200 possible points.
\bigskip
\noindent
I. 
Let $\varphi, \psi : {\bf Z} \to {\bf Z}$ be the mappings defined
$$\eqalign{\varphi(x) &= \cases{3x & if $x$ is odd\cr 1 & 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) Is $\psi$ a permutation of ${\bf Z}$?  Prove your assertion.
\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 $C + D = (C \cup D) - (C\cap D)$.  For instance,
$\{1\} + \{1,2\} = \{1,2\} - \{1\} = \{2\}$.  
\bigskip
\item{A)}  (15) Compute the rest of the operation table for $+$ on
${\cal P}$.
\bigskip
\item{B)}  (5)  Is there an identity element for $+$ in ${\cal P}$.  If so,
what is the identity element?
\bigskip
\noindent
III.  (10)  Prove by contradiction: if $A = \{a_1, \ldots, a_n\}$ 
is a {\it finite\/} set and $\varphi : A \to A$ is surjective then 
$\varphi$ is also injective.
\bigskip
\noindent
IV.
\item{A)}  (5) Let $a,b$ be two integers, at least one of which is nonzero.
Give the definition of a gcd of $a,b$. 
\bigskip
\item{B)} (15)  Find the integer $d = \gcd(537,411)$ and express 
$d$ in the form $d = 537r + 411s$ for some integers $r,s$.
\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)}  (20) An RSA public key cryptographic system has $m = 209$ and encryption
exponent $e = 37$.  What is the corresponding decryption exponent $d$?
\bigskip
\noindent
V.  (20) Prove by mathematical induction:  for all real numbers $a,b$ and all $n \ge 1$:
$$\pmatrix{a & b \cr 0 & a}^n = \pmatrix{a^n & na^{n-1} b \cr 0 & a^n}.$$
\bigskip
\noindent
VI. (20) 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} : a,b,c,d \in {\bf R}\right\}.$$ 
Show that $M_{2\times 2}({\bf R})$ is a group under matrix 
{\it addition\/}:
$$\pmatrix{a&b\cr c&d\cr} + \pmatrix{e&f\cr g&h\cr} = 
\pmatrix{a+e&b+f\cr c+g&d+h\cr}.$$
\bigskip
\noindent
VII.  All parts of this question refer to the group $G = {\bf Z}_{27}$,
in which the operation is addition mod 27.
\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
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 $ab^{-1} \in \ker(\varphi)$.
\bigskip
\item{C)}  (5)  Prove that $\varphi$ is injective if and only if
$\ker(\varphi) = \{e_G\}$.
\bigskip
\noindent
IX.  (10) Let $G$ be a group, and let $x,y \in G$.  The conjugacy relation
$R$ on $G$ is defined as follows.  We say $x$ and $y$
are {\it conjugate} in $G$, $xRy$, if there exists an $a \in G$ such
that $y = axa^{-1}$.  Show that the conjugacy relation is an equivalence
relation on $G$. 

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