## 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.
• (a) Give an example of a relation on the set {a,b,c} which is symmetric but not transitive.
• (b) Give an example of a relation on the set {a,b,c} which is reflexive but not an equivalence relation. Justify why your relation is not an equivalence relation.
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.
• (a) Let r be the least positive residue of 734 modulo 6. Find r.
• (b) Explain how Fermat's Little Theorem can be used to simplify the computation of the least positive residue of 5734 modulo 7.
• (c) Compute the least positive residue of 5734 modulo 7.
2. Let f: R -> R be the map on the reals R defined by f(x) = -x.
• (a) Is f a group homomorphism of the reals, regarded as a group under addition? If not, give an explicit example of some property of group homomorphisms that f does not have. If f is a group homomorphism, determine whether or not it is an isomorphism, and explain why it is, or is not, an isomorphism.
• (b) Is f a ring homomorphism of the reals? If not, give an explicit example of some property of ring homomorphisms that f does not have. If f is a ring homomorphism, determine whether or not it is an isomorphism, and explain why it is, or is not, an isomorphism.
• (c) Let h: Z -> (Z/5Z)x(Z/7Z) be the map defined by h(m) = ([m]5,[m]7). This map is in fact a homomorphism. Find an integer m such that h(m) = ([3]5,[2]7). You may use any method to find such an m. If you guess, however, you must verify that your m works. Otherwise, your work should justify your answer.
3. 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)).
• (a) If n = 35 and e = 11, find the decryption exponent d. (Recall that d has the property that (xe)d = x for every x in UZ/nZ.) Explain what you are doing to find d, and show your work.
• (b) Explain in terms of Euler's Theorem why (xe)d = x for every x in UZ/nZ.

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

7. Problem E1, p. 268 of the text.

8. For each of the following polynomials, determine if the polynomial is irreducible in the given ring. Justify your answers.
• x3 - 2 in Q[x]
• x3 - 2 in (Z/3Z)[x]
• x4 + x + 1 in (Z/2Z)[x]
• x3 - 2 in R[x]
• x3 - 2 in C[x]