Exam 1 solutions

Math 116: Finashin, Pamuk, Pierce, Solak

Thursday, April 7, 2011

Problem 1. (15 pts)

(a) Find the greatest common divisor d of 453 and 213. Present d in the form d = 453x + 213y.

(b) If there is one, find a solution to 213x ≡ 12 (mod 453).

(c) Find the least positive integer in {4530x + 2139y: x, y ∈ ℤ}.

Solution. (a) First apply the Euclidean algorithm:

453 = 213 · 2 + 27,
213 = 27 · 7 + 24,
27 = 24 · 1 + 3,
24 = 3 · 8.

So gcd(453, 213) = 3. Also we compute

3 = 27 − 24
= 27 − (213 − 27 · 7)
= 27 · 8 − 213
= (453 − 213 · 2) · 8 − 213
= 453 · 8 − 213 · 17.

(b) By (a), we have 3 ≡ 213 · −17 (mod 453), so

213x ≡ 12 ⟺ 213x ≡ 4 · 3 ≡ 213 · −68.

Therefore the congruence is solved when x ≡ −68 ≡ 385 (mod 453).

(c) 4530x + 2130y = 10(453x + 213y), so the least positive integer in the given set is 10 · 3, or 30 .

Remark. 1. There is a reason why the three parts of this problem are together. One application of the Euclidean algorithm is enough to give the answers of all three parts. (Some people used the algorithm two or three times; this was unnecessary.)

2. The second half of part (a) does not ask you to write “3 = 453x+213y” and then stop; it asks for a solution to this equation.

3. In part (b), one may observe that 3 divides each of 213, 12, and 453, so that

213x ≡ 12 (mod 453) ⟺ 71x ≡ 4 (mod 151).

From part (a) we have 1 = 151 · 8 + 71 · −17, so the congruence is solved by

x ≡ 4 · −17 ≡ −68 ≡ 83 (mod 151),
x ≡ 83, 234, 385 (mod 453).

This is the complete solution, but it was not required to find this: the problem asked just for one solution.

4. In part (c), some people seemed to confuse the least positive integer in the given set with the least common multiple of 4530 and 2130.

5. Part (c) does not ask for the values of x and y such that 4530x + 2130y is minimized among positive integers; it asks for the minimum possible positive value of this expression.

Problem 2. (8pts) Let G be the set of even integers and ∗ be the binary operation on G defined by x ∗ y = x + y + 4. Determine whether (G, ∗) is a group or not. Prove your claim.

Solution. Since x, y, are 4 are even, their sum is also even; so G is closed under ∗. To simplify some computations, we may note also that, since + is commutative, so is ∗. Let us check for an identity. We claim that −4 is an identity with respect to ∗. Indeed,

x ∗ (−4) = x − 4 + 4 = x

(and therefore also (−4) ∗ x = x, by commutativity of ∗). So −4 is an identity. Considering

x ∗ (y ∗ z) = x ∗ (y + z + 4)
= x + (y + z + 4) + 4
= (x + y + 4) + z + 4
= (x + y + 4) ∗ z
= (x ∗ y) ∗ z,

we have that ∗ is associative. Now check for inverses. We claim that −x − 8 is the inverse of x with respect to ∗. We have

x ∗ (−x − 8) = x − x − 8 + 4 = −4

(hence also (−x − 8) ∗ x = −4). Therefore (G, ∗) is a group.

Problem 3. (7pts) Let a ∗ b = a + b + 3ab , does ∗ define a binary operation on the set ℚ_{+} of positive rationals ? Is ∗ associative? Explain.

Solution. Since the sum and product of two positive rationals is again a positive rational, ℚ_{+} is closed under ∗. Therefore ∗ is a binary operation on ℚ_{+}.

For the associativity, we have

a ∗ (b ∗ c) = a ∗ (b + c + 3bc)
= a + (b + c + 3bc) + 3a(b + c + 3bc)
= a + b + c + 3bc + 3ab + 3ac + 9abc.

while

