M328K First Midterm Solutions, February
21, 2003

1. Using induction, prove the formula:

We prove this by induction. The formula is true for the base case *n*=1,
since
Now for the inductive step. We assume the formula is true for *n*=*m*-1
and show it works for *n*=*m*. If it is true for *n*=*m*-1,
then

But then

which is the formula we needed to show.

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.]

I claim that

If we can prove this, then the original assertion follows, since being divisible by 4 is the same as being congruent to 0 or 4 modulo 8.

We prove the claim by (generalized) induction. It is true for the base
cases *n*=1 and *n*=2, since
. Now, for *m*;*SPMgt*;2, suppose that it is true for all values
of *n* up to *m*-1. We must show it is true for *n*=*m*.
There are 8 cases to check:

If , then and , so and , so .

If , then and , so and , so .

Similarly, if , then and , so .

If , then and , so .

If , then and , so .

If , then and , so .

If , then and , so .

If , then and , so , and then we're done.

3. Greatest common factors:

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

By the Euclidean algorithm: 66 = 1(52) + 14; 52 = 3(14) + 10; 14 = 1(10)+4; 10 = 2(4) + 2; 4 = 2(2). So (66,52)=2.

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 `` ''.

Working through the algorithm, we have 14 = 66 - 52; 10 = 52 - 3(14) = 4(52) - 3(66); 4 = 14 - 10 = 4(66) - 5(52); and finally our answer: 2 = 10 - 2(4) = 14(52) - 11(66).

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.

By inspection, or by the Euclidean algorithm, you can see that -3(25) + 2(38) = -75 + 76 = 1. Thus ALL integer solutions are of the form

where *n* is an arbitrary integer.

b) Find a solution to the equation .

This is the same question, and the answer is *x*=-3 (or *x*=35,
or any number that is congruent to -3 modulo 38).

c) Find a solution to the equation .

There was a typo in the question. It* *should have read "mod
25", not "mod 28".* *As written, there is no answer, since the
left hand side is always congruent to 0 (mod 38). As intended, the answer
is *x*=2 (or anything congruent to 2 modulo 25).

d) Find a positive solution to the congruences , .

Since
and
, and since
and
, *x*=5(76)+8(-75) = -220 is congruent to 5 modulo 25 and 8 modulo
38. However, we wanted a POSITIVE solution, so we add an arbitrary multiple
of (25)(38)=950. The smallest solution is -220+950 = 730.

Lorenzo Sadun