GCD & LCM Calculator

GCD, also called Greatest Common Factor (GCF), is the largest positive integer that divides both numbers without a remainder. For example, GCD of 12 and 18 is 6 because 6 is the largest number that divides both evenly.

LCM is the smallest positive integer that is divisible by both numbers. For example, LCM of 4 and 6 is 12 because 12 is the smallest number divisible by both 4 and 6.

For any two positive integers a and b: GCD(a,b) × LCM(a,b) = a × b. This relationship allows you to calculate LCM if you know the GCD, or vice versa.

GCD is essential for simplifying fractions (divide numerator and denominator by their GCD), solving Diophantine equations, and various applications in cryptography and computer science.

To simplify a fraction, divide both the numerator and denominator by their GCD. For example, to simplify 24/36: find GCD(24,36) = 12, then divide both by 12 to get 2/3. This gives you the fraction in its lowest terms.

LCM is used when synchronizing repeating events. Examples include finding when two buses arrive at the same time, determining common denominators for adding fractions, scheduling recurring tasks, or planning when gears with different tooth counts align.

Break each number into prime factors, then multiply the common factors with the lowest powers. For example, 48 = 2^4 × 3 and 18 = 2 × 3^2. Common factors are 2^1 and 3^1, so GCD = 2 × 3 = 6.

Break each number into prime factors, then multiply all factors using the highest powers. For 12 = 2^2 × 3 and 18 = 2 × 3^2, take 2^2 and 3^2, so LCM = 4 × 9 = 36.

The Euclidean algorithm efficiently finds GCD by repeatedly dividing and taking remainders. For GCD(48,18): 48÷18=2 remainder 12, 18÷12=1 remainder 6, 12÷6=2 remainder 0. When remainder is 0, the last divisor (6) is the GCD.

Coprime numbers (also called relatively prime) have no common factors except 1. For coprime numbers, GCD = 1 and LCM = their product. For example, 8 and 15 are coprime: GCD(8,15) = 1 and LCM(8,15) = 120.