This assignment is due next Thursday (10/15) but start it over the weekend so we can discuss it some on Tuesday.

1. (Koffi's problem(s) of the day). Find the last three digits in

   	(20092008)2007
   

   and

   	2009 to the power 20082007.
   

   We don't quite yet have the tools to handle this problem. We will in a week or so. If you don't see how to do it with what you know, get as far as you can, then wait.

2. If you haven't taken abstract algebra, you can skip this problem. But you don't have to - you might be able to make some progress on it anyway.

   All you need to know is that a ring is a set of things you can add and multiply in a way that honors the usual rules of arithmetic, and that an element p in a ring R is prime if whenever you write p = ab, exactly one of a and b is invertible (multiplicatively). (It follows from this definition that the invertible elements are not prime.)

   We count two primes p and q as equivalent when p = aq for an invertible a. So in the integers, +2 and -2 are equivalent primes.

   1. Find a ring with just one prime (up to equivalence).

   2. Find a ring which has noninvertible elements but no primes.

   3. The set T of integers congruent to 1 (mod 4) isn't a ring.

      Why not?

      Nevertheless, you can define primes there. For example, 9 is one since it can't be factored in T. Show that the fundamental theorem of arithmetic fails in T.

3. Practice multiplying polynomials in Z_p[x], the set of polynomials with coefficients mod p. Compute

   	a(x) = (x-1)(x2+2) 
   

   and

   	b(x) = (x-2)(x-3)(x-4(x-5)
   

   mod 7, and mod 11.

4. We will prove next week that the Euclidean algorithm works in Z_p[x], but even before we prove it you can exercise it. Let d(x) be the greatest common divisor of the polynomials a(x) and b(x) in the previous problem. Find polynomials f(x) and g(x) such that

   	f(x)a(x) + g(x)b(x) = d(x).
   

   Of course this is really two problems, one mod 7 and the other mod 11.

   In one of the two problems, a(x) and b(x) are relatively prime, so d(x) = 1. Can you predict which before you do the work?