Mathematics 243, section 3 – Algebraic Structures Exam 3 – December 5, 2012

Directions

Do all work in the blue exam booklet. There are 100 possible regular points and 10 Extra Credit points.

I. In an RSA public key cryptosystem, the public key information is m = 323 and e = 13. Messages consisting of capital roman letters and blanks are encoded as 3-digit blocks 000, 001, ⋯, 026 (with blank = 000, A = 001, B = 002, ... , Z = 026) and encrypted as 3-digit blocks.

A) (15) How would the plaintext symbol N be encrypted?

B) (15) What is the (secret) decryption exponent d?

II. (20) Let

H = \{( \begin{matrix}a & b \\ 0 & 1 \end{matrix} ) | a, b ∈ R and a ≠ 0\}

Is H a group under the operation of matrix multiplication? If so, give a proof. If not, say which of the group properties fail. Note: We discussed a general rule for finding the multiplicative inverse of a 2 × 2 matrix on a problem set earlier in the semester. If you don’t remember it, you can “buy” it from me during the exam in return for a reduction of 5 points on your score for this problem.

III. A) (15) Let G be a cyclic group with generator a. Show that every subgroup of G is also

cyclic.

The next parts of this question refer to Z_{24}, which is a cyclic group under addition mod 24.

B) (10) How many different subgroups does Z_{24} contain, including Z_{24} itself and {[0]}?

C) (15) Show that if gcd(a, 24) = 1, then ϕ : Z_{24} → Z_{24} defined by ϕ([x]) = [ax] is a 1-1 and onto group homomorphism.

IV. (10) Let G be a group with operation written as multiplication, let H be a subgroup of G, and let a ∈ G be a fixed element. Let aH = {ah | h ∈ H}. Show that aH is a subgroup of G if and only if a ∈ H.

Extra Credit (10) A group G is generated by elements x, y satisfying x^{n} = e, y^{2} = e, and yx = x^{n−1}y. Show that all of the elements x^{ℓ}y for ℓ = 0, 1, …, n − 1 have order 2.

The General Pattern for 2 × 2 Matrix Inverses If

A = ( \begin{matrix}a & b \\ c & d \end{matrix} )

then A has a inverse matrix (for multiplication) if and only if det(A) = ad − bc ≠ 0, and then

A^{−1} = ( \begin{matrix}\frac{d}{ad−bc} & \frac{−b}{ad−bc} \\ \frac{−c}{ad−bc} & \frac{a}{ad−bc} \end{matrix} )