Mathematics 243, section 3 – Algebraic Structures Final Examination – December 15, 2012

Directions

You have until 2:00 p.m. to work on this exam. Do problems I - VIII in the blue exam booklet. There are 200 possible regular points and 20 Extra Credit points. I. Let φ, ψ : Z → Z be the mappings defined

φ(x) = \{ \begin{matrix}3x + 1 & if x is odd \\ x/2 & 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) What is the set φ({1, 2, 3, 4})? 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 B ∗ C = B − (B ∩ C). For instance, {1, 2} ∗ {1} = {1, 2} − {1} = {2}. A) (15) Compute the rest of the operation table for ∗ on P. B) (10) Is ∗ a commutative operation? Is it associative? C) (5) Is there an identity element for ∗ in P. If so, what is the identity element? III. A) (15) Let a, b be integers, at least one of which is nonzero. Show that there is an integer

d satisfying the definition of gcd(a, b) that is contained in the set S = {ma+nb | m, n ∈ Z}.

B) (15) Find the integer d = gcd(535, 410) and express d in the form d = 535m + 410n

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

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

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

V. (15) 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\} ,

which is a group under matrix addition. Show that

H = \{( \begin{matrix}0 & a \\ 0 & b \end{matrix} ) | a, b ∈ R\}

is a subgroup of M_{2×2}(R). VI. All parts of this question refer to the group G = Z_{36}, in which the operation is addition mod 36. 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. VII. (10) Let G be a group with operation ∗ and let a ∈ G. Let ℓ_{a} : G → G be the mapping defined by ℓ_{a}(x) = a ∗ x. Show that ℓ_{a} is always a one-to-one and onto mapping. 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 a ∗_{G} b^{−1} ∈ ker(φ). C) (15) Let G be a group and let H be a subgroup of G. Define a relation called

congruence modulo H on G by this rule:

x ≡ y mod H ⇔ xy^{−1} ∈ H.

Show that congruence mod H is an equivalence relation.

Extra Credit (20) From the 2012 Putnam Exam: Let ∗ be a commutative and associative binary operation on a set S. Assume that for every x, y ∈ S, there exists some z ∈ S such that x ∗ z = y. (The z may depend on x and y.) Show that if a, b, c ∈ S and a ∗ c = b ∗ c, then a = b.

Have a peaceful and joyous holiday season!