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.