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

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

3. 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.

4. 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}$ .

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

6. 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.)

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

8. 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.