Programming Assignment I - Due: Tuesday June 20, 2000

The Greatest Common Divisor

Part I

In the first part of this programming assignment you will accept two integers as input, a and b. You will rearrange them so that b is larger than a. You will then implement the Euclidean Algorithm to find the greater common divisor of a and b.

Recall that d is a divisor of n if when we divide n by d, the remainder is 0. The greatest common divisor of a and b is the largest integer d which is a divisor of a and b

For example, the greatest common divisor of 100 and 15 is 5.

In order to find the greatest common divisor, we may use the Euclidean Algorithm.

If a is a divisor of b, then there is no need to do any work because a is the greatest common divisor of a and b.

So assume that a is not a divisor of b.

Divide b by a to get the quotient, q1, and remainder, r1.

Now divide a by r1 to get the quotient, q2, and remainder, r2.

Continue this process until you get a remainder of 0. The last non-zero remainder is the greatest common divisor of a and b.

Part II

It is a fact in mathematics that the greatest common divisor of two numbers can be written as a linear combination of the numbers. For example, 5 = 7*15-100.

Let us see how the Euclidean Algorithm works.

100 = 6*15 + 10

15 = 1*10 + 5

10 = 2*5 + 0

So the greatest common divisor of 100 and 15 is 5. Now we wish to write 5 as a linear combination of 100 and 15. We do that by filling in the following tableau. Across the top we write down all of the quotients found except the last. Then to fill in the spots in the tableau, on each line multiply the entry in the top by the entry directly to the left of the blank and add that product to the entry to its left. For example, to fill in the spot under the 6 on the first line, multiply 6 by 1 and add that result to 0. Once we do this for each empty spot in the tableau, the rightmost column will contain the integers that will give us the linear combination.

The larger of the integers will necessarily be associated with the smaller of a and b. However you will need to perform a test to see which of these numbers should be negative.

For example, 7*15 is larger and 1*100, so the coefficient of 100 must be changed to -1.

Submitting the Assignment

You will submit this assignment in two stages. The first stage will be the algorithmic stage. Before you can be successful at writing this program you must first have a plan. So the algorithm for your solution must be turned in by Friday. This will count 10% of the grade for this assignment. The program itself must be submitted at the beginning of class next Tuesday.

You can turn your algorithm in in class on Friday, but when you submit your assignment, make a print out of it and place it in a folder along with a 3.5-inch floppy with a copy of your source code and take it to FCW 20 and put in the basket for Jian Huang.