M328K First Midterm Exam, February 21, 2003

1. Using induction, prove the formula:


2. As you know, the Fibonacci numbers tex2html_wrap_inline22 are defined by tex2html_wrap_inline24 , tex2html_wrap_inline26 and, for n>2, tex2html_wrap_inline30 . Give a rigorous proof of the assertion: `` tex2html_wrap_inline22 is divisible by 3 if and only if n is divisible by 4.'' [Hint: Before writing down your proof, you may want to first determine which Fibonacci numbers are congruent to 1 (mod 3), which are congruent to 2 (mod 3), and which are divisible by 3. I'm sure you'll see the patters quickly enough.]

3. Greatest common factors:

a) Find the greatest common factor of 66 and 52.

b) Write this number explicitly as a linear combination of 66 and 52. For instance, if (66,52) were equal to 24 (which it obviously isn't!), you might write `` tex2html_wrap_inline36 ''.

c) What is the least common multiple of 66 and 52?

4. Congruences, Diophantine equations and the Chinese Remainder Theorem.

a) Find all integer solutions to the equation 25 x + 38 y = 1.

b) Find a solution to the equation tex2html_wrap_inline40 .

c) Find a solution to the equation tex2html_wrap_inline42 .
(This is a typo. The question should have been (mod 25), not (mod 38))

d) Find a positive solution to the congruences tex2html_wrap_inline44 , tex2html_wrap_inline46 .

Lorenzo Sadun
Mon Feb 24 08:43:53 CST 2003