Mathematics 243, section 1 – Algebraic Structures Final Examination – December 13, 2006

Directions

You have until 11:30 a.m. to work on this exam. Do problems I - IX in the blue exam booklet. There are 200 possible points. I. Let φ, ψ : Z → Z be the mappings defined

φ(x) = \{ \begin{matrix}3x & if x is odd \\ 1 & if x is even \end{matrix}
ψ(x) = \{ \begin{matrix}x + 1 & if x is odd \\ x − 1 & if x is even \end{matrix}

A) (10) Is ψ a permutation of Z? Prove your assertion. B) (10) What is the mapping φ ∘ ψ? II. Let A = {1, 2} and let P = {∅, {1}, {2}, {1, 2}} (the collection of all subsets of A). Let + be the binary operation on P defined by C + D = (C ∪ D) − (C ∩ D). For instance, {1} + {1, 2} = {1, 2} − {1} = {2}. A) (15) Compute the rest of the operation table for + on P. B) (5) Is there an identity element for + in P. If so, what is the identity element? III. (10) Prove by contradiction: if A = {a_{1}, …, a_{n}} is a finite set and φ : A → A is surjective then φ is also injective. IV. A) (5) Let a, b be two integers, at least one of which is nonzero. Give the definition of a

gcd of a, b. B) (15) Find the integer d = gcd(537, 411) and express d in the form d = 537r + 411s for

some integers r, s. C) (15) Assume that a, b, c are integers, d = gcd(a, b), a|c and b|c. Prove that ab|cd. D) (20) An RSA public key cryptographic system has m = 209 and encryption exponent

e = 37. What is the corresponding decryption exponent d? V. (20) Prove by mathematical induction: for all real numbers a, b and all n ≥ 1:

( \begin{matrix}a & b \\ 0 & a \end{matrix} )^{n} = ( \begin{matrix}a^{n} & na^{n−1}b \\ 0 & a^{n} \end{matrix} ) .

VI. (20) Consider the set of all 2 × 2 matrices with real entries:

M_{2×2}(R) = \{( \begin{matrix}a & b \\ c & d \end{matrix} ) : a, b, c, d ∈ R\} .

Show that M_{2×2}(R) is a group under matrix addition:

( \begin{matrix}a & b \\ c & d \end{matrix} ) + ( \begin{matrix}e & f \\ g & h \end{matrix} ) = ( \begin{matrix}a + e & b + f \\ c + g & d + h \end{matrix} ) .

VII. All parts of this question refer to the group G = Z_{27}, in which the operation is addition mod 27. A) (5) Find all generators for G. B) (5) Find the elements of the cyclic subgroup ⟨[21]⟩ in G. C) (5) Find all elements of G of order 9. VIII. Let G and H be groups with identity elements e_{G} and e_{H} respectively, and let φ : G → H be a group homomorphism. A) (15) Show that ker(φ) is a subgroup of G. B) (5) Let c ∈ H, and let a, b ∈ φ^{−1}({c}), (the inverse image under the mapping φ).

Prove that ab^{−1} ∈ ker(φ). C) (5) Prove that φ is injective if and only if ker(φ) = {e_{G}}. IX. (10) Let G be a group, and let x, y ∈ G. The conjugacy relation R on G is defined as follows. We say x and y are conjugate in G, xRy, if there exists an a ∈ G such that y = axa^{−1}. Show that the conjugacy relation is an equivalence relation on G.

Have a peaceful and joyous holiday season!