%hw9.tex: Homework assignment 9
%%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 9
}

{\bf 1.} Find

{\bf i.} $1001  \pmod {13}$  \quad {\bf ii.} $1001  \pmod {17}$  \quad {\bf iii.} $10001  \pmod {1007}$ 

{\bf 2.} True or False?

{\bf i.} {\bf i.} $10^{100}+10^{98}+1 \equiv  10^{98}+1\pmod {10^{100}}$   
\quad {\bf ii.} $10^{100}+10^{98}+1 \equiv  10^{98}+2\pmod {10^{100}}$  

{\bf 3.} Find $ 91 + 87 + 85 + 103 \pmod {105}$

({\bf Tip}: If $a > m/2$ then it is more convenient to replace $a$ by $a-m$.

{\bf 4.} {\bf i.} Compute $2001 \cdot 207 \pmod {1000}$.

{\bf ii.} Compute $2009 \cdot 2011 \pmod {2010}$.


{\bf 5.} Compute $13^{5} \pmod {15}$ using (a) the slow way. (b) the fast way. (c) the other fast way.

{\bf 6.} Compute $13^{18} \pmod {15}$ using (a) the fast way. (b) the other fast way.


{\bf 7.} Find the last (decimal) digit of $7^{1024}$

{\bf 8.} Find the three last (decimal) digit of $7^{1024}$



\end
