THEORY OF NUMBERS, Math 115 A Homework 6 Due Wednesday November 15 2002

1. (6.1 6) What is the remainder when 7 · 8 · 9 · 15 · 16 · 17 · 23 · 24 · 25 · 43 is divided by 11?

2. (6.1 12) Using Fermat’s little theorem, find the least positive residue of 2^{1000000} modulo 17.

3. (6.1 34) Show that if p is a prime and 0 < k < p, then (p − k)!(k − 1)! ≡ (−1)^{k} modulo p.

4. (6.1 40,41) Using the fact that p divides the binomial coefficient \binom{p}{k} when k is less than p show that if a, b are integers then (a + b)^{p} ≡ a^{p} + b^{p}. Use this to prove Fermat’s little theorem.

5. (6.2 2) Show that 45 is a pseudoprime to the bases 17 and 19.

6. (6.2 20) Show that if n is a Carmichael number then n is square free.

7. (6.2 1 computer exploration) Determine for which positive integers n, n ≤ 100, the integer n2^{n} − 1 is prime.

8. (6.3 6) Find the last digit of the decimal expansion of 7^{999,999}.

9. (6.3 10) Show that a^{ϕ(b)} + b^{ϕ(a)} ≡ 1 (mod ab) if a,b are relatively prime positive integers.

10. (6.3 2 computational exploration) Find ϕ(n) for all integers less than 1000. What conjecture can you make about the values of ϕ(n).