1. Using induction, prove the formula:
2. As you know, the Fibonacci numbers 
are defined by 
, 
and, for n>2, 
. Give a rigorous proof of the assertion: ``
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 `` 
''.
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 
.
c) Find a solution to the equation 
.
(This is a typo. The question should have been (mod 25), not (mod 38))
d) Find a positive solution to the congruences 
, 
.