MathAlgorithmaka greatest common divisor, Euclid, extended Euclidean algorithm, Bezout coefficients

GCD (Euclidean Algorithm)

Compute the greatest common divisor by repeatedly replacing (a, b) with (b, a mod b); the extended form also finds x, y with ax + by = gcd.

▶ VisualizePattern: Math & Number TheoryPractice (2)
Progress

Overview

The greatest common divisor gcd(a, b) is the largest integer dividing both. Euclid's algorithm computes it with the identity gcd(a, b) = gcd(b, a mod b) and base case gcd(a, 0) = a. For gcd(252, 105): 252 mod 105 = 42, 105 mod 42 = 21, 42 mod 21 = 0, so the answer is 21.

The extended Euclidean algorithm tracks how each remainder is a combination of the original inputs, yielding integers x, y with a·x + b·y = gcd(a, b) (Bezout's identity). This is how Modular Inverse is computed when the modulus is not prime, and how linear Diophantine equations ax + by = c are solved (solvable iff gcd | c).

The number of steps is O(log min(a, b)); the worst case is consecutive Fibonacci numbers. Every mainstream library ships it (math.gcd, std::gcd, BigInteger.gcd), but interviews expect you to write it and to know the extended version.

gcdEuclidnumber theoryO(log n)Bezout

Intuition

A mental model before the formal terms.

Tile a 252 × 105 rectangle with the largest square possible. Cut off as many 105 × 105 squares as fit (two), leaving a 105 × 42 strip. Repeat on the strip: two 42 × 42 squares leave 42 × 21; two 21 × 21 squares leave nothing. The last square that tiles exactly, 21, is the gcd. Each step shrinks the problem to the leftover strip, which is what a mod b computes.

How it works

  1. While b != 0: set (a, b) = (b, a mod b). When b reaches 0, a is the gcd.
  2. Extended: maintain two pairs (old_r, r) = (a, b), (old_s, s) = (1, 0), (old_t, t) = (0, 1) such that old_r = a·old_s + b·old_t and r = a·s + b·t at all times.
  3. Each step computes q = old_r div r and updates every pair as (old, cur) = (cur, old - q·cur). The invariant is preserved because it is linear.
  4. When r becomes 0, old_r is the gcd and (old_s, old_t) are the Bezout coefficients.
  5. Binary GCD (Stein) replaces divisions with shifts and subtractions: factor out common 2s, then repeatedly subtract the smaller odd number from the larger.

Why it works

Any common divisor d of a and b divides a - q·b = a mod b, and any common divisor of b and a mod b divides a = q·b + (a mod b). So the pair (a, b) and the pair (b, a mod b) have exactly the same common divisors, hence the same greatest one.

Termination and speed: after two steps the larger value at least halves (a mod b < a / 2 whenever b ≤ a), so the number of steps is at most 2·log2(a). Lamé's theorem sharpens this to about log_φ(min(a, b)) steps, attained by Fibonacci inputs.

Extended: the coefficients are correct because each remainder is computed as an integer combination of the previous two, and the initial values are trivially combinations of a and b.

Recognition

How to tell a problem wants this.

  • "Greatest common divisor", "can these be measured with a common unit", "reduce a fraction", "simplify a ratio".
  • Any LCM (Least Common Multiple) question, since lcm = a / gcd · b.
  • Modular inverses when the modulus is composite, or solving ax + by = c in integers.
  • Detecting whether a step size k visits every position in a cycle of length n (yes iff gcd(k, n) = 1).
“modulo 10^9 + 7” → Math & Number Theory

Interactive visualization

Play, step, change the input. ← → and space work too.

abq = a div br = a mod b
252105··
1/8gcd(252, 105): Euclid's insight is gcd(a, b) = gcd(b, a mod b), because any common divisor of a and b also divides a - q·b. We also track coefficients s, t with s·252 + t·105 = current a (extended Euclid).
Current division a = q·b + rValues that become the next (a, b)Finished rowsGCD
PseudocodeLearn GCD (Euclidean Algorithm) →
1(s0, s1), (t0, t1) = (1, 0), (0, 1)   # a = s0·A + t0·B, b = s1·A + t1·B
2while b != 0:
3  q = a div b; r = a mod b
4  a, b = b, r
5  s0, s1 = s1, s0 - q·s1;  t0, t1 = t1, t0 - q·t1
6return a  # gcd; and s0·A + t0·B == gcd
Variables
a252
b105
s1
t0
Complexity
best O(1)
avg O(log min(a, b))
worst O(log min(a, b))
space O(1)
Speed

Pseudocode

1gcd(a, b):
2  while b != 0:
3    a, b = b, a mod b
4  return a
5ext_gcd(a, b):
6  if b == 0: return (a, 1, 0)
7  g, x1, y1 = ext_gcd(b, a mod b)
8  return (g, y1, x1 - (a div b) * y1)

Implementations

1from typing import Tuple
2 
3 
41 · Iterative Euclidean algorithm
5def gcd(a: int, b: int) -> int:
6    """math.gcd does this in C; shown for the algorithm. Exact for any size."""
7    a, b = abs(a), abs(b)
8    while b:
9        a, b = b, a % b  # (a, b) -> (b, a mod b) shrinks b every step
10    return a  # gcd(a, 0) == a
11 
12 
132 · Extended Euclid: g = ax + by
14def ext_gcd(a: int, b: int) -> Tuple[int, int, int]:
15    """Return (g, x, y) with a*x + b*y == g == gcd(a, b)."""
16    if b == 0:
17        return a, 1, 0
18    g, x1, y1 = ext_gcd(b, a % b)
19    return g, y1, x1 - (a // b) * y1  # floor // matches Python's floor %
20 
21 
223 · Demo
23if __name__ == "__main__":
24    import math
25    assert gcd(48, 18) == 6 == math.gcd(48, 18)
26    assert gcd(-48, 18) == 6
27    assert gcd(0, 7) == 7
28    g, x, y = ext_gcd(240, 46)
29    assert g == 2 and 240 * x + 46 * y == g
Walkthrough
  1. The tuple assignment a, b = b, a % b performs the Euclid step atomically — no temporary needed.
  2. Python % returns a result with the divisor's sign (floor semantics); after abs normalization the loop only sees non-negatives anyway.
  3. ext_gcd uses floor division // with floor % — consistent, so the Bezout identity holds for negative inputs too.
  4. Arbitrary-precision ints mean no overflow anywhere; math.gcd is the C-speed stdlib version.
Complexity (this implementation)
time O(log min(a, b)) · space O(1) iterative, O(log) recursion for ext_gcd

Each op costs O(digits) on huge ints.

Language notes
  • math.gcd (any number of args since 3.9) always returns a non-negative int — prefer it in real code.
  • Python's floor % differs from C++/JS truncation: -7 % 3 is 2 in Python, -1 in C++/JS. Euclid works with either, as long as //// matches.
  • Recursion in ext_gcd is depth O(log), nowhere near the default 1000-frame limit.
Common mistakes in this language
  • Re-implementing gcd in a hot loop instead of calling math.gcd.
  • Porting C code with int(a / b) — true division then truncation disagrees with Python's floor % on negatives.
  • Assuming % behaves like C: sign conventions differ.
Language differences that matter here
  • Stdlib: C++17 std::gcd, Python math.gcd; JS/TS have none — always hand-rolled.
  • Division/remainder signs: C++ and JS truncate toward zero (-7 % 3 == -1); Python floors (-7 % 3 == 2). Extended Euclid must pair the matching quotient: a / b (C++), Math.trunc(a / b) (JS/TS), a // b (Python).
  • Range: C++ long long to 2^63; JS/TS number exact to 2^53, then BigInt (separate code path); Python unbounded.
  • Edge case: llabs(INT64_MIN) overflows in C++; Python and BigInt have no such value.

Complexity

Best
O(1)
Average
O(log min(a, b))
Worst
O(log min(a, b))
Space
O(1)

Worst case is consecutive Fibonacci numbers. Recursive form uses O(log) stack. Extended version has the same bound with constant extra work per step.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Reducing fractions, computing LCM (Least Common Multiple), checking coprimality.
  • Modular inverse modulo a composite m (extended Euclid) — see Modular Inverse.
  • Solving linear Diophantine equations and Chinese Remainder Theorem reconstruction.
  • GCD of an array or of a sliding range (combine with Sparse Table or Segment Tree since gcd is associative and idempotent).
Avoid it when
  • Never write trial division over 1..min(a, b) — that is O(min(a, b)) versus O(log).
  • Floating-point inputs: gcd is defined on integers; convert exact rationals first.
  • When only powers of two are involved, a & -a and shifts are cheaper — see Power-of-Two Tricks.

Alternatives

Prime FactorizationLCM (Least Common Multiple)

Common mistakes

  • Swapping arguments incorrectly in the recursive form (gcd(a % b, b) instead of gcd(b, a % b)) — still correct but doubles the steps.
  • Negative inputs: % in C++, Java, JavaScript and Go keeps the sign of the dividend, so take absolute values first or normalize the result.
  • Extended Euclid: returning (x1 - (a / b) * y1) with integer division that truncates toward zero on negatives — fine as long as remainders are computed with the same division; do not mix floor and truncation.
  • JavaScript: a % b on values above 2^53 loses precision; use BigInt.
  • Assuming gcd(0, 0) = 0 is an error; by convention it is 0, and gcd(x, 0) = |x|.

Interview patterns

  • GCD of strings: "ABCABC", "ABC" have a common divisor string iff s + t == t + s, of length gcd(len(s), len(t)).
  • Rotate an array in place by k using gcd(n, k) cycles.
  • Count pairs (i, j) with gcd(a[i], a[j]) = 1 via inclusion-exclusion over divisors — see Combinatorics.
  • Water jug problem: z is reachable iff z ≤ x + y and gcd(x, y) divides z.

Example problems

Pow(x, n)mediumCount Primesmedium