\magnification=\magstep1
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Review Sheet, Final Exam}
\centerline{December 4, 2006}
\bigskip
\noindent
{\it General Information}
\bigskip
The final examination for this course will be given at 
8:30 a.m. on Wednesday, December 13 in our regular class room, 
Swords 328.  It will be a comprehensive exam, covering all 
the material we have studied each semester, divided {\it roughly} 
in thirds according to the topics from the three hour exams.
Some questions on earlier material (e.g. the one-to-one and onto
properties of mappings, binary operations, equivalence relations, 
etc.) may appear in the context of topics covered later in the semester, though.
The exam will be roughly twice the length of one of the three
midterms, but you will have the full three hour period from
8:30 am to 11:30 am to work on it if you need that much time.
\bigskip
\noindent
{\it Topics to be Covered}
\bigskip
\item{1)}  Sets: set operations (union, intersection, difference, complement,
Cartesian product, etc.) and their properties.
\item{2)}  Mappings: the 1-1 and onto properties, direct and inverse
images of sets under mappings,
\item{3)} Binary operations: identity elements, inverses, properties
such as associativity, commutativity, key examples such as 
function composition, matrix addition and multiplication, 
addition and multiplication in ${\bf Z}$ and ${\bf Z}_n$, etc.  
\item{4)}  Relations:  especially equivalence relations and 
the partition of a set into equivalence classes under an 
equivalence relation (key example:  the congruence mod $n$
relation on ${\bf Z}$ -- the set of equivalence classes
in that case is ${\bf Z}_n$).
\item{5)}  Properties of ${\bf Z}$:  the Well-Ordering
Property, proof by mathematical induction, the division algorithm,
divisibility, prime numbers and prime factorizations,
the gcd and lcm of two integers, Euclid's algorithm for the
gcd.
\item{6)}  The congruence mod $n$ relation on ${\bf Z}$
and the integers modulo $n$,  addition and multiplication
in ${\bf Z}_n$ and their properties.
 Applications to cryptography (affine and RSA cryptosystems). 
\item{7)}  Groups:  the definition, key examples such as
${\bf Z}_n$ under addition mod $n$, the group
$$U(n) = \{[x] \in {\bf Z}_n : [x]^{-1}\ {\rm (multiplicative\ inverse)\ exists}\}
= \{[x] \in {\bf Z}_n : \gcd(x,n) = 1\}$$
under multiplication mod $n$, $GL_2({\bf R})$, the symmetric groups
$S_n$, etc.
\item{8)}  Subgroups of groups:  know how to determine whether
a given subset of a group is a subgroup.  Cyclic subgroups.
\item{9)}  Cyclic groups, generators, orders of elements, etc.
\item{10)}  Homomorphisms of groups, kernel and image of a 
homomorphism, isomorphisms.
\item{11)}  Permutation groups and cycle notation for permutations,
orders of permutations.
\vfill
\eject
\noindent
{\it Proofs to Know}
\bigskip
See the review sheets for Exams 1, 2, and 3.  (These
are reposted on the course homepage in case you need
additional copies.)
\bigskip
\noindent
{\it Suggestions on How to Study}
\bigskip
Start by reading the above list of topics carefully.
If there are terms there that are unfamiliar or for which
you cannot give the precise definition, {\it learn the definitions
now}.   Review the class notes.  {\it Everything on 
the final will be similar to something we have discussed at
some point this semester.}   Also look back over your graded
problem sets and exams.  If there are problems that you 
did not get the first time around, try them again now.  Then
go through the suggested problems from the three
review sheets.  If you have worked these out previously,
it is not necessary to do them all again.  But try a representative
sample ``from scratch'' -- don't just look over your old
solutions and nod your head if it looks familiar.  You
need the practice thinking through the logic of how
the solution is derived again!
\bigskip
\noindent
{\it Review Session}
\bigskip
I will be happy to run a review session for the final
exam during study week.  We can discuss a time in class
on Monday, December 4.
\bigskip
\noindent
{\it Some Sample Exam Questions}
\bigskip
\noindent
I.    
\bigskip
\item{A)} 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)}  What is $\varphi^{-1}(\{3,4,5,6,7\})$ for
the mapping in part A?
\item{C)}  What is $\varphi(\{1,2,3\} \cap \{x\in A : x^2 < 5\})$?
\bigskip
\noindent
II.
\item{A)}  Give the precise statement and the proof of the Division 
Algorithm in ${\bf Z}$.
\item{B)}  Find the integer $d = \gcd(753,154)$ and express 
$d$ in the form $d = 753m + 154n$ for some integers $m,n$.
\item{C)}  Show that if $a,b,c$ are integers, $a | (b\cdot c)$ and 
$\gcd(a,c) = 1$, then $a|b$.  
\bigskip
\noindent
III.  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)}  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)}  (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
IV.  
\item{A)}  In an affine cipher on a 26-letter alphabet, 
``E'' (the most common letter) is encrypted to ``Z'' and ``T''
(the next most common letter) is encrypted to ``B''.  What
are the encryption and decryption functions?  
\item{B)} 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
V.  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)} Show that $G$ is a group under matrix {\it addition\/}.
\item{B)} 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
VI. All parts of this question refer to  ${\bf Z}_{30}$,
in which the operations are addition and multiplication mod 30.
\item{A)}  Which elements of ${\bf Z}_{30}$ have {\it multiplicative}
inverses in ${\bf Z}_{30}$?
\item{B)}  Find all the elements of the additive group 
$({\bf Z}_{30},+)$ that generate the additive subgroup
$\langle [24]\rangle$.
\bigskip
\noindent
VII.  Let $G$ and $H$ be groups and let 
$\varphi : G \to H$ be a group homomorphism.
\item{A)}  Give the precise definition of the {\it kernel\/} of $\varphi$,
$\ker(\varphi)$.
\item{B)}  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)}   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
VIII.  Are there any elements of order 14 in the symmetric group 
$S_8$?  Why or why not?
\bye

