GCD

The greatest common divisor, or GCD, is the largest positive integer that divides two integers without a remainder.

It appears in many algorithm problems involving divisibility, ratios, periods, and number theory.

Core Idea

The Euclidean algorithm uses the fact that gcd(a, b) is the same as gcd(b, a % b) until the remainder becomes zero.

This gives a fast recursive or iterative algorithm.

Python Example

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return abs(a)

Python also provides math.gcd.

Common Confusions

GCD is about divisibility, not about the closest numeric value.

Be careful with zero. gcd(a, 0) is abs(a), but gcd(0, 0) is usually treated specially depending on context.

When To Use It

Use GCD for simplifying fractions, detecting shared periods, solving divisibility constraints, and reasoning about integer steps or grid movement.