%hw10.tex: Homework assignment 10
%%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 10
}

{\bf 1.} Without actually solving, 
find out how many solutions there are in $\{0,1, \dots n-1\}$ where $n$ is the modulo.

{\bf i.} $7x \equiv 2 \pmod{11}$

{\bf ii.} $42x \equiv 12 \pmod{66}$

{\bf iii.} $15x \equiv 64 \pmod{35}$

{\bf iv.} $10^{10}x \equiv 64 \pmod{11^{100}}$

{\bf 2.} Using Brute Force, solve
$$
5x \equiv 6 \pmod {13} \quad .
$$

{\bf 3.}: Find, or explain why it does not exist

{\bf i.} $3^{-1} \pmod {35}$.

{\bf ii.} $7^{-1} \pmod {35}$.

{\bf iii.} $7^{-1} \pmod {125}$.

{\bf iv.} $5^{-1} \pmod {21}$.

{\bf 4.} Solve, if possible, the following linear congruences.

{\bf i.} $ 3x \equiv 8 \pmod {35}$

{\bf ii.} $ 7x \equiv 100 \pmod {35}$

{\bf iii.} $7x \equiv 97 \pmod {125}$.

{\bf iv.} $25x \equiv 75  \pmod {105}$.

{\bf 5.} Solve the system of linear congruences
$$ 
3x \equiv 8 \pmod {35} \quad , \quad 5x \equiv 2 \pmod {11} \quad .
$$

\end