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.
