The greatest common divisor of two numbers is the largest integer that divides both evenly. For 12 and 18, the divisors of 12 are 1, 2, 3, 4, 6, 12 and the divisors of 18 are 1, 2, 3, 6, 9, 18. The largest value in both lists is 6, so gcd(12, 18) = 6.

The zero cases follow from the definition. Every integer divides 0, since 0 divided by any nonzero k leaves no remainder. So the common divisors of a and 0 are the divisors of a, and the largest is a itself, giving gcd(a, 0) = a and gcd(0, b) = b. When both inputs are 0, every integer divides both, so there is no largest common divisor. By convention this is gcd(0, 0) = 0.

The naive approach tests every integer from 1 up to min(a, b) and keeps the largest that divides both. It works, but it scales with the size of the inputs. The approaches below build up to the Euclidean algorithm, which runs in a number of steps proportional to the logarithm of the smaller input.

Key Constraints:

Intuition

If a number d divides both a and b, it also divides their difference a - b. Suppose a = d * x and b = d * y. Then a - b = d * (x - y), still a multiple of d. The argument runs in reverse too, so the common divisors of a and b are the common divisors of a - b and b. The gcd therefore does not change when you replace the larger number with the difference: gcd(a, b) = gcd(a - b, b).

Repeatedly subtracting the smaller value from the larger keeps the gcd fixed while shrinking the numbers. When the two values become equal, that shared value is the gcd. For example, gcd(48, 36) becomes gcd(12, 36), then gcd(12, 24), then gcd(12, 12), so the answer is 12.

The zero inputs need attention before the loop, since the loop assumes both values are positive. If either value is 0, the answer is the other value, so those cases return directly.

Algorithm

Example Walkthrough

Input:

Neither value is 0, so the loop runs. The pair starts at (48, 36). Since 48 > 36, subtract to get (12, 36). Now 36 > 12, so subtract to get (12, 24). Again 24 > 12, so subtract to get (12, 12). The two values are equal, so the loop stops and the answer is 12. Each subtraction preserved the gcd while pulling the larger number down toward the smaller one.

This approach is correct but slow when the two values are far apart. Computing gcd(1000000, 2) would subtract 2 half a million times before finishing. The next approach replaces the chain of subtractions with a single remainder operation.

Code

Intuition

The subtraction approach wastes work when one number is much larger than the other. Subtracting b from a until a drops below b is integer division: the value left at the end is a mod b. So a whole run of subtractions collapses into one remainder operation.

That gives the Euclidean identity: gcd(a, b) = gcd(b, a mod b). The divisor argument from before still holds, since any common divisor of a and b also divides a mod b, and the reverse too. The remainder a mod b is always strictly less than b, so each step shrinks the pair fast. The process stops when the remainder reaches 0, and at that point the other value is the gcd, matching the rule gcd(x, 0) = x.

This is the recommended approach. It runs in O(log(min(a, b))) steps and needs no special handling for the zero inputs, since they fall out of the loop logic directly.

Algorithm

Example Walkthrough

Input:

The pair starts at (270, 192). The remainder 270 mod 192 is 78, so the pair becomes (192, 78). Next, 192 mod 78 is 36, giving (78, 36). Then 78 mod 36 is 6, giving (36, 6). Then 36 mod 6 is 0, giving (6, 0). Now b is 0, so the loop stops and a, which is 6, is the answer. The pair reached the result in four steps, far fewer than subtraction would take.

Code

Intuition

The modulo version has a recursive structure built into it. The identity gcd(a, b) = gcd(b, a mod b) is defined in terms of a smaller instance of the same problem, and gcd(a, 0) = a is the base case where the recursion stops. Writing it recursively puts the identity and its base case side by side, mirroring the math.

The recursion terminates because the second argument strictly decreases on every call. The remainder a mod b is always less than b, so the chain drives the second argument down to 0. At that point the base case returns the first argument, the gcd. The recursion depth matches the iteration count of the loop version, so it stays within O(log(min(a, b))) calls.

Algorithm

Example Walkthrough

Input:

The first call is gcd(12, 18). Since b is not 0, it returns gcd(18, 12 mod 18), and 12 mod 18 is 12, so the next call is gcd(18, 12). That returns gcd(12, 18 mod 12), and 18 mod 12 is 6, so the next call is gcd(12, 6). That returns gcd(6, 12 mod 6), and 12 mod 6 is 0, so the next call is gcd(6, 0). Here b is 0, so the base case returns 6, which unwinds back through the calls as the final answer.

Code