Greatest Common Divisor
Last reviewed: January 2026
Find the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of any two or more integers. This calculator runs entirely in your browser — your data stays private, and no account is required.
GCD (Greatest Common Divisor): the largest number that divides both values evenly. GCD(48, 18) = 6, because 6 divides both and no larger number does. LCM (Least Common Multiple): the smallest number that both values divide into evenly. LCM(48, 18) = 144. Relationship: GCD × LCM = a × b. So GCD(48,18) × LCM(48,18) = 6 × 144 = 864 = 48 × 18. The Euclidean algorithm finds GCD efficiently: divide the larger by the smaller, take the remainder, repeat until remainder = 0.
GCD: simplifying fractions (divide both numerator and denominator by GCD). Distributing items equally into groups without remainder. Finding the largest tile that fits perfectly in a room without cutting. LCM: adding fractions (find the common denominator). Scheduling problems where events that repeat at different intervals align (two buses with different cycle times). Gear ratios: when two gears with different tooth counts complete a full cycle together. Music: LCM determines when two rhythmic patterns with different lengths next coincide.
| Numbers | GCD | LCM | Relationship |
|---|---|---|---|
| 12, 18 | 6 | 36 | 12 × 18 = 6 × 36 |
| 15, 25 | 5 | 75 | 15 × 25 = 5 × 75 |
| 8, 12 | 4 | 24 | 8 × 12 = 4 × 24 |
| 7, 13 | 1 | 91 | 7 × 13 = 1 × 91 (coprime) |
The Greatest Common Divisor (GCD) — also called Greatest Common Factor (GCF) or Highest Common Factor (HCF) — is the largest positive integer that divides two or more numbers without a remainder. The GCD of 24 and 36 is 12, because 12 is the largest number that divides both evenly (24 ÷ 12 = 2, 36 ÷ 12 = 3). The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of two or more numbers. The LCM of 4 and 6 is 12, because 12 is the smallest number that both 4 and 6 divide into evenly. GCD and LCM are inversely related through the formula: GCD(a,b) × LCM(a,b) = a × b. This means if you know any three of these four values, you can calculate the fourth. For 12 and 18: GCD = 6, and LCM = (12 × 18) ÷ 6 = 36.
| Method | Steps | Example: GCD(48, 36) | Best For |
|---|---|---|---|
| Prime Factorization | Factor both numbers, take common primes at lowest power | 48=2⁴×3, 36=2²×3² → GCD=2²×3=12 | Small numbers, educational |
| Euclidean Algorithm | Repeatedly divide and take remainder until 0 | 48÷36=1 R12, 36÷12=3 R0 → GCD=12 | Large numbers, programming |
| Listing Factors | List all factors of each, find largest common | 48: {1,2,3,4,6,8,12,16,24,48} ∩ 36: → 12 | Very small numbers |
The Euclidean algorithm, developed over 2,300 years ago by the Greek mathematician Euclid, is one of the oldest algorithms still in active use. It finds the GCD through repeated division: divide the larger number by the smaller, then replace the larger number with the smaller and the smaller with the remainder, and repeat until the remainder is zero — the last non-zero remainder is the GCD. For GCD(252, 198): 252 ÷ 198 = 1 remainder 54, then 198 ÷ 54 = 3 remainder 36, then 54 ÷ 36 = 1 remainder 18, then 36 ÷ 18 = 2 remainder 0. Therefore GCD(252, 198) = 18. This algorithm is remarkably efficient — it finds the GCD in at most log(min(a,b)) steps, making it practical for numbers with hundreds of digits. The extended Euclidean algorithm additionally finds integers x and y such that ax + by = GCD(a,b), which is fundamental to public-key cryptography (RSA encryption relies on this to compute modular multiplicative inverses).
GCD and LCM appear in numerous practical situations. Simplifying fractions uses GCD: to reduce 48/60, divide both by GCD(48,60) = 12, yielding 4/5. Adding fractions uses LCM to find the least common denominator: to add 5/12 + 7/18, find LCM(12,18) = 36. Scheduling problems use LCM: if two buses depart every 15 and 20 minutes respectively from the same stop, they will depart together every LCM(15,20) = 60 minutes. Tile and layout problems use GCD: to tile a 24×36 inch area with the largest possible square tiles without cutting, use GCD(24,36) = 12 inch tiles (requiring 2×3 = 6 tiles). Gear ratios in mechanical engineering use GCD to find the simplest gear ratio. Music theory uses LCM to determine when rhythmic patterns of different lengths realign — two patterns of 3 and 4 beats realign every LCM(3,4) = 12 beats. Packaging optimization, signal processing, computer science algorithms, and cryptographic protocols all rely on efficient GCD and LCM computation.
In computer science, GCD computation is a building block for numerous algorithms. The RSA cryptographic algorithm — which secures most internet communications including banking, email, and e-commerce — relies on computing GCD and modular inverses of very large prime numbers (typically 2,048 bits, or approximately 617 decimal digits). Hash table design uses GCD to minimize collision rates — choosing a prime number table size ensures that the GCD of the table size and common data patterns is 1, distributing entries evenly. In graphics programming, calculating the aspect ratio of an image uses GCD: a 1920×1080 image has GCD(1920,1080) = 120, giving an aspect ratio of 16:9. Memory allocation in operating systems uses LCM to align data structures efficiently. Network packet scheduling uses LCM to calculate the hyperperiod — the time after which all periodic tasks repeat their pattern — essential for real-time systems in aerospace and automotive applications.
Extending GCD and LCM to three or more numbers uses the associative property: GCD(a,b,c) = GCD(GCD(a,b),c) and LCM(a,b,c) = LCM(LCM(a,b),c). For example, to find GCD(24, 36, 60): first GCD(24,36) = 12, then GCD(12,60) = 12. For LCM(4, 6, 10): first LCM(4,6) = 12, then LCM(12,10) = 60. The prime factorization method scales naturally to multiple numbers — take the highest power of each prime for LCM and the lowest power for GCD. For 12 = 2²×3, 18 = 2×3², and 30 = 2×3×5: GCD = 2¹×3¹ = 6 (lowest powers of common primes), LCM = 2²×3²×5¹ = 180 (highest powers of all primes). For related math tools, see our Fraction Calculator and Prime Number Checker.
Bezout's Identity states that for any two integers a and b, there exist integers x and y such that ax + by = GCD(a,b). The extended Euclidean algorithm finds these coefficients efficiently. For GCD(240, 46) = 2, the algorithm finds x = -9 and y = 47, meaning 240(-9) + 46(47) = 2. This identity is the mathematical foundation of modular arithmetic in cryptography — RSA encryption uses it to compute the private key from the public key components. The algorithm is also essential in solving linear Diophantine equations (equations requiring integer solutions), computing modular inverses for hash functions, and implementing error-correcting codes in digital communications.
See also: Fraction Calculator · Ratio Calculator · Prime Number Checker
→ GCD simplifies fractions; LCM finds common denominators. To simplify 24/36: GCD(24,36) = 12, so 24/36 = 2/3. To add 1/4 + 1/6: LCM(4,6) = 12, so 3/12 + 2/12 = 5/12. These are the two most common practical applications.
→ The Euclidean algorithm finds GCD efficiently. GCD(48, 18): 48 = 2×18 + 12, then 18 = 1×12 + 6, then 12 = 2×6 + 0. GCD = 6. This 2,300-year-old algorithm works for any size numbers and is still used in modern cryptography.
→ LCM(a,b) = (a × b) / GCD(a,b). This relationship means you only need to find one to get the other. For three or more numbers, compute pairwise: LCM(a,b,c) = LCM(LCM(a,b), c).
→ GCD appears in everyday scheduling problems. "Two events repeat every 12 and 18 days — when do they coincide?" LCM(12,18) = 36 days. "I have 24 red and 36 blue tiles — what's the largest square pattern using equal groups?" GCD(24,36) = 12 tiles per group. See our Fraction Calculator and Prime Factorization.
See also: Fraction Calculator · Prime Factorization · Prime Checker · Scientific Calculator