%q7.tex: 
%begin macros
\baselineskip=14pt
\parskip=10pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\def\g{\bigtriangledown}
\def\S{\cal S}
\nopagenumbers
%end macros
 

\centerline
{
\bf  Quiz \# 7 for Dr. Z.'s Number Theory
}
\bigskip
{\bf NAME:} (print!) $\underline
{\quad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}$
\bigskip
{\bf E-MAIL ADDRESS:} (print!) 
$\underline
{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad}$
\bigskip

{\bf 1.} (3 points) Using the formula, find $\phi(3003)$.

\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip


{\bf 2.} ( 3 points)
State and prove Euler's Classical Formula for the sum-over-divisors of $n$ of $\phi$.
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip

{\bf 3.} (4 points)
For the following prime $p$ and $q$ (let $n=pq$) public key $e$, and encrypted message $c$

(i) Check that $e$ is an OK key, i.e. that it is coprime to $\phi(n)$.

(ii) Find the deciphering key, $d$, such that $de \equiv 1 \pmod{\phi(n)}$

(iii) Suppose Alice sent you the encrypted message $c$. Check that this is an OK message (coprime to $n$), and if it is
 find her original message?, $m$

$p=3 \quad , \quad q=5 \quad , \quad e=5 \quad , \quad c=7$


\end






