Math 480 (Spring 2007): Homework 2

Due: Monday, April 9


There are 8 problems. Each problem is worth 6 points and parts of multipart problems are worth equal amounts. (Note: 6 points each, instead of 5 this time.)
Office Hours. My official office hours are on Thursdays 4-6pm in Padelford C423.

    1. Prove that for any positive integer $ n$ , the set $ (\mathbb{Z}/n\mathbb{Z})^*$ under multiplication modulo $ n$ is a group.
    2. Prove that for any positive integer $ n$ , the set $ \mathbb{Z}/n\mathbb{Z}$ under addition and multiplication modulo $ n$ is a ring.

  1. Prove that for every positive integer $ n$ the integer $ 5^{2n} +
3\cdot 2^{5n-2}$ is divisible by $ 7$ .

  2. Let $ f(x)=x^3+a \in\mathbb{Z}[x]$ be a cubic polynomial with integer coefficients, e.g., $ f(x)=x^3+1$ .
    1. Formulate a conjecture about when the set $ \{ f(n) : n\in \mathbb{Z}$ and $f(n)$ is prime$ \}$ is infinite.
    2. Give numerical evidence that supports your conjecture.

  3. Prove the following statements:
    1. If $ a$ is an odd integer, then $ a^2\equiv 1\pmod{8}$ .
    2. For any integer $ a$ , we have $ a^3 \equiv 0,1,$ or $ 6\pmod{7}$ .
    3. For any integer $ a$ , we have $ a^4 \equiv 0$ or $ 1\pmod{5}$ .

  4. Find rules for divisibility of an integer by $ 5$$ 9$ , and $ 11$ , and prove each of these rules using arithmetic modulo a suitable $ n$ .

  5. What is the multiplicative order of $ 3$ modulo $ 17$ ? (You may use any method (even a computer) to answer this question, as long as you explain what you do.)

  6. A basket has $ n$ eggs in it. One egg remains when the eggs are removed from the basket 2, 3, 4, 5, or 6 at a time. No egg remains if they are removed 7 at a time. Find the smallest number $ n$ of eggs that could be in the basket.

    1. Verify by hand the equation $ \sum_{d\mid n} \varphi(d) = n$ in the case $ n=12$ . Here we are summing over the positive divisors of $ n$ .
    2. Verify by computer that $ \sum_{d\mid n} \varphi(d) = n$ for $ n=1000$ . In your solution make sure to explain exactly what you type into the computer, and what program you use.



William 2007-04-04