Math 58 - Number Theory

September 5, 2006 (rev. 9/6)

Homework 1 (due September 7):

1. Evaluate:

2. Use the Euclidean Algorithm formally to compute gcd (1776, 2006). How many

divisions are required?

3. It takes 2 divisions to compute gcd (2, 3 ) using Euclid:

3 – 1 * 2 = 1

2 – 2 * 1 = 0

It takes 3 divisions to compute gcd ( 3, 5).

What are the smallest positive numbers a and b such that computing gcd (a, b)

(using the Euclidean Algorithm) requires 4 divisions?

What about 5 divisions?

4. If d is your answer to the gcd you computed in question 2, then find integers x and y (which may be positive or negative) such that

d = 1776 x + 2006 y.

5. Simplify (no proof required):

f₁ + f₃ + f₅ + f₇ + … + f₉₉ = ?

where the f_n’s are Fibonacci numbers. (Recall f₁ = 1, f₂ = 1, f₃=2, etc.)

(Hint: Since f₂ = f₁, you might as well write

f₂ + f₃ + f₅ + f₇ + … + f₉₉. )

(end)