\magnification=\magstep1
\centerline{Mathematics 243, section 2 -- Mathematical Structures}
\centerline{Information on Exam 2}
\centerline{October 25, 2017}
\bigskip
\noindent
{\it General Information}
\bigskip
The second exam this semester will be
given next week, either on Thursday evening, November 2 or in class on Friday
morning, November 3.  (We'll discuss the options on October 27 and decide.)
The exam will cover the
material we have discussed since the first exam (Problem Sets 4,5,6), through
class on Friday, October 27 (``Fermat's Little Theorem'').  
\bigskip
\item{1)}  Functions/Mappings, injectivity and surjectivity
\item{2)}  Integer division -- know the statement of the Division Algorithm 
(Theorem 4.8 in the text) and its proof, 
\item{3)}  Greatest common divisors and Euclid's algorithm for 
$\gcd(a,b)$.  Know the proof of Theorem 4.20 -- Every nonzero subgroup of the integers
under addition has the form $d{\bf Z}$ for some $d > 0$, and how $d$ satisfies
the properties of a gcd (see Definitions 4.21 and 4.23).  
\item{3)}  Prime numbers, Euclid's Lemma (Theorems 5.13 and 5.12), prime factorizations and 
the ``Fundamental Theorem of Arithmetic (Theorems 5.17 and 5.18). 
\item{4)}  Congruence mod $n$ and the integers mod $n$: the set of 
congruence classes ${\bf Z}/n{\bf Z}$ and the addition and multiplication
mod $n$ operations.  
\bigskip
\noindent
{\it Some Review Problems}
\bigskip
\noindent
From the course notes:
\bigskip
\item{1)} Chapter 4: 4.7, 4.9, 4.10
\item{2)} Chapter 5: 5.5, 5.8a, 5.9, 5.14, 5.15, 5.16  
\item{3)} Chapter 6: 6.3, 6.4, 6.7, 6.9b,c 
\bigskip
\noindent
{\it Review Session}
\bigskip
I will be happy to run a review session before the exam.  
Tuesday evening (October 31) is probably the best time for this for me,
especially if we do the exam on Thursday evening.
\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. 
\bigskip
\noindent
I.  Let $[a] \in  {\bf Z}/18{\bf Z}$ and let
$m_{[a]}: {\bf Z}/18{\bf Z} \to {\bf Z}/18{\bf Z}$
be the mapping defined by $m_{[a]}([x]) = [a]\cdot [x] = [a\cdot x]$.
\item{A)}  Is $m_{[12]}$ an injective mapping?  Why or why not?  
Is it a surjective mapping?  Why or why not?
\item{B)}  Is $m_{[5]}$ an injective mapping?  Why or why not?
\item{C)}  Prove that $m_{[a]}$ is injective if and only if
$[a]$ has a multiplicative inverse in ${\bf Z}/18{\bf Z}$.
\item{D)}  Prove the $m_{[a]}$ is injective if and only if 
$m_{[a]}$ is surjective.  
\bigskip
\noindent
II.  
\item{A)}   Given integers $a$, and $b > 0$, prove that there exist
unique integers $q$ and $r$ such that $a = qb + r$ and $0 \le r < b$.
(You may apply the Well-Ordering Principle without justifying that.)
\item{B)}   Find the quotient $q$ and the remainder $r$ as in part A for 
$a = 4578$ and $b = 235$.
\bigskip
\noindent
III.
\item{A)}  Prove that if $S = \langle a,b\rangle = \{x \in {\bf Z} : x = ma + nb, m,n\in {\bf Z}\}$,
then the smallest positive integer $d$ in $S$ satisfies the properties:
\itemitem{1.}  $d$ divides $a$ and $d$ divides $b$.
\itemitem{2.}  If $c$ divides $a$ and $c$ divides $b$, then $c$ divides $d$. 
\item{B)}  Find the integer $d = \gcd(488,376)$ and express 
$d$ in the form $d = m\cdot 488 + n\cdot 76$ for integers $m,n$.
\item{C)}  Prove that if there is a solution of the 
congruence $ax \equiv b \pmod n$ (where $n > 1$), 
then ${\rm gcd}(a,n) | b$.
\bigskip
\noindent
IV.  
\item{A)}  Show that for all $n \ge 1$, $8|(9^n - 1)$. (Hint: 
Show first that $9^{k+1} - 1 = 9^k\cdot 8 + (9^k - 1)$.)   
\item{B)}  Restate the result of part A as a congruence.
\item{C)}  (Extra Credit-type question) Suppose we used base 9 rather 
than base 10 to represent integers.  How could you test numbers for 
divisibility by 8 using the base 9 digits?  How could you test numbers
for divisibility by 10 using the base 9 digits?
\bigskip
\noindent
V.  Show that $[x]$ has a multiplicative inverse in 
${\bf Z}/n{\bf Z}$ (that is, a $[y]$ such that $[x][y] = [1] = [y][x]$)
if and only if $\gcd(x,n) = 1$. 
\bigskip
\noindent
VI. 
\item{A)}  Find all integer solutions of the congruence
$12x \equiv 7 \bmod 331$. 
\item{B)}  Find all solutions $[x]$  of the equation 
$[17][x] + [4] =  [2]$ in ${\bf Z}/{29}{\bf Z}$. 
\item{C)}  Which $[x] \in {\bf Z}/18{\bf Z}$ have multiplicative inverses?
\bye
