\magnification=\magstep1
\centerline{Mathematics 243, section 3 -- Algebraic Structures}
\centerline{Information on Exam 2}
\centerline{October 26, 2012}
\bigskip
\noindent
{\it General Information}
\bigskip
The second exam this semester will be
given next Friday, November 2.  The exam will cover the
material we have discussed since the first exam, through
class on Friday, October 26.  This is the material from sections
1.7, 2.1, 2.2, 2.3, 2.4, 2.5, and 2.6.
The topics to review are:
\bigskip
\item{1)}  Relations, especially equivalence relations, and their properties
\item{2)}  Properties of ${\bf Z}$
\item{3)}  Proof by mathematical induction
\item{4)}  Divisibility.  Know the statement of the Division Algorithm 
(Theorem 2.10 in the text) and its proof, 
\item{5)}  Prime numbers, prime factorizations and the Unique Factorization
Theorem (Theorem 2.18), 
\item{6)}  Greatest common divisors and Euclid's algorithm for 
$\gcd(a,b)$.  Know the proof of Theorem 2.12 (existence of $\gcd(a,b)$
in $S = \{x \in {\bf Z} : x = ma + nb, {\rm\ for\ some\ } m,n \in {\bf Z}\}$,
and uniqueness of gcd).
\item{7)}  Congruence mod $n$ and the integers mod $n$: the set of 
congruence classes ${\bf Z}_n$ and the addition and multiplication
mod $n$ operations.  
\bigskip
\noindent
{\it Some Review Problems}
\bigskip
\noindent
From Gilbert and Gilbert:
\bigskip
\item{1)} Section 1.7: 4, 8, 12
\item{2)} Section 2.2: 4, 6, 13, 14, 32, 33, 45
\item{3)} Section 2.3: problems like 1-16, proofs like 17-25, 34, 37
\item{4)} Section 2.4: problems like 2, 3, 16, 18, 20 (Note:  In the text, $(a,b) = \gcd(a,b)$.)
\item{5)} Section 2.5: problems like 1, 3-24, 30, 34
\item{6)} Section 2.6: problems like 3,4,5,6,7
\bigskip
\noindent
{\it Review Session}
\bigskip
I will be happy to run a review session before the exam.  
Tuesday October 31 or Thursday, November 1 are probably the best times for this for me,
but I might also be able to do a session Wednesday evening.
\vfill\eject
\noindent
{\it Sample Exam Questions}
\bigskip
\noindent
{\it Disclaimer:}  As always, the following questions indicate the range of topics that
will be covered and the approximate level of difficulty of the exam questions.  The
actual exam questions may be organized differently, though.
\bigskip
\noindent
I. Expect an induction proof like one of the following:
\item{A)} Show using mathematical induction that 
$$1^2 + 3^2 + 5^2 + \cdots + (2n-1)^2 = {n(2n-1)(2n+1)\over 3}$$ 
for all integers $n \ge 1$.
\item{B)} The basic triangle inequality is $|x + y| \le |x| + |y|$, a fact
that follows for all $x,y\in {\bf Z}$ from the basic order properties.  
Taking this as given show that for all $n\ge 2$ and all $x_i\in {\bf Z}$, 
$$|x_1 + x_2 + \cdots + x_n| \le |x_1| + |x_2| + \cdots + |x_n|.$$
\noindent
II.  Let $R$ be the relation on ${\bf Z}$ defined by $x R y$ if (and only
if $5|(x^2 - y^2)$.  
\item{A)}  Is $R$ an equivalence relation?  Prove your assertion.
\item{B)}  Show that $x R y$ if and only if $x \equiv y {\pmod 5}$
or $x \equiv -y {\pmod 5}$.  (Hint: Euclid's Lemma)
\bigskip
\noindent
III.  
\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
IV.
\item{A)}  Give the definition of the {\it greatest common divisor}
of the integers $a,b$.
\item{B)}  Prove that if $S = \{x \in {\bf Z} : x = ma + nb, m,n\in {\bf Z}\}$,
then the smallest positive integer in $S$ is $\gcd(a,b)$. 
\item{C)}  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{D)}  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
V.  
\item{A)}  Show that for all $n \ge 1$, $9|(10^n - 1)$ and 
$11|(10^n - (-1)^n)$. (Hint:  For the first statement,  
show first that $10^{k+1} - 1 = 10^k\cdot 9 + (10^k - 1)$.)   
\item{B)}  Restate the result of part A as a congruence.
\item{C)}  (Extra Credit-type question) How can you test numbers for 
divisibility by 9 using the base 10 digits?  How could you test numbers
for divisibility by 11 using the base 10 digits?
\bigskip
\noindent
VI. 
\item{A)}  Find all integer solutions of the congruence
$12x + 3 \equiv 7 \bmod 31$. 
\item{B)}  Find all solutions $[x]$  of the equation 
$[17][x] + [4] =  [5]$ in ${\bf Z}_{29}$.
\item{C)}  Show that $[x]$ has a multiplicative inverse in 
${\bf Z}_n$ (that is, a $[y]$ such that $[x][y] = [1] = [y][x]$)
if and only if $\gcd(x,n) = 1$.   
\item{D)}  Which $[x] \in {\bf Z}_{18}$ have multiplicative inverses?
\bye
