GCD & Modular Arithmetic

Euclidean GCD & LCM

gcd(a, b) = gcd(b, a % b), recursing until b hits zero. Three lines, O(log min(a,b)) because the remainder at least halves every two steps. LCM comes from it as a / gcd(a,b) * b, dividing first so the product never overflows.

O(log min(a,b))

O(1)

say this out loud

gcd(a, b) equals gcd(b, a mod b) until the second is zero. For the LCM I divide before multiplying, because a times b overflows first.

How It Works

The Euclidean algorithm rests on one identity: gcd(a, b) equals gcd(b, a mod b). Any common divisor of a and b also divides a mod b, so the pair can be replaced by a smaller pair with the same answer. Repeat until the second value is zero, and the first is the gcd.

It is fast for a reason worth being able to state: after two steps the remainder is at most half of what it was, so the number of iterations is O(log min(a, b)). For values near a billion that is about 45 steps. LCM follows from gcd as a / gcd(a,b) * b, and the ordering there is deliberate: dividing before multiplying keeps the intermediate value small, whereas a * b / gcd overflows a 64-bit long for inputs that the correct form handles comfortably.

Step-by-Step Visualization

Find the greatest common divisor of 48 and 18

a48

b18

1/7

Code

Java

static long gcd(long a, long b) {
  while (b != 0) {
    long t = a % b;
    a = b;
    b = t;
  }
  return a;
}

static long lcm(long a, long b) {
  return a / gcd(a, b) * b;   // divide first, then multiply
}

Tips & Gotchas

1gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a is the base case

2For LCM divide before multiplying: a / gcd * b avoids overflowing on a * b

3The remainder at least halves every two steps, which is where the log comes from

Practice Problems

1Greatest Common Divisor of Strings
2Fraction Addition and Subtraction
3Simplified Fractions
4Number of Different Subsequences GCDs

About the GCD & Modular Arithmetic Pattern

Modular arithmetic is what lets you answer questions about enormous numbers without ever holding one. Addition and multiplication pass through the modulus cleanly, division does not, and the Euclidean algorithm underpins the whole area.

Key insight

Almost every math problem is asking you to avoid the obvious loop. Trial division to n becomes a sieve, repeated multiplication becomes binary exponentiation, and division under a modulus becomes multiplication by an inverse. If your solution loops to n or to the exponent, there is nearly always a log or sqrt version.

Common Math & Number Theory Interview Problems

Count Primes
Pow(x, n)
Greatest Common Divisor of Strings
Excel Sheet Column Title
Ugly Number II
Factorial Trailing Zeroes

Frequently Asked Questions

Why does gcd(a, 0) return a?

Every integer divides zero, so the divisors shared by a and 0 are exactly the divisors of a, and the greatest of those is a. It is the base case that terminates the recursion, and it also makes gcd over an array work naturally when you seed the accumulator with 0.

How does GCD of Strings work?

If two strings have a repeating common block, then s1 + s2 must equal s2 + s1. Check that first, and if it holds the answer is the prefix of length gcd(s1.length, s2.length). The numeric gcd gives the block size directly, which is why a string problem is solved by an integer algorithm.

Why divide before multiplying for LCM?

a * b overflows long for values around 10^10, but a / gcd(a,b) is exact because gcd divides a, and the result times b stays much smaller. Same answer, no overflow, and it costs nothing to write it in the safe order.