3 (mod 17).
1. The message below was enciphered using the following method. First, a substituion was
applied: each letter was substituted with the letter three ahead in the alphabet. Second,
a transposition was applied: the message was padded to have length divisible by five, and
each block of five letters was rotated two positions forward.
a. (20pt) What is the deciphering method?
b. (10pt) What is the first word of the message?
2a. (15 pt) Find the smallest positive integer A which solves 5A + 2
3 (mod 17).
2b. (15 pt) Explain why there is no integer B which solves the
congrunce 7B
1 (mod 21).
3. Consider the sequence Sn defined for all natural numbers as follows:
S1 = 1, S2 = 1, and Sn =
2Sn-1 + Sn-2 for n > 2.
a. (10pt) Compute S3, S4, S5, S6.
b. Show consecutive numbers in this sequence are relatively prime.
(Hint: use an induction argument.)
BONUS. Explain why Sn is never a multiple of 5.