1) The last words of Caesar -- using Scytale.

2.1)

n= 257. phi(n) = 256 since n is prime.
n= 32768 = 2^15. phi(n) = 2^14 = 16384.

2.2)

phi(n) = phi(p) phi(q) phi(r) = (p-1)(q-1)(r-1) since the phi function is multiplicative.

2.3)

n = 5, 8, 10, 12.

2.4)  CORRECTION: The problem should state "... all numbers n such that ..."

n = 1 and n = 2.

3.1)

The intermediate numbers in Euclid are: 291, 252, 39, 18, 3, 0. gcd = 3.

The intermediate numbers in Euclid are: 16534528044, 8332745927, 8201782117, 130963810, 82025897, 48937913, 33087984,
15849929, 1388126, 580543, 227040, 126463, 100577, 25886, 22919, 2967, 2150, 817, 516, 301, 215, 86, 43, 0
gcd = 43.


3.2)

gcd(12,18) = 6 and 6 does not divide 56, so no solutions.

gcd(16,25) =1 so this does have a solution. x = 33, y = -21 for example, but also infinitely many others
of the form (33+25k, -21-16k) for any k \in \mathbb{Z}.  


3.3)

if d | x+y and d | x-y, then d divides both 2x and 2y 
Since x and y have no common divisors, d | 2.
Thus d = 1 or d = 2.


3.4)

Ext Euclid tells us that a = 11, b = -30 is a solution to 202a + 74b = 2, and thus,
a =11* 3819 = 42009 and b = -30* 3819 = -114570 are solutions to 202a + 74b = 7638   
Thus, the set of solutions is all pairs (42009 - 37k, -114570 + 101k). 
Positivity of both coordinates gives us the conditions k <= 1135 and k >= 1135. Thus, there is a
positive solution

(42009 - 37*1135, -114570 + 101*1135) =
(14, 65)

Indeed 202*14 + 74*65 = 7638.



3.5)

We need to solve 87a + 123 b = 8733. 

Euclid says that (17, -12) is a solution to 87a + 123 b = 3
and thus, (17*8733/3 = 49487, -12*8733/3 = -34932) is a solution to 87a + 123 b = 8733.  
Thus, (49487-41k, -34932+29k) is the set of all solutions 
For positivity, k <= 1207 and k >= 1205. Thus, the three
positive solutions are:

(82, 13)
(41, 42)
(0, 71)

Since most condos rent at $87, the number of them is 82 and
the number of them that rent at $123 is 13.


3.6)

Prove by induction.
Base case: Euclid returns 1 on input (F_0, F_1) = (0, 1).
Ind. Hypothesis: Assume that for some i >= 0, on input (F_i, F_i+1), Euclid returns 1.
We will prove that for i+1. On input (F_i+1, F_i+2), one step of Euclid
takes us to (F_i+2 - F_i+1, F_i+1) = (F_i, F_i+1) which on further execution gives us 1
by the inductive hypothesis.