One efficient way to compute the GCD of two numbers is to use Euclid's algorithm, which states the following:
GCD(A, B) = GCD(B, A % B)
GCD(A, 0) = Absolute value of A
In other words, if you repeatedly mod A by B and then swap
the two values, eventually B will store 0 and A will store the greatest
common divisor.