This homework is due Thursday, October 2.

The Euclidean algorithm.

1. Use the Euclidean algorithm to compute the greatest common divisor d of 59400 and 16200 and find integers A and B such that

   	59400A + 16200B = d
   

   (This is B&W Section 2 problem 2.5 on page NT-25.)

2. Write a function (method, procedure) in any language you choose that accepts two integers as input and produces their gcd as output. Then write a program that calls that function and prints the output.

   A well written program will do the right thing when the input values are any integers - positive, negative or zero. The only case that might require special treatment is gcd(0,0). There is no right answer then. Just make sure your program doesn't crash.

   Note 1. The function that does the computation should not do any printing. That all happens in the calling program. If possible, the calling program should get the integer input values from the command line, or from stdin (System.in in Java). (Of course that's possible. But if your programming skills are so rusty that it's really difficult, don't spend time on it.)

   Note 2. Since CS110 is a prerequisite for this course, you should all be able to write this program. But for some of you your programming skills are so rusty that polishing them up so you can answer this question isn't worth the time. If that's the case, don't.

   Note 3. It's really easy to find solutions to this problem on the internet. I'd rather you wrote your own, but won't insist. If you do get one from the net you must acknowledge and understand the source and compile and run the program to test it.

3. Improve your solution to the previous problem so that your program both finds the gcd of its input values and also finds the coefficients for a linear integral combination of the inputs that produces the gcd.

   I'd still rather your function do no printing, but that's harder to arrange now that there are three integer outputs rather than just one. Do that if you can, but if you can't don't worry.

4. Given integers m > n the first step of the Euclidean algorithm look like this:

   	m = nq + r		0 <= r  < n
   

   1. Show that r is less than or equal to half of m.

   2. Suppose the Euclidean algorithm for computing gcd(m,n) takes k steps. Show that k won't be larger than log₂(n).

   3. Instrument the gcd program you wrote so that it reports how many steps (iterations or recursive calls) it takes. Run the program for some very large input values and show that the step counts are consistent with the logarithmic bound you proved above.

5. Recall that the Fibonacci numbers Fn are defined recursively as

   	F0 = F1 = 1,
   	Fn = Fn-1 + Fn-2 
   

   The sequence starts 1, 1, 2, 3, 5, 8, 13, 21, ...
   1. Compute the greatest common divisor of F8 and F9 and express it as an integer combination of those two numbers.

   2. Make the same computation for some other consecutive pair of Fibonacci numbers.

   3. Guess the general pattern suggested by these two examples.

   4. Prove that your guess is correct (if you can).

   5. How many iterations will the Euclidean algorithm need to compute the gcd of F_n+1 and F_m? Use the closed form expression for the Fibonacci numbers to confirm the logarithmic time bound on this computation.

6. The Euclidean algorithm works because you can do "long division with remainder" in the integers. That is, given m and n you can always find q and r with m = nq + r with r strictly smaller than n.

   You can also do "long division with remainder" for polynomials with rational coefficients. That is, given polynomials m(x) and n(x) you can find polynomials q(x) and r(x) where r(x) is "strictly smaller than" n(x). Here "strictly smaller than" means "has lower degree than".

   Therefore you can carry out the Euclidean algorithm for polynomials. Do that, to find the polynomial that's the greatest common divisor d(x) of

   	m(x) = x4 + 5x3 + 6x2 -4x - 8
   

   and

   	n(x) = x3 - 3x2 + 4
   

   and, at the same time, find polynomials A(x) and B(x) such that

   	A(x)m(x) + B(x)n(x) = d(x).
   

   If you're really ambitious you can write your gcd program so that it works for any objects that implement the you-can-do-long-division interface. I don't expect that ...