GCD Calculator

What is GCD?

We call the Greatest Common Divisor (GCD) the largest number that divides two or more integers exactly. To find it, use the Euclidean algorithm: divide the larger by the smaller, then redo the operation with the divisor and the remainder until that remainder reaches zero.

Here is an example. GCD(12, 8) → 12 = 1×8 + 4 → 8 = 2×4 + 0 → GCD = 4.

Greatest common divisor and the Euclidean algorithm

The greatest common divisor gcd(a, b) is the largest positive integer that divides both a and b with zero remainder. The Euclidean algorithm computes it efficiently using the identity gcd(a, b) = gcd(b, a mod b), repeated until b = 0 — at which point the answer is a. Example: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6. The procedure dates back to Euclid's Elements (Book VII, c. 300 BC) and runs in O(log min(a, b)) — dramatically faster than trial-factoring both numbers, which is O(sqrt n).

A useful identity links GCD and LCM: a · b = gcd(a, b) · lcm(a, b). Two integers are coprime when their GCD equals 1.

Where the GCD shows up

• Reducing fractions to lowest terms: 18/48 = 3/8 after dividing both by gcd = 6.
• RSA cryptography uses the extended Euclidean algorithm to compute modular inverses of the public exponent.
• Partitioning quantities into equal groups (e.g., the largest tile size that paves a rectangular floor without cuts).
• Diophantine equations ax + by = c have integer solutions iff gcd(a, b) | c.

FAQ

Why prefer Euclid over factoring both numbers? Euclid runs in O(log min(a, b)); trial-division factoring is O(sqrt n). For 20-digit numbers Euclid finishes in microseconds while factoring may take seconds or minutes.

What is gcd(0, n)? By convention gcd(0, n) = n for any positive n, since every integer divides 0.

How does GCD scale to more than two numbers? Apply pairwise: gcd(a, b, c) = gcd(gcd(a, b), c). The operation is associative.

Can the GCD be negative? No — by definition the GCD is the largest positive divisor. Negative signs in inputs are dropped.