\magnification=\magstep1
\nopagenumbers
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Exam 2, November 5, 2003}
\bigskip
\noindent
{\it Directions:}  Do all work in the blue exam booklet.  There 
are 100 possible points.
\bigskip
\noindent
I.  
\item{A)} (10) Give the precise statement of the division algorithm
in ${\bf Z}$.  (You need not give the proof.)
\bigskip
\item{B)} (15) Use the Euclidean algorithm to find the integer
$d = {\rm gcd}(576,99)$ and express $d$ in the form 
$d = m\cdot 576 + n\cdot 99$
for some integers $m,n$.
\bigskip
\item{C)}  (10)  Prove that if $a,b$ are positive integers and 
$a = qb + r$ for integers $q,r$, then ${\rm gcd}(a,b) = {\rm gcd}(b,r)$.
\bigskip
\noindent
II.  
\item{A)} (10) Prove that if there is a solution of the congruence
$a x \equiv b \pmod{n}$, then ${\rm gcd}(a,n) | b$.
\bigskip
\item{B)} (15) For which $[b]$ do solutions $[x]$ of the equation 
$[12][x] = [b]$ exist in ${\bf Z}_{16}$?  Find a solution in each case.
\bigskip
\noindent
III.  Plaintext messages containing capital roman letters (only)
are represented in numerical form by 2-digit blocks, $00, 01, \ldots, 25$
and encrypted using an affine cipher with encryption function 
$f([x]) = [5][x] + [12]$ (in ${\bf Z}_{26}$).  
\bigskip
\item{A)} (10) How is the letter $E$ encrypted in this system?
\bigskip
\item{B)} (10) What is the decryption function? 
\bigskip
\noindent
IV.  
In an RSA public key cryptosystem, the public key information
is $m = 323$ and $e = 11$.  Messages consisting of capital roman
letters and blanks are encoded as 3-digit blocks $000, 001, \cdots, 026$
and encrypted as 3-digit blocks.
\bigskip
\item{A)}  (10) How would the letter $U$ be encrypted?
\bigskip
\item{B)}  (10) What is the (secret) decryption function $g$?
\bigskip
\noindent
{\it Extra Credit}
(10) Show that an integer $n$ is divisible by 11 if and only if
the alternating sum of its base 10 digits is divisible by 11.  
(For instance, $1727$ has alternating digit sum $1 - 7 + 2 - 7 = -11 \equiv 0 \pmod{11}$, 
and $1727 = 11\cdot 157$.)
\bye