(a ∗ b) ∗ c = (a + b + 3ab) ∗ c
= (a + b + 3ab) + c + 3(a + b + 3ab)c
= a + b + 3ab + c + 3ac + 3bc + 9abc.

So we see that a ∗ (b ∗ c) = (a ∗ b) ∗ c. Hence ∗ is an associative binary operation on ℚ_{+}.

Problem 4. (15pts) Let G be the group (ℤ_{28}, +).

(a) Find all generators of G.

(b) List all the subgroups of G. For each subgroup, different from G, write down all its elements.

Solution. (a) When 0 ≤ k < 28, we have k = 1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27 if and only if gcd(k, 28) = 1. Therefore the generators of G are [1], [3], [5], [9], [11], [13], [15], [17], [19], [23], [25], [27].

(b) The subgroups of G are ⟨[d]⟩, where d | 28; so they are

⟨[1]⟩,  ⟨[2]⟩,  ⟨[4]⟩,  ⟨[7]⟩,  ⟨[14]⟩,  ⟨[28]⟩.

Moreover,

⟨[1]⟩ = ℤ_{28}
⟨[2]⟩ = {[2], [4], [6], [8], [10], [12], [14], [16], [18], [20], [22], [24], [26], [0]}
⟨[4]⟩ = {[4], [8], [12], [16], [20], [24], [0]}
⟨[7]⟩ = {[0], [7], [14], [21]}
⟨[14]⟩ = {[14], [0]}
⟨[28]⟩ = ⟨[0]⟩ = {[0]}

Problem 5. (5pts) Let G be an abelian group and H = {g ∈ G|g^{2} = e}, where e is the identity element of G. Show that H is a subgroup of G.

Solution. Since e^{2} = ee = e, we have e ∈ H: the identity is in H.

Let a, b ∈ H, so that a^{2} = e and b^{2} = e. To show that H is closed under multiplication, consider (ab)^{2}. Since G is abelian, we have

(ab)^{2} = abab = aabb = a^{2}b^{2} = ee = e,

so ab ∈ H. Thus H is closed.

Let a ∈ H, so that a^{2} = e, and let a^{−1} be the inverse of a. Consider

a^{−1}a^{−1} = (a^{−1})^{2} = (a^{2})^{−1} = e^{−1} = e,

so a^{−1} ∈ H.

Therefore, H is a subgroup of G.

Problem 6. (10pts)

(a) Let G be a group. For a ∈ G, define a mapping t_{a} : G ⟶ G by t_{a}(x) = axa^{−1} for all x ∈ G. Prove that t_{a} is an isomorphism.

(b) i)Prove that ℤ_{2} is not isomorphic to ℤ_{3}. ii) Prove that ℤ_{6} is not isomorphic to S_{3}, where S_{3} is the group of permutations on the set {1, 2, 3}.

Solution. (a) If x, y ∈ G, then

t_{a}(xy) = axya^{−1} = axa^{−1}aya^{−1} = t_{a}(x) · t_{a}(y).

So, t_{a} is a homomorphism. Now let x, y ∈ G and t_{a}(x) = t_{a}(y). Then axa^{−1} = aya^{−1}. Since G is a group, it allows left and right cancellation. Therefore x = y. So, t_{a} is one-to-one. Finally, let x ∈ G. We shall show that there is y in G such that t_{a}(y) = x. Let y = a^{−1}xa. Then

t_{a}(y) = t_{a}(a^{−1}xa) = aa^{−1}xaa^{−1} = x.

So, t_{a}(x) is onto. Hence, t_{a}(x) is an isomorphism.

(b) i) Since their orders are different, |ℤ_{2}| = 2 ≠ 3 = |ℤ_{3}|, we cannot find a bijection between the sets, so the groups cannot be isomorphic.

ii) ℤ_{6} is an abelian group, but S_{3} is not. Under an isomorphism being abelian must be preserved: ϕ(xy) = ϕ(yx) since xy = yx, so

ϕ(x) · ϕ(y) = ϕ(xy) = ϕ(yx) = ϕ(y) · ϕ(x).

Remark. In the last part, it would be acceptable to note that ℤ_{6} is cyclic, but S_{3} is not.