\magnification=\magstep1
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Final Examination -- December 16, 2003}
\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 
regular points and 20 Extra Credit points.  Note:  Even if you 
don't see how to derive a complete solution to a problem, don't leave
it blank.  Partial credit will be given for relevant definitions, 
ideas that could lead to solutions, and so forth.  
\bigskip
\noindent
I. 
\item{A)} (15) Let $p,q$ represent any propositions. 
Construct the truth table for the proposition
$$(p\ {\rm implies}\ q)\ {\rm if\ and\ only\ if}\ ((p\ {\rm and\ not}\ q)\ {\rm implies\ not}\ p)$$
\item{B)}  (10)  Give the contrapositive form of the statement
``If the product of two integers $x,y$ is even, then $x$ is even 
or $y$ is even.''
\bigskip
\noindent
II.    
\bigskip
\item{A)} (15) Let $A = {\bf Z}$, the set of all integers.
Consider $\varphi : A \to A$ be the mapping defined
by 
$$\varphi(x) = \cases{5x & if $x$ is even\cr
                      x - 2 & if $x$ is odd\cr}$$
Is $\varphi$ one-to-one?  Why or why not?
Is $\varphi$ onto?  Why or why not?
\item{B)} (10) If $A$ is a {\it finite\/} set and
$\varphi : A \to A$ is one-to-one, is $\varphi$ also necessarily
onto?  Explain, and/or prove your assertion.
\bigskip
\noindent
III.
\item{A)}  (20) Give the precise statement and the proof of the Division 
Algorithm in ${\bf Z}$.
\item{B)} (10)  Find the integer $d = \gcd(753,154)$ and express 
$d$ in the form $d = 753m + 154n$ for some integers $m,n$.
\item{C)}  (10)  Show that if $a,b,c$ are integers, $a | (b\cdot c)$ and 
$\gcd(a,c) = 1$, then $a|b$.  
\bigskip
\noindent
IV.  Let $f_0 = 0, f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for 
all $n \ge 2$.  (The $f_n$ are called the {\it Fibonacci numbers}; the 
first few of them are $1,1,2,3,5,8,13,21,34, \ldots$.)
\item{A)} (10)  Let $A = \pmatrix{1&1\cr 1&0\cr}$.  Compute the 
matrix powers $A^2,A^3,A^4$.  Do you see a pattern developing?
\item{B)} (10) (The pattern!)  Show by mathematical induction:
$$\pmatrix{1&1\cr 1&0\cr}^n = \pmatrix{f_{n+1}&f_n\cr f_n& f_{n-1}}$$
for all $n \ge 1$.
\bigskip
\noindent
V.  (25) In an RSA public key cryptosystem, the public key consists of
the integer $m = 323$ and the encryption exponent $e = 29$.
What is the decryption exponent $d$?  
\bigskip
\noindent
VI.  Consider the following set of all $2\times 2$ matrices with real entries:
$$G = 
\left\{\pmatrix{a&b\cr 0&d\cr}\ |\ a,b,d \in {\bf R}\right\}.$$ 
\item{A)} (10) Show that $G$ is a group under matrix 
{\it addition\/}.
\item{B)} (10)  Is the set 
$$H = \left\{ \pmatrix{1&n\cr 0&1\cr}\ |\ n \in {\bf Z}\right\}$$
a subgroup of the group from part A?  Why or why not?
\bigskip
\noindent
VII. All parts of this question refer to  ${\bf Z}_{30}$,
in which the operations are addition and multiplication mod 30.
\item{A)} (10) Which elements of ${\bf Z}_{30}$ have {\it multiplicative}
inverses in ${\bf Z}_{30}$?
\item{B)} (10) Find all the elements of the additive group 
${\bf Z}_{30}$ that generate the additive subgroup
$\langle [24]\rangle$.
\bigskip
\noindent
VIII.  Let $G$ and $H$ be groups and let 
$\varphi : G \to H$ be a group homomorphism.
\item{A)} (5)  Give the precise definition of the {\it kernel\/} of $\varphi$,
$\ker(\varphi)$.
\item{B)} (5)  Show that if $K = \ker(\varphi)$ and $g \in G$
is an arbitrary fixed element, then $gKg^{-1} = \{gkg^{-1}\ |\ k \in K\}$
is equal to $K$.
\item{C)}  (5)  Show that the relation $R$ on $G$
defined by 
$$x R y \Leftrightarrow xy^{-1} \in \ker(\varphi)$$
is an {\it equivalence relation} on $G$.  
\bigskip
\noindent
IX.  (10)  Are there any elements of order 14 in the symmetric group 
$S_8$?  Why or why not?
\bigskip
\noindent
{\it Extra Credit} (20)
\bigskip
Prove that if $G = \langle a\rangle$ is a finite cyclic group with
$o(G) = n$, then $\langle a^k\rangle = \langle a^d\rangle$
where $d = {\rm gcd}(n,k)$.
\bigskip
\centerline{\it Have a peaceful and joyous holiday season!}
\bye
