\documentclass{article}
\include{macros}
\title{Homework 2: Congruences\\\sc \Large Due Wednesday, October 3.}
\begin{document}
\maketitle 

Do {\em not} use a computer for problems 2--8, except for basic arithmetic
and to check your work (these problems are easy to solve in PARI).  
Remember to {\bf work in groups} and cite sources of help.
\begin{enumerate}
\item Find complete sets of residues modulo $7$, all of whose elements
are (a) nonnegative, (b) odd, (c) even, (d) prime.

\item Find an integer $x$ such that $37x \con 1\pmod{101}$.

\item What is the order of $5$ modulo $37$?

\item Let $n=\vphi(7!)$.  Compute the prime factorization of~$n$.

\item Find $x, y\in\Z$ such that
$$
  6613x + 8947y = 389.
$$

\item Find an $x\in\Z$ such that
$x \con -4 \pmod{17}$ and $x\con 3\pmod{23}$.

\item Compute 
$7^{100}\pmod{389}$.

\item Find a number $a$ such that $0\leq a < 111$ and
$$
  (102^{70}+1)^{35} \con a\pmod{111}.
$$ 
(See Problem 2.05 on page 217 of Davenport.)


\item Prove that if $n>4$ is composite then 
$$
   (n-1)! \con 0 \pmod{n}.
$$

\item For what values of~$n$ is $\vphi(n)$ odd?

\item Find your own $100$-digit number~$n$ such that
$
  a^{n-1}\con 1\pmod{n}
$
for $a=2,3,5$.

\item Seven thieves try to share a hoard of gold bars equally between
themselves.  Unfortunately, six bars are left over, and in the fight
over them, one thief is killed.  The remaining six thieves, still
unable to share the bars equally since two are left over, again fight,
and another is killed.  When the remaining five share the bars, one
bar is left over, and it is only after yet another thief is killed
that an equal sharing is possible.  What is the minimum number of bars
which allows this to happen?

\item 
 An elderly woman goes to a market where a horse tramples her basket
 crushing her eggs. The horse's honest rider offers to pay for the
 damages and asks her how many eggs she had brought. She doesn't
 remember the exact number, but recalls that when she had taken them
 out two at a time, there was one egg left. The same happened when she
 picked them out three, four, five, and six at a time, but when she
 took them out seven at a time two were left. What is the smallest
 number of eggs she could have had?



\end{enumerate}



\end{document}