Mathematics 243, section 1 – Algebraic Structures Exam 2, November 5, 2003

Directions: Do all work in the blue exam booklet. There are 100 possible points.

I. A) (10) Give the precise statement of the division algorithm in Z. (You need not give

the proof.)

B) (15) Use the Euclidean algorithm to find the integer d = gcd(576, 99) and express d in the form d = m · 576 + n · 99 for some integers m, n.

C) (10) Prove that if a, b are positive integers and a = qb + r, then gcd(a, b) = gcd(b, r).

II. A) (10) Prove that if there is a solution of the congruence ax ≡ b (mod n), then

gcd(a, n)|b.

B) (15) For which [b] do solutions [x] of the equation [12][x] = [b] exist in Z_{16}? Find a solution in each case.

III. Plaintext messages containing capital roman letters (only) are represented in numerical form by 2-digit blocks, 00, 01, …, 25 and encrypted using an affine cipher with encryption function f([x]) = [5][x] + [12] (in Z_{26}).

A) (10) How is the letter E encrypted in this system?

B) (10) What is the decryption function?

IV. In an RSA public key cryptosystem, the public key information is m = 323 and e = 11. Messages consisting of capital roman letters and blanks are encoded as 3-digit blocks 000, 001, ⋯, 026 and encrypted as 3-digit blocks.

A) (10) How would the letter U be encrypted?

B) (10) What is the (secret) decryption function g?

Extra Credit (10) Show that an integer n is divisible by 11 if and only if the alternating sum of its base 10 digits is divisible by 11. (For instance, 1727 has alternating digit sum 1 − 7 + 2 − 7 = −11 ≡ 0 (mod 11), and 1727 = 11 · 157.)