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?
Rotate each block of five letters two positions backward,
and substitute each letter with the one three back in the alphabet.
Note that in this case, doing these steps in the opposite order also works.
Also, a rotation three positions forward is the same as a rotation two
positions backward.
b. (10pt) What is the first word of the message?
GIVE
Complete message: GIVEM YREGA RDSTO BROAD WAYXX
2a. (15 pt) Find the smallest positive integer A which solves 5A + 2
3 (mod 17).
The fancy way is to subtract 2 from both sides,
and see to invert 5 modulo 17.
The nonfancy way is just to write 5A+2 for values of A:
7, 12, 17, 22, 27, 32, 37, and check each modulo 17.
Voila: 7, 12, 0, 5, 10, 15, 3, so A = 7.
2b. (15 pt) Explain why there is no integer B which solves the
congrunce 7B
1 (mod 21).
The problem asks for the multiplicative inverse of 7 modulo 21.
7 and 21 have a common divisor of 7, and so are not relatively prime.
Therefore, there is no inverse of 7.
Equivalently, for any integer B, 7B is always a multiple of 7, so modulo 21, the result is one of 0, 7, or 14, and none of these is 1.
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.
S3 = 2x1 + 1 = 3
S4 = 2x3 + 1 = 7
S5 = 2x7 + 3 = 17
S6 = 2x17+ 7 = 41
b. Show consecutive numbers in this sequence are relatively prime.
(Hint: use an induction argument.)
Base case. Check that S1 and S2 are relatively prime.
GCD(S1, S2) = (1, 1) = 1.
Inductive Hypothesis. Suppose for natural number k, Sk and Sk+1 are relatively prime.
Inductive Step. We show, given the inductive hypothesis for k, that
Sk+1 and Sk+2 are relatively prime.
(The result is the inductive hypothesis for k+1.)
Let d be a natural number dividing both Sk+1 and Sk+2. We aim to show that d = 1.
The relation for the sequence gives Sk+2 = 2Sk+1 + Sk.
If d divides Sk+2 and Sk+1, then d also divides
Sk.
By the inductive hypothesis, the greatest common divisor of Sk and
Sk+1 is 1. Thus, d = 1.
Conclusion. By the principle of mathematical induction, the consecutive sequence elements, Sk and Sk+1 are relatively prime, for all natural numbers k.
BONUS. Explain why Sn is never a multiple of 5.
First solution. Write the sequence modulo 5. It repeats on a cycle of length 12. Once two consecutive elements are the same, the rest must follow on in the cycle.
Second solution. Write the sequence relation twice and collect terms:
Sn = 2 Sn-1 + Sn-2 =
2 (2Sn-2 + Sn-3) + Sn-2 =
5Sn-2 + 2Sn-3.
Thus, Sn
2Sn-3 (mod 5).
Therefore, Sn is a multiple of 5 if and only if
Sn-3 is a multiple of 5.
Observe that the sequence begins 1, 1, 3, and none of these
are multiples of 5.
(This is actually the base case of a very simple induction argument.)