\magnification=\magstep1
\centerline{Mathematics 243, section 2 -- Mathematical Structures}
\centerline{Information on Exam 3}
\centerline{November 28, 2017}
\bigskip
\noindent
{\it General Information}
\bigskip
The third exam this semester will be
given next week.  The options for scheduling are:
\bigskip 
\item{$\bullet$} the regular class period on Wednesday, December 6, or
\item{$\bullet$} Thursday in the late afternoon (say 5 - 7pm).  
(Unfortunately, I am not available after 7pm that day because of 
the Festival of Lessons and Carols in the Chapel starting at 8pm.
I also have a rehearsal for that on Wednesday night.)
(We'll discuss the options on November 29 and decide.)
The exam will cover the
material we have discussed since the second exam (Problem Sets 7,8), through
class on Wednesday, November 29 (convergence of sequences).  
\bigskip
\item{1)}  ``Fermat's Little Theorem'' (know the statement and proof)
\item{2)}  RSA public key cryptography (be able to take the public key information
$m,e$ for an RSA system, ``crack'' it by finding the primes $p,q$ with $m = pq$
and the decryption exponent $d$ and decrypt a short message (one or two characters), 
given an ASCII table for the numerical equivalents of the characters like the one 
you used for the problem on Problem Set 7.  
\item{3)}  Functions/Mappings, injectivity and surjectivity, direct and inverse
images -- be able to prove things like the problems from Problem Set 7, {\it including
statements you have not seen before}
\item{4)}  Properties of the real number systems including the Binomial Theorem, 
problems like the ones from 
Problem Set 8, etc.   Know especially what Axiom C (''completeness'') says and
consequences like the facts that the natural numbers are not bounded and 
given any $\varepsilon > 0$ , there exists $n \in {\bf N}$ such that ${1\over n} < \varepsilon$.
\item{5)}  I may ask you to give a proof that a simple sequence like $a_n = 2 + {1\over n}$
or something similar converges.
\bigskip
\noindent
{\it Review Session}
\bigskip
I will be happy to run a review session before the exam.   However, 
Tuesday evening (December 5) is virtually the only time for this for me.
\bigskip
\noindent
{\it Sample Exam Questions}
\bigskip
\noindent
Note:  This list is longer than the actual exam will be to 
show the range of different kinds of questions that might appear.  But
the exam questions will be similar in content and format.  
\bigskip
\noindent
I.  Consider an RSA public key cryptosystem with public information 
$m = 143$ and $e = 37$.
\item{A)}  ``Crack the system'' by determining the private information
$p,q$ and $d$.  
\item{B)}  You intercept a message encrypted using this system consisting
of the numbers $40, 114$.  Use your answer to part A and the table on
page 102 of the course notes to decrypt the message.  
\bigskip
\noindent
II.  
\item{A)}  Give the statement and proof of ``Fermat's Little Theorem.''
\item{B)}  Use part A to compute $3^{177} \bmod 7$.
\item{C)}  What is the {\it smallest} positive power $k$ such that 
$7^k \equiv 1 \bmod 11$?  Same question for $5^k \equiv 1 \bmod 11$.  
\bigskip
\noindent
III.  Let $f : A \to B$ be a mapping.
\item{A)}  If $S,T \subseteq A$ and $f(S) \cap f(T) \neq \emptyset$, can you conclude
that $S \cap T \neq \emptyset$?  (The answer is:  No).  Why not?  Give a counterexample. 
\item{B)}  (continuing from A) Give a condition on $f$ that would imply $S \cap T\ne \emptyset$
under the assumption that $f(S) \cap f(T) \ne \emptyset$.  Prove your assertion.
\item{C)}  If $U,V \subseteq B$ and $f^{-1}(U) \cap f^{-1}(V) \neq \emptyset$,
can you conclude that $U \cap V \neq \emptyset$?  If so, prove it.  If not, 
give a counterexample.
\item{D)}  Show that $f$ is surjective if and only if there is a mapping
$g : B \to A$ such that $f\circ g = id_B$.  ($id_B : B \to B$ is the mapping
satisfying $id_B(y) = y$ for all $y \in B$.)
\bigskip
\noindent
IV.  
\item{A)}  The binomial coefficient ${n \choose k}$ is the number of subsets
of $A = \{a_1,\ldots,a_n\}$ that contain exactly $k$ elements.  Assuming this fact,
give (yet another) proof that $A$ has $2^n$ distinct subsets (including
$\emptyset$ and $A$ itself).    
\item{B)}  Show by mathematical induction:  For all $u > 0$ in the reals, and 
all $n\ge 0$, 
$$1 + nu + {n(n-1)\over 2} u^2 + {n(n-1)(n-2)\over 6} u^3 \le (1 + u)^n$$
\item{C)}  Give a second proof of the statement in part B using the 
Binomial Theorem.  
\bigskip
\noindent
V. 
\item{A)}  Prove that ${\bf N}$ is not bounded above in the real numbers.  Use
this to deduce that for any $\varepsilon > 0$, there exists $n \ne 0 \in {\bf N}$ such 
that ${1 \over n} < \varepsilon$.  
\item{B)}  Use the last statement in part A to prove that the sequence 
$a_n = 3 - {1\over n}$ converges to $L = 3$.  
\item{C)}  Prove that 
$a_n = 3 - {1\over \sqrt{n}}$ also converges to $L = 3$.  
\bigskip
\noindent
VI.  Let $R$ be the relation on the set of real numbers defined by 
$a R b$ if and only if $a - b \in {\bf Z}$.  For example $1.32 R (-5.68)$ is true
for this relation since $1.32 - (-5.68) = 7 \in {\bf Z}$.  
\item{A)}  Show that $R$ is an equivalence relation.
\item{B)}  Show that the functions $\sin(2\pi x)$ and $\cos(2\pi x)$ are
well-defined mod $R$.  
\item{C)}  Give a subset of ${\bf R}$ that contains a {\it unique} element from
each of the equivalence classes for the relation $R$.  (That is, your 
set should contain $a$'s ``hitting'' all of the equivalence classes, but 
each one only once.   
\bye
