Mathematics 243, section 1 – Algebraic Structures Final Examination – December 16, 2003

Directions

You have until 11:30 a.m. to work on this exam. Do problems I - IX in the blue exam booklet. There are 200 possible regular points and 20 Extra Credit points. Note: Even if you don’t see how to derive a complete solution to a problem, don’t leave it blank. Partial credit will be given for relevant definitions, ideas that could lead to solutions, and so forth.

I. A) (15) Let p, q represent any propositions. Construct the truth table for the proposition

(p ⇒ q) ⇔ ((p∧ ∼ q) ⇒∼ p)

B) (10) Give the contrapositive form of the statement “If the product of two integers x, y is even, then x is even or y is even.”

II.

A) (15) Let A = Z, the set of all integers. Consider φ : A → A be the mapping defined

by

φ(x) = \{ \begin{matrix}5x & if x is even \\ x − 2 & if x is odd \end{matrix}

Is φ one-to-one? Why or why not? Is φ onto? Why or why not? B) (10) If A is a finite set and φ : A → A is one-to-one, is φ also necessarily onto?

Explain, and/or prove your assertion.

III. A) (20) Give the precise statement and the proof of the Division Algorithm in Z. B) (10) Find the integer d = gcd(753, 154) and express d in the form d = 753m + 154n

for some integers m, n. C) (10) Show that if a, b, c are integers, a|(b · c) and gcd(a, c) = 1, then a|b.

IV. Let f_{0} = 0, f_{1} = 1, and f_{n} = f_{n−1}+f_{n−2} for all n ≥ 2. (The f_{n} are called the Fibonacci numbers; the first few of them are 1, 1, 2, 3, 5, 8, 13, 21, 34, . . ..)

A) (10) Let A = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ). Compute the matrix powers A^{2}, A^{3}, A^{4}. Do you see a pattern

developing? B) (10) (The pattern!) Show by mathematical induction:

( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{n} = ( \begin{matrix}f_{n+1} & f_{n} \\ f_{n} & f_{n−1} \end{matrix} )

for all n ≥ 1.

V. (25) In an RSA public key cryptosystem, the public key consists of the integer m = 323 and the encryption exponent e = 29. What is the decryption exponent d?

VI. Consider the following set of all 2 × 2 matrices with real entries:

G = \{( \begin{matrix}a & b \\ 0 & d \end{matrix} ) | a, b, d ∈ R\} .

A) (10) Show that G is a group under matrix addition. B) (10) Is the set

H = \{( \begin{matrix}1 & n \\ 0 & 1 \end{matrix} ) | n ∈ Z\}

a subgroup of the group from part A? Why or why not?

VII. All parts of this question refer to Z_{30}, in which the operations are addition and multiplication mod 30. A) (10) Which elements of Z_{30} have multiplicative inverses in Z_{30}? B) (10) Find all the elements of the additive group Z_{30} that generate the additive sub-

group ⟨[24]⟩.

VIII. Let G and H be groups and let φ : G → H be a group homomorphism. A) (5) Give the precise definition of the kernel of φ, ker(φ). B) (5) Show that if K = ker(φ) and g ∈ G is an arbitrary fixed element, then gKg^{−1} =

{gkg^{−1} | k ∈ K} is equal to K. C) (5) Show that the relation R on G defined by

xRy ⇔ xy^{−1} ∈ ker(φ)

is an equivalence relation on G.

IX. (10) Are there any elements of order 14 in the symmetric group S_{8}? Why or why not?

Extra Credit (20)

Prove that if G = ⟨a⟩ is a finite cyclic group with o(G) = n, then ⟨a^{k}⟩ = ⟨a^{d}⟩ where d = gcd(n, k).

Have a peaceful and joyous holiday season!