# Applying euclid's algorithm for gcd

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.