Homework 2: Congruences
DUE WEDNESDAY, OCTOBER 3.

William Stein

Date: Math 124 $\quad$ HARVARD UNIVERSITY $\quad$ Fall 2001

Do 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 work in groups and cite sources of help.

1. Find complete sets of residues modulo $7$, all of whose elements are (a) nonnegative, (b) odd, (c) even, (d) prime.

2. Find an integer $x$ such that $37x \equiv 1\pmod{101}$.

3. What is the order of $5$ modulo $37$?

4. Let $n=\varphi (7!)$. Compute the prime factorization of $n$.

5. Find $x, y\in\mathbb{Z}$ such that
   $$6613x + 8947y = 389.$$

6. Find an $x\in\mathbb{Z}$ such that $x \equiv -4 \pmod{17}$ and $x\equiv 3\pmod{23}$.

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

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

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

10. For what values of $n$ is $\varphi (n)$ odd?

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

12. 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?

13. 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?