课程名称：离散数学
课程性质︰资讯工程学系选修
课程教师︰陈健辉
开课学院：电机资讯学院
开课系所︰资讯工程学系
考试日期（年月日）︰2014/05/16
考试时限（分钟）：原定120，延长20
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
Examination #2
(范围:Algebra)
1. Prove that if 3|n^2, then 3|n, where n is a positive integer, by the methods
of
(a) p->q <=> not q -> not p; (5%)
(b) contradiction; (5%)
2. Let (K, ‧, +) be a Boolean algebra. The following is a proof of a‧(a+b)=a
for every a, b \in K.
a‧(a+b) = (a‧a)+(a‧b) = a+(a‧b) = (a‧1)+(a‧b)
= a‧(1+b) = a‧1 = a.
Please prove a+(a‧b)=a for every a, b \in K. (10%)
3. Is the following argument correct or wrong? Why? (10%)
Suppose that R is a binary relation on a non-empty set A. If R is
symmetric and transitive, then R is reflexive.
Proof. Let (x, y) \in R. By the symmetric property, we have (y, x) \in
R. Then, with (x, y), (y, x) \in R, it follows by the transitive
property that we have (x, x) \in R. As a consequence, R is reflexive.
4. Define a R b if and only if a ≡ b(mod n). Prove that R is an
equivalence relation on Z. (10%)
5. Suppose that (R, +, ‧) is a commutative ring with unity. Prove that R is an
integral domain if and only if for a, b, c \in R and a ≠ z, a‧b=a‧c
=> b=c. (10%)
6. Define two binary operations⊕, ⊙ on Z as follows: a⊕b = a+b-1 and a⊙b =
a+b-ab. Then, (Z, ⊕, ⊙) is a commutative ring with unity. Please find (1)
the zero of Z; (2) the inverse of a under ⊕; (3) the unity of Z. (6%)
Also show that Z has no proper divisor of zero. (4%)
7. Consider the ring (Z, ⊕, ⊙). Prove that for each integer 0<a<n, if
gcd(a, n)>1, then [a] is a proper zero divisor of Z_n. (10%)
8. Let f: (R, +, ‧) -> (S, ⊕, ⊙) be a ring homomorphism. Prove that if A is a
subring of R, then f(A) is a subring of S. (hints: you need to show the
closure property and inverse property) (10%)
9. A positive integer solution for x ≡ a_i(mod m_i), i=1, 2, ..., k, where
k≧2, m_i≧2 is an integer, 0≦a_i≦(m_i)-1 is an integer, and gcd(m_i, m_j)
= 1 for all 1≦i≦j≦k, can be obtained as follows.
●Compute M_i = m_1...m_(i-1)*m_(i+1)...m_k for all 1≦i≦k.
●Find x_i satisfying M_i*x_i ≡ 1(mod m_i) for all 1≦i≦k.
●x = a_1*M_1*x_1 + a_2*M_2*x_2 + ... + a_k*M_k*x_k.
Explain why the obtained x is a solution. (5%)
Also find all solutions. (5%)
10.Suppose that (G, ‧) is a group and a \in G. Prove that the inverse of a is
unique. (10%)
11.Explain why a cyclic group is abelian and why the group (S_4, ‧) is not
cyclic, where S_4 is the set of 24 permutations on {1, 2, 3, 4} (e.g.,
1 2 3 4 1 2 3 4
( ) \in S_4) and ‧ denotes function composition(e.g., ( )
2 4 3 1 2 4 3 1
1 2 3 4 1 2 3 4
‧( ) = ( ). (10%)
2 1 3 4 1 4 3 2
12.Let G be a group with subgroups H and K. If |G| = 330, |K| = 22, and K
\subset H \subset G, what are the possible values for |H|? (10%)

∈⊂