GCD & LCM Calculator - Greatest Common Divisor and Least Common Multiple

How the GCD & LCM Calculator Works

Enter two or more numbers separated by commas. The calculator finds both the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) using the Euclidean algorithm. It shows the step-by-step solution and prime factorization of each number.

GCD vs LCM - Definitions and Comparison

GCD and LCM are inverse concepts. One finds the largest shared factor, the other finds the smallest shared multiple:

Concept	Full Name	Definition	Example (12, 18)
GCD	Greatest Common Divisor	Largest number that divides all inputs evenly	6 (12=6x2, 18=6x3)
LCM	Least Common Multiple	Smallest number divisible by all inputs	36 (36/12=3, 36/18=2)

Key relationship: GCD(a,b) x LCM(a,b) = a x b. For 12 and 18: 6 x 36 = 216 = 12 x 18. This formula lets you find one from the other.

The Euclidean Algorithm - Step by Step

The fastest method to find GCD, used since 300 BC. Repeatedly divide and take the remainder until it reaches zero:

Step	Division	Remainder
1	48 = 2 x 18 + 12	12
2	18 = 1 x 12 + 6	6
3	12 = 2 x 6 + 0	0 (stop)

The last non-zero remainder is the GCD: GCD(48, 18) = 6. Then LCM = (48 x 18) / 6 = 144.

Practical Examples

Example 1: GCD(24, 36) = 12, LCM(24, 36) = 72. Simplify 24/36 = 2/3.

Example 2: GCD(15, 25) = 5, LCM(15, 25) = 75. Common denominator for 1/15 + 1/25 = 75.

Example 3: GCD(7, 13) = 1 (coprime - no common factors), LCM(7, 13) = 91.

Example 4: GCD(48, 60, 72) = 12, LCM(48, 60, 72) = 720. Three numbers at once.

Example 5: GCD(100, 75) = 25, LCM(100, 75) = 300. 100/75 simplifies to 4/3.

Example 6: GCD(144, 60) = 12, LCM(144, 60) = 720. Useful for scheduling cycles.

Example 7: GCD(17, 31) = 1. Both are prime, so always coprime. LCM = 17 x 31 = 527.

Real-World Applications

Application	Uses GCD or LCM?	Example
Simplifying fractions	GCD	36/48 = (36/12)/(48/12) = 3/4
Adding fractions	LCM	1/6 + 1/8 = LCD is LCM(6,8)=24
Scheduling problems	LCM	Bus A every 12 min, B every 18 min - both arrive together every LCM(12,18)=36 min
Tiling floors	GCD	Room 12x18 ft - largest square tile is GCD(12,18)=6 ft
Cryptography (RSA)	GCD	Key generation requires GCD(e, phi) = 1 (coprime check)
Gear ratios	GCD	Gears with 48 and 36 teeth - ratio simplifies by GCD(48,36)=12 to 4:3

FAQ

When do I need GCD in real life?

Simplifying fractions (divide numerator and denominator by their GCD), dividing items into equal groups without leftovers, tiling problems (largest tile that fits evenly), and cryptography (RSA key generation requires coprime check via GCD).

When do I need LCM?

Adding or subtracting fractions with different denominators (finding the least common denominator), scheduling problems (when do two periodic events coincide?), and determining the period of combined signals or cycles.

What does coprime mean?

Two numbers are coprime (also called relatively prime) when their GCD equals 1. They share no common factors other than 1. Examples: 7 and 13, 8 and 15, 9 and 16. Any two consecutive integers are always coprime.

How does the Euclidean algorithm work?

Repeatedly divide the larger number by the smaller and take the remainder. Continue until the remainder is zero. The last non-zero remainder is the GCD. For GCD(48,18): 48 = 2x18 + 12, then 18 = 1x12 + 6, then 12 = 2x6 + 0. The GCD is 6. This algorithm is over 2300 years old and still the fastest known method.

Can I find GCD and LCM of more than 2 numbers?

Yes. Calculate GCD for the first two numbers, then use that result with the third number, and so on. GCD(a,b,c) = GCD(GCD(a,b), c). Same approach for LCM. Enter all numbers separated by commas and the calculator handles the chain automatically.

What is the relationship between GCD and LCM?

GCD(a,b) x LCM(a,b) = a x b. This means if you know one, you can calculate the other: LCM = (a x b) / GCD. For example: GCD(12,18) = 6, so LCM = (12 x 18) / 6 = 36. This identity holds for any pair of positive integers.

Is GCD the same as HCF?

Yes. GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are the same thing, just different names used in different countries. GCD is more common in American math education, HCF in British. Both refer to the largest number that divides all given numbers evenly.

What is prime factorization and how does it relate to GCD?

Prime factorization breaks a number into prime factors: 12 = 2x2x3, 18 = 2x3x3. The GCD takes the minimum power of each shared prime: GCD = 2^1 x 3^1 = 6. The LCM takes the maximum power: LCM = 2^2 x 3^2 = 36. The Euclidean algorithm is faster for computation, but prime factorization gives more insight into why.

Related Tools

Logarithm Calculator

Calculate logarithms with any base - log10, ln, log2 and custom - Open calculator

Area Calculator

Calculate the area of squares, rectangles, triangles, circles and more - Open calculator

Fraction Calculator

Add, subtract, multiply and divide fractions with step-by-step solutions - Open calculator

Average Calculator

Calculate arithmetic, weighted and geometric average - Open calculator

Percentage Calculator

Find percentages, percentage change and ratios - Open calculator