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

I. Let φ, ψ : ℤ → ℤ be the mappings defined

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

A) What is the set φ({1, 2, 3, 4})?

Solution: By definition, φ({1, 2, 3, 4}) = {φ(1), φ(2), φ(3), φ(4)} = {4, 1, 10, 2}.

B) What is the mapping φ ∘ ψ?

Solution: Since x − 1 is even if x is odd, while x + 1 is odd if x is even we have:

(φ ∘ ψ)(x) = \begin{cases}3(x + 1) + 1 = 3x + 4 & if x is even \\ (x − 1)/2 & if x is odd \end{cases}

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) Compute the rest of the operation table for ∗ on P. Solution:

\begin{matrix}∗ & ∅ & \{1\} & \{2\} & \{1, 2\} \\ ∅ & ∅ & ∅ & ∅ & ∅ \\ \{1\} & \{1\} & ∅ & \{1\} & ∅ \\ \{2\} & \{2\} & \{2\} & ∅ & ∅ \\ \{1, 2\} & \{1, 2\} & \{2\} & \{1\} & ∅ \end{matrix}

B) Is ∗ a commutative operation? Is it associative? Solution: ∗ is not commutative, since for instance {1}∗{1, 2} = ∅, but {1, 2}∗{1} = {2}. It is not associative, since for instance ({1, 2}∗{1})∗{1} = {2}∗{1} = {2}, but {1, 2}∗({1}∗{1}) = {1, 2} ∗ ∅ = {1, 2}.

C) Is there an identity element for ∗ in P. If so, what is the identity element?

Solution: There is no identity element since no row of the table above consists of the same sets as the column labels. (Note that ∅ is a right identity, but not a left identity.)

III.

A) 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 ∈ ℤ}.

Solution: If one of a, b is zero, say b = 0, then gcd(a, b) = |a| = (±1)a, which is an element of S. So now assume that a, b are both nonzero. By adjusting the signs of a, b, we can always produce strictly positive elements in S. Let d be the smallest strictly postive element, which exists by the Well Ordering Principle. We will show that d satisfies the properties of gcd(a, b). First d > 0 is true by construction. Next, we will show d|a. By the division algorithm, we have a = qd + r where 0 ≤ r < d. But a, qd ∈ S, so r = a − qd is in S as well. This shows that r = 0 since r cannot be strictly smaller than d. Similarly, d|b. Now let c be any integer satisfying c|a and c|b, so a = rc and b = sc for some integers r, s. Since d = ma + nb for some integers m, n, we have d = m(rc) + n(sc) = (mr + ns)c. Hence c|d. Therefore d satisfies the properties in the definition of gcd(a, b)

B) Find the integer d = gcd(535, 410) and express d in the form d = 535m + 410n for some integers m, n.

Solution: By the Euclidean Algorithm

535 = 1 · 410 + 125
410 = 3 · 125 + 35
125 = 3 · 35 + 20
35 = 1 · 20 + 15
20 = 1 · 15 + 5.

Therefore gcd(535, 410) = 5, the last nonzero remainder. To find the integers m, n, we use the Extended Euclidean Algorithm table:

1  0
0  1
1 1 −1
3 −3 4
3 10 −13
1 −13 17
1 23 −30

Therefore (535)(23) + (410)(−30) = 5.

C) Assume that a, b, c are integers, d = gcd(a, b), a|c and b|c. Prove that (ab)|(cd).

Solution: By part A above we have d = ma + nb for some integers m, n. Moreover c = ra and c = sb for some integers r, s. Therefore substituting for c in each term and using distributivity, we have

cd = c(ma + nb) = mca + mnb = m(sb)a + n(ra)b = ab(ms + nr)

It follows that ab|cd.

D) An RSA public key cryptographic system has m = 187 and encryption exponent e = 31. What is the corresponding decryption exponent d?

Solution: m = 187 = 11 · 17 so the two primes used to construct the RSA system are p = 11 and q = 17. Hence (p − 1)(q − 1) = 160, and we need to find [d] with [31][d] = [1] in ℤ_{160}. We apply the Euclidean Algorithm again:

160 = 5 · 31 + 5
31 = 6 · 5 + 1.

Then

\begin{aligned}& 1 & 0 \\ & 0 & 1 \\ 5 & 1 & −5 \\ 6 & −6 & 31 \end{aligned}

Therefore (−6)(160) + (31)(31) = 1. Hence d = 31. (This is another case like the one on the review sheet for the final where d = e.)

IV. 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}) .

Solution: With n = 1, there is nothing to prove. Assume that

(\begin{matrix}a & 0 \\ b & a \end{matrix})^{k} = (\begin{matrix}a^{k} & 0 \\ ka^{k−1}b & a^{k} \end{matrix})

and compute

(\begin{matrix}a & 0 \\ b & a \end{matrix})^{k+1} = (\begin{matrix}a & 0 \\ b & a \end{matrix})^{k} (\begin{matrix}a & 0 \\ b & a \end{matrix})

= (\begin{matrix}a^{k} & 0 \\ ka^{k−1}b & a^{k} \end{matrix}) (\begin{matrix}a & 0 \\ b & a \end{matrix})

= (\begin{matrix}a^{k+1} & 0 \\ (k + 1)a^{k}b & a^{k+1} \end{matrix}) ,

which is what we wanted to show. V. Consider the set of all 2 × 2 matrices with real entries:

M_{2×2}(ℝ) = \{(\begin{matrix}a & b \\ c & d \end{matrix}) | a, b, c, d ∈ ℝ\} ,

