Solution Review: Greatest Common Divisor

Solution

There are many ways to find the GCD of two integers. We’ll use Euclid’s algorithm to calculate the GCD:

• If n = 0 then GCD(n, m) = m. This is a termination condition.

• If m = 0 then GCD(n, m) = n. This is a termination condition.

• Write n in the form of a quotient remainder $(n = mq + r)$. q is the quotient, and r is the remainder.

• Since GCD(N,M) = GCD(M,R), use the Euclidean Algorithm to find GCD(M,R).

Coding exercise