<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%hw16.tex: Homework assignment 16
%%a Plain TeX file by Doron Zeilberger

%begin macros
\nopagenumbers
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros

\centerline
{
\bf Dr. Z.'s Number Theory Homework assignment 16
}




{\bf 1.} Check Euler's theorem for ({\bf a.}) $n=15$ \quad ({\bf b.}) $n=24$ ({\bf c.}) $n=21$

{\bf 2.} For the following primes $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$

{\bf a.} $p=11, q=7, e=9, c=20$

{\bf b.} $p=11, q=5, e=9, c=10$

{\bf c.} $p=3, q=13, e=2, c=10$

{\bf 3.} State and prove Euler's Theorem.





\end
</pre></body></html>