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.
 Consider the sequence a_{1}, a_{2}, a_{3}, ...
defined by a_{1}=3, a_{2}=9, and, for i>1,
a_{i+1}=a_{i}+6a_{i1}.
Prove that a_{k}=3^{k} 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 5^{734} modulo 7.
 (c) Compute the least positive residue of 5^{734} modulo 7.
 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.
 One can regard RSA encryption as a map
f: U_{Z/nZ} > U_{Z/nZ}
defined by f(x) = x^{e}, where n = pq is the product of two
different primes p and q,
and e is a positive integer relatively prime to
phi(n) = (p1)(q1). 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 (x^{e})^{d} = x for every x in
U_{Z/nZ}.) Explain what you are doing to find d,
and show your work.
 (b) Explain in terms of Euler's Theorem why
(x^{e})^{d} = x for every x in U_{Z/nZ}.
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.
 x^{3}  2 in Q[x]
 x^{3}  2 in (Z/3Z)[x]
 x^{4} + x + 1 in (Z/2Z)[x]
 x^{3}  2 in R[x]
 x^{3}  2 in C[x]