Applying euclid's algorithm for gcd

Euclid's algorithm for the greatest common divisor is often among the first algorithms seen that has a significantly faster run time than the naive algorithm (exponentially faster, in fact). A traditional assignment is to ask you to work through the application of Euclid's algorithm on a pair of integers that are modestly large.

Example

Consider the integers 12345 and 67890. We let a=67890, b=12345, and apply the Euclidian algorithm in the following steps.

• a = 5*b + 6165, so set a=12345 and b=6165
• a = 2*b + 15, so set a=6165 and b=15
• a = 441*b + 0, so gcd(a, b) = b

We conclude that gcd(67890, 12345) = 15. Note that we could perform the divisions required by hand or used a calculator (or other means), but we have showed how we work through the algorithm until we have the gcd at the end (when we get a 0 remainder).

Assignment

You will be assigned values of a and b and asked to work out the gcd in the same way as above.

Pass rating check You should follow the same steps as above, and include a similar amount of text as above so that you have clearly stated what you are doing, and someone can verify that you have applied Euclid's gcd algorithm correctly. You need to both hand in your work, and also check in with the help lab to demonstrate the algorithm. You can use your work that you hand in, and should talk the GA through the algorithm. The GA will make note if you are not able to do this, or if it seems you do not fully understand the process.