which is a group under matrix addition. Show that

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

is a subgroup of M_{2×2}(ℝ). Solution: In words, H is the set of all 2 × 2 matrices with zeroes in the first column. H is clearly nonempty since it contains matrices for all choices of a, b ∈ ℝ in the second column. Let A = (\begin{matrix}0 & a \\ 0 & b \end{matrix}) and B = (\begin{matrix}0 & a′ \\ 0 & b′ \end{matrix}) be two arbitrary elements of H. We have

A − B = (\begin{matrix}0 & a \\ 0 & b \end{matrix}) − (\begin{matrix}0 & a′ \\ 0 & b′ \end{matrix}) = (\begin{matrix}0 & a − a′ \\ 0 & b − b′ \end{matrix}) .

Since the matrix A−B also has zeroes in the first column, it belongs to H. Hence by the “shortcut” method (Theorem 3.10), H is a subgroup of M_{2×2}(ℝ). VI. All parts of this question refer to the group G = ℤ_{36}, in which the operation is addition mod 36.

A) Find all generators for G.

Solution: The generators for G are the [a] with gcd(a, 36) = 1, so the elements of {[1], [5], [7], [11], [13], [17], [19], [23], [25], [29], [31], [35]}.

B) Find the elements of the cyclic subgroup ⟨[21]⟩ in G.

Solution: We have

⟨[21]⟩ = {[0], [21], [6], [27], [12], [33], [18], [3], [24], [9], [30], [15]}.

(This is the same as ⟨[3]⟩, since 3 = gcd(21, 36).) C) Find all elements of G of order 9.

Solution: We want all the [a] for which gcd(a, 36) = 4. These are the classes in

{[4], [8], [16], [20], [28], [32]}.

(These are the multiples of [4] by k such that gcd(k, 9) = 1. The number of them is φ(9) = 6.)

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

Solution: Let x, y ∈ G. If ℓ_{a}(x) = ℓ_{a}(y), then a ∗ x = a ∗ y. Since G is a group, though, it contains an inverse for a. We can multiply that on both sides of the equation above (on the left). Then by associativity, (a^{−1} ∗ a) ∗ x = (a^{−1} ∗ a) ∗ y, which shows x = y. This shows that ℓ_{a} is one-to-one. Now let y ∈ G be arbitrary. The equation y = ℓ_{a}(x) = a ∗ x is true for x = a^{−1} ∗ y. Therefore ℓ_{a} is onto.

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) Show that ker(φ) is a subgroup of G.

Solution: ker(φ) = {x ∈ G | φ(x) = e_{H}}. We know that this is nonempty, since φ(e_{G}) e_{H}. Hence e_{G} ∈ ker(φ). Next, let x, y be two arbitrary elements of ker(φ). Since φ is a group homomorphism, we have

φ(x ∗ y^{−1}) = φ(x) ∗ φ(y^{−1})
= φ(x) ∗ φ(y)^{−1}
= e_{H} ∗ (e_{H})^{−1}
= e_{H}.

Hence ker(φ) is a subgroup of G by the “shortcut” criterion.

B) Let c ∈ H, and let a, b ∈ φ^{−1}({c}), (the inverse image under the mapping φ). Prove that a ∗_{G} b^{−1} ∈ ker(φ).

Solution: By the same reasoning as above, if φ(a) = c = φ(b),

φ(a ∗_{G} b^{−1}) = φ(a) ∗_{H} φ(b^{−1})
= φ(a) ∗_{H} φ(b)^{−1}
= c ∗_{H} c^{−1}
= e_{H}.

Therefore a ∗_{G} b^{−1} ∈ ker(φ).

1. C) 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.

Solution: Congruence mod H is reflexive since for all x ∈ G, xx^{−1} = e_{G} ∈ H. If x ≡ y mod H, then xy^{−1} ∈ H. This implies (xy^{−1})^{−1} = yx^{−1} is in H since H is a subgroup, hence closed under inverses. Therefore y ≡ x mod H too, and congruence mod H is symmetric. Finally, if x ≡ y mod H and y ≡ z mod H, then xy^{−1} ∈ H and yz^{−1} ∈ H. It follows that (xy^{−1})(yz^{−1}) = x(y^{−1}y)z^{−1} = xz^{−1} is in H since H is a subgroup and hence closed under products. Therefore x ≡ z mod H, and congruence mod H is transitive.

Extra Credit – 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.

Solution: Letting x = a ∗ c = b ∗ c and y = a, the given information says there exists some w ∈ S such that

(1)  (a ∗ c) ∗ w = a = (b ∗ c) ∗ w.

Similarly, with x = b ∗ c = a ∗ c and y = b, there exists some u ∈ S such that

(2)  (b ∗ c) ∗ u = b = (a ∗ c) ∗ u.

By associativity and commutativity, and using (2) and then (1),

(a ∗ c) ∗ w ∗ c ∗ u = ((a ∗ c) ∗ u) ∗ (c ∗ w) = b ∗ (c ∗ w) = (b ∗ c) ∗ w = a.

But on the other hand using (1) and then (2),

(a ∗ c) ∗ w ∗ c ∗ u = (b ∗ c) ∗ w ∗ c ∗ u = ((b ∗ c) ∗ w) ∗ (c ∗ u) = a ∗ (c ∗ u) = (a ∗ c) ∗ u = b.

Therefore a = b. (There are many other correct ways to solve this one as well. This is just the first proof I found as I was thinking about the problem! For instance, you can “cook up” an identity element and inverses from the given information. However, you cannot use things like the existence of inverses without proving that they exist.)