Old Final

This is the final from Spring 2006. I removed from this anything not relevant to what we covered, so all of the remaining problems are relevant for this fall.
  1. Consider the sequence a1, a2, a3, ... defined by a1 = 3, a2 = 9, and, for i>1, ai+1 = ai+6ai-1. Prove that ak = 3k for all for all k>0.
  2. Answer: Check the base cases: a1 = 3 and a2=9 both satisfy the rule ak = 3k. Now assume that ak = 3k holds for all k up to some n, where n >= 2. Then an+1 = an+6an-1 by definition, and an+6an-1 = 3n+6*3n-1 by our induction hypothesis, so an+1 = 3n+6*3n-1 = 3n+2*3n = 3*3n = 3n+1. It now follows that ak = 3k for all for all k>0.
  3. Let f: R -> R be the map on the reals R defined by f(x) = -x.
  4. One can regard RSA encryption as a map f: UZ/nZ -> UZ/nZ defined by f(x) = xe, where n = pq is the product of two different primes p and q, and e is a positive integer relatively prime to phi(n) = (p-1)(q-1). The decryption exponent d is a solution to ed == 1 (mod phi(n)).

  5. Here are a few additional problems on material we covered the last two weeks of the semester. These problems were not on the old final.

    6. Problem E13(i), p. 252 of the text.
    Answer: See the back of the book.
    7. Problem E1, p. 268 of the text.
    Answer: See the back of the book.
    8. For each of the following polynomials, determine if the polynomial is irreducible in the given ring. Justify your answers.