## 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.
• Answer: For example, let R be the relation {(a,b), (b,a)}. This is symmetric, but it is not transitive since it does not include (a,a).
• (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.
• Answer: Just pick one that is reflexive but not, say, symmetric: R = {(a,a), (b,b), (c,c), (a,c)}.
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.
• (a) Let r be the least positive residue of 734 modulo 6. Find r.
• Answer: Since 734 = 6*122 + 2, we see that r = 2.
• (b) Explain how Fermat's Little Theorem can be used to simplify the computation of the least positive residue of 5734 modulo 7.
• Answer: 5734 = 56*122 + 2 = (56)12252, but 56 == 1 (mod 7) by Fermat's Theorem, so (56)12252 == 112252 = 52 = 25 == 4 (mod 7).
• (c) Compute the least positive residue of 5734 modulo 7.
• Answer: As we saw in (b), it is 4.
3. 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.
• Answer: Yes, since f(x+y) = -(x+y) = -x + -y = f(x) + f(y).
• (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.
• Answer: No, since f(1) = -1 is not 1. Also, f(xy) = -xy is not f(x)f(y) = (-x)(-y) = xy.
• (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.
• Answer: We must solve the simultaneous equations
```x == 3 (mod 5)
x == 2 (mod 7)
```
By the first equation, x = 3 + m5, so plugging into the second equation gives 3 + m5 = 2 + n7, or 7n - 5m = 3 - 2 = 1. We can either guess or use Euclid's algorithm to find n = -2 and m = -3, so x = 3 + (-3)5 = -12. We use x = 2 + n7 to check: x = 2 + 7(-2) = -12. Thus m = -12 works: h(-12) = ([3]5,[2]7).
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)).
• (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.
• Answer: We need to solve de == 1 (mod (p-1)(q-1)); i.e., we need to solve 11d == 1 (mod 24). We can use Euclid's algorithm to find 11*11-5*24 = 1, so d = 11.
• (b) Explain in terms of Euler's Theorem why (xe)d = x for every x in UZ/nZ.
• Answer: Firsy, de = 1 + m*phi(n) for some positive integer m. Thus (xe)d = xed = x1 + m*phi(n) = x1(xphi(n))m, but Euler's Theorem tells us that xphi(n) = 1, so we have x1(xphi(n))m = x1(1)m = x11 = x, for all x in UZ/nZ.

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.
• x3 - 2 in Q[x]
• Answer: This polynomial has one real root, and that root is not rational, so this polynomial is irreducible (since a polynomial of degree 2 or 3 is irreducible iff it has a root in the coefficient field).
• x3 - 2 in (Z/3Z)[x]
• This has x+1 is a factor since x = -1 is a root. Thus it is not irreducible.
• x4 + x + 1 in (Z/2Z)[x]
• Answer: If this were not irreducible it would have an irreducible factor of degree 1 or 2. But it has no degree 1 factors, since it has no roots in Z/2Z, and the only irreducible polynomial of degree 2 is x2 + x + 1, which we check is not a fzctor of x4 + x + 1. Thus x4 + x + 1 is irreducible in (Z/2Z)[x].
• x3 - 2 in R[x]
• Answer: This has a real root so it has a linear factor; in fact, x - 21/3 is a factor, so x3 - 2 is not irreducible in R[x]. Alternatively, we know that an irreducible polynomial in R[x] must have degree 1 or 2, so this polynomial cannot be irreducible.
• x3 - 2 in C[x]
• Answer: we know that an irreducible polynomial in C[x] must have degree 1, so this polynomial cannot be irreducible.