課程名稱︰離散數學
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2016.06.23
考試時限（分鐘）：
試題 :
Discrete Mathematics
Final Examination on June 23, 2016
Spring Semester, 2016
Problem 1 (10 points)
Let (R, +, ·) be a ring with unity. Prove the following statements.
(1) (5 points) The unity is unique.
(2) (5 points) If x is a unit of R, then the multiplicative inverse of x is
unique.
Ans: (1) For all x ∈ R, assume that there are two unities u_1 and u_2 ∈ R
where x · u_1 = u_1 · x = x and x · u_2 = u_2 · x = x. Then
u_1 = u_2 and so the claim holds.
(2) Let x ∈ R be a unit and u denote the unity of R. Suppose that
r_1, r_2 ∈ R both satisfy the properties of multiplicative inverses
of x, which are x · r_1 = r_1 · x = u and x · r_2 = r_2 · x = u.
Then it is clear that
r_1 = r_1 · u = r_1 · (x · r_1) = r_1 · (x · r_2)
= u · r_2 = r_2.
Problem 2 (10 points)
Let (G, o) and (H, o') be two groups, and f : G → H be a group homomorphism
onto H. If G is abelian, prove that H is a abelian.
Ans: Let g_1 and g_2 in G. Then there exist h_1 and h_2 in H so that
f(g_1) = h_1 and f(g_2) = h_2. Hence, h_1 o' h_2 = f(g_1) o' f(g_2) =
f(g_1 o g_2) = f(g_2 o g_1) = f(g_2) o' f(g_1) = h_2 o' h_1.
Problem 3 (10 points)
Let S_6 be a group of all permutations of {1, 2, 3, 4, 5, 6}, and
╭ 1 2 3 4 5 6 ╮ ╭ 1 2 3 4 5 6 ╮
α = │ │, β = │ │
╰ 2 4 3 1 6 5 ╯ ╰ 3 4 1 5 2 6 ╯
be two elements of S6.
(1) (5 points) Express the cycle decomposition (product of disjoint cycles)
of α.
(2) (5 points) Express the cycle decomposition for αβ.
Ans: (1) α = (124)(3)(56).
(2) αβ = (143)(256).
Problem 4 (10 points)
Let h(x) = x^4 + x^3 + x^2 + x + 1 ∈ Z_2[x]. Prove that h(x) is irreducible.
Ans: Since h(0) = h(1) = 1, h(x) has no first-degree factors. Now we examine
the second-degree factors. Assume that (x^2 + ax + b)(x^2 + cx + d) =
x^4 + x^3 + x^2 + x + 1. By expanding the aforesaid equation and comparing
the coefficients, it is easy to obtain
a + c = 1,
ac + b + d = 1,
ad + bc = 1,
bd = 1,
As bd = 1, it follows that b = d = 1, so ac = 1 and furthermore a = c = 1.
This implies a + c = 0, a contradiction. Hence, h(x) is irreducible.
Problem 5 (10 points)
Let G be a group. Please explain that for all a, b ∈ G,
-1 -1
(a) (a ) = a
-1 -1 -1
(b) (ab) = b a
Ans: -1 -1 -1
(a) As aa = e = a a, the inverse of a is a.
-1 -1 -1 -1 -1 -1
(b) As (ab)(b a ) = a(bb )a = aea = aa = e, the inverse of ab
-1 -1
is b a .
Problem 6 (10 points)
Assume that G is a group, H ⊆ G and H ≠ ψ. Prove that H is a subgroup of G
if for all a, b ∈ H, ab^(-1) ∈ H.
Ans: (i) Identity: Because H ≠ ψ, there exists an a ∈ H, which implies
aa^(-1) = e ∈ H.
(ii) Inverse: For all a ∈ H, ea^(-1) = a^(-1) ∈ H, because e ∈ H.
(iii) Closure: For all a, b ∈ H, a(b^(-1))^(-1) = ab ∈ H,
for b^(-1) ∈ H.
(iv) Associativity: See p. 788 on the slides.
Problem 7 (10 points)
G is a group, H ⊆ G, H ≠ ψ and H is finite. Prove that H is a subgroup of G
if for all a, b ∈ H, ab ∈ H. (Hint: Cite the theorem of the previous problem)
Ans: Because H ≠ ψ, there exists an a ∈ H so that a^1, a^2, a^3, … ∈ H
by the closure property. Because H is finite, there exists i < j and
a^i = a^j, which implies e = a^(j-i) = aa^(j-i-1) = a^(j-i-1)a. Hence,
a^(-1) = a^(j-i-1) ∈ H. Then, for all a, b ∈ H, ab^(-1) ∈ H, because
of b^(-1) ∈ H and the closure property. The theorem of the previous
problem then implies H is a subgroup of G.
Problem 8 (10 points)
Define the binary operation ⊕ and ⊙ on Z by x ⊕ y = x + y - 7,
x ⊙ y = x + y - 3xy, for any x, y ∈ Z. Show that (Z, ⊕, ⊙) is not a ring.
Ans: Take x = y = z = 1, x, y, z ∈ Z. Then
╭ x ⊙ (y ⊕ z) = 1 ⊙ (1 ⊕ 1) = 1 ⊙ (-5) = 11
<
╰ (x ⊙ y) ⊕ (x ⊙ z) = (1 ⊙ 1) ⊕ (1 ⊙ 1) = (-1) ⊕ (-1) = -9
Since x ⊙ (y ⊕ z) ≠ (x ⊙ y) ⊕ (x ⊙ z) disobey the distributive law,
(Z, ⊕, ⊙) is not a ring.
Problem 9 (10 points)
Consider the following two polynomials: p(x) = 1 + 2x + x^3,
q(x) = 3 + x^2 + 2x^3 over the ring (Z_4, +, ·).
(a) Find p(x) + q(x).
(b) Find p(x) · q(x).
Ans: (a) p(x) + q(x) = (1 + 2x + x^3) + (3 + x^2 + 2x^3)
= 4 + 2x + x^2 + 3x^3
= 2x + x^2 + 3x^3
(b) p(x) · q(x) = (1 + 2x + x^3) · (3 + x^2 + 2x^3)
= 3 + 6x + x^2 + 7x^3 + 4x^4 + x^5 + 2x^6
= 3 + 2x + x^2 + 3x^3 + 0 + x^5 + 2x^6
= 3 + 2x + x^2 + 3x^3 + x^5 + 2x^6
Problem 10 (10 points)
Find the multiplicative inverses of all elements of Z_11 and Z_13.
Ans: (a) In Z_11, 1^(-1) = 1, 2^(-1) = 6, 3^(-1) = 4, 4^(-1) = 3, 5^(-1) = 9,
6^(-1) = 2, 7^(-1) = 8, 8^(-1) = 7, 9^(-1) = 5, 10^(-1) = 10.
(b) In Z_13, 1^(-1) = 1, 2^(-1) = 7, 3^(-1) = 9, 4^(-1) = 10, 5^(-1) = 8,
6^(-1) = 11, 7^(-1) = 2^(-1), 8^(-1) = 5, 9^(-1) = 3, 10^(-1) = 4,
11^(-1) = 6, 12^(-1) = 12.