\documentclass[12pt]{article}

\usepackage{amsmath,amscd,amsbsy,amssymb,latexsym,url}
\usepackage{epsfig,graphicx,subfigure}
\usepackage{enumitem,balance,mathtools}
\usepackage{wrapfig}
\usepackage{tikz} \setlength\oddsidemargin{-0.05in}
\usetikzlibrary{calc} \setlength\evensidemargin{-0.05in}
\setlength\textheight{8.7in} \setlength\topmargin{-0.1in}
\setlength\textwidth{6.3in}
\usepackage{mathrsfs, euscript}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exercise}{Exercise}[section]
%\newtheorem{solution}{section}

\setcounter{section}{1} \numberwithin{equation}{section}
\numberwithin{figure}{section}

\newenvironment{proof}[1][Proof:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{definition}[1][Definition:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{solution}[1][Solution:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\qed}{\nobreak \ifvmode \relax \else
      \ifdim\lastskip<1.5em \hskip-\lastskip
      \hskip1.5em plus0em minus0.5em \fi \nobreak
      \vrule height0.4em width0.5em depth0.25em\fi}
\newcommand{\hw}[1]{#1}%includes solutions
%\newcommand{\hw}[1]{}
\newcommand{\indt}[1]{\begin{list}{\setlength\leftmargin{0.5in}}\item{}#1\end{list}\noindent}
\def\Prob{\text{Prob}}
\def\prob{\text{Prob}}
\begin{document}
\noindent

%========================================================================
\begin{center}
\textbf{\Large{Homework 5}} \vspace{2mm}

Mathematics in Computer Science
%John E. Hopcroft
\end{center}
\vspace{1mm}

\begin{enumerate}
  \item What is $800^{35}\pmod {11}$?

  \item
    \begin{enumerate}
      \item if $i\ge 0$ what is $i\pmod p$?
      \item if $i<0$ what is $i\pmod p$?
    \end{enumerate}
    %
   %
    \item  Solve\[\begin{array}{ll}3x+2y=1&\pmod 7\\x-y=5&\end{array}\]
    %
  \item
  \begin{enumerate}
    \item Use Euclead's algorithm to compute the gcd of 495 and 210.
    Write out the steps.
    \item What is the prime factorization of 495 and of 210?
    \item Is your answer to part (a) correct?
  \end{enumerate}
  %
  \item (Extended Eucleadean Algorithm)  What is multiplicative
  inverse of 400 mod 997?

  \item What is the relationship between $a\times b$, $\gcd (a,b)$,
  and $\rm{lcm} (a,b)$?
  %
  \item I wish to calculate the value of a number of ten digits
  numbers such as 4756213912 mod 9.  Prove that I can get the correct
  answer by adding the digits and taking the result mod 9.
  %
  %
  \item Consider the integers mod $p$.  Notice that certain numbers
  are perfect squares.  For example, $3^2=2\text{ mod } p$.
    \begin{enumerate}
    \item What fraction of the numbers mod $p$ are perfect squares?
    Hint: Explore integers modulo a small prime like 7 or 11.
    \item Give a proof of your answer to a.
    \end{enumerate}
   %
   \item
    \begin{enumerate}
      \item Prove that $=\pmod p$ is an equivalence relation.
      \item Note that in mod arithmetic one represents each equivalence
      class by a representative of the class and defines arithmetic
      for the representative elements. If $p=3$ what are the
      addition and multiplication tables for the representative
      elements?
    \end{enumerate}
    %
\end{enumerate}

\underline{Think about the following question (Optional, no need for submission)}

\begin{enumerate}
\item Your task is to design a "prove" problem, which needs to be proved by  the induction proof method, but you have to use a stronger induction hypothesis (than the problem itself) during the induction step.
\end{enumerate}
%========================================================================
\end{document}
