Divide, divide, and divide again to find the greatest common divisor
When you find the greatest common divisor (GCD) of two numbers, you do not need to list all their divisors one by one. Keep replacing the larger number with the remainder after dividing it by the smaller number, and you eventually reach the GCD. This method was described by Euclid more than 2,300 years ago.
Rule: For (a, b), if r is the remainder when a is divided by b, then gcd(a,b) = gcd(b,r). Repeat this until r becomes 0. The last nonzero number is the greatest common divisor.