課程名稱：離散數學
課程性質︰資訊工程學系選修
課程教師︰陳健輝
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰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%)

∈⊂