1 MATHEMATICS 271 L01/02 WINTER 2016 ASSIGNMENT 2 Due at 3:00 PM on Friday, February 26, 2016. Put your assignments into the appropriate wooden box (corresponding to your lecture section and last name) outside MS 569. Assignments must be understandable to the marker ( i.e., logically correct as well as legible ), and must be done by the student in his / her own words. Answer all questions, but only one question per assignment will be marked for credit. Please make sure that: (i) the cover page has only your student ID number and your instructor's name, (ii) your name and ID number are on the top right corners of all the remaining pages, and (iii) your assignment is STAPLED. Marked assignments will be handed back during your scheduled lab. 1. For each of the following statements, determine whether the statement is true or false and then prove your answer. (a) For all integers a; b and c, if a j bc then a j b or a j c. (b) For all integers a; b and c, if a j bc and gcd (a; b) = 1 then a j c. (c) For all integers a; b and c, if a j c and b j c then ab j c. (d) For all integers a; b and c, if a j c and b j c, and gcd (a; b) = 1 then ab j c. 2. The Fibonacci sequence f1 ; f2 ; f3 ; ::: is de ned recursively as follows: f1 = f2 = 1, and for n 3, fn = fn 1 + fn 2 . n 1 7 for all integers n 2. (a) Prove that fn < 4 (b) Prove that fn = 1 p 5 p n 1+ 5 2 1 p 2 5 n for all integers n 1. 3. Let N be your University of Calgary ID number. (a) Use the Euclidean Algorithm to nd gcd (N; 271) and use this to nd integers x and y so that gcd(N; 271) = N x + 271y. (b) De ne the sequence a1 ; a2 ; a3 ; ::: recursively as follows: a1 = 271, a2 = 2016, and for n 3, an = an 1 + an 2 . Prove that gcd(an ; an 1 ) = gcd(a2 ; a1 ) for every integer n 2. (c) Compute gcd(an ; an 1 )