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.

Function Contract

gcd(a, b) expects integers.

It returns the non-negative greatest common divisor. gcd(a, 0) returns abs(a). The special case gcd(0, 0) may need separate interpretation depending on the problem.

Python Example

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

Python also provides math.gcd.

Step-by-Step Example

For gcd(48, 18):

48 % 18 = 12
18 % 12 = 6
12 % 6 = 0

The GCD is 6.

Why the Euclidean Algorithm Works

Any number that divides both a and b also divides a - b, and more generally a % b. Replacing (a, b) with (b, a % b) preserves the common divisors while making the numbers smaller.

The process stops when the remainder is zero.

Complexity

The Euclidean algorithm is very fast, usually described as O(log min(a, b)) arithmetic steps. The exact bit-level cost depends on integer size, but for algorithm practice it is treated as logarithmic.

Common Uses

GCD often appears when a problem can be reduced by a shared factor:

• Simplifying a fraction.
• Finding a common period between cycles.
• Checking whether a step size can reach a target difference.
• Normalizing a direction vector such as (dx, dy) by dividing both parts by their GCD.

The algorithmic role is usually to preserve exact divisibility information in a smaller form.

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.

Another common mistake is using a slow loop over all possible divisors when the Euclidean algorithm is available.

When To Use It

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

Do not use GCD when the problem is about nearest values, averages, or general numeric similarity rather than exact divisibility.

The Main Point

GCD preserves exact divisibility information while reducing a pair of integers to their shared factor structure.