GCD & LCM Calculator

Reference

What are GCD and LCM?

The Greatest Common Divisor (GCD), also called the Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is a multiple of two or more numbers. These are fundamental concepts in number theory used in simplifying fractions, finding common denominators, and solving problems in algebra and cryptography.

The Euclidean Algorithm

The Euclidean algorithm is one of the oldest algorithms in mathematics, dating back to 300 BC. It computes the GCD of two numbers by repeatedly dividing the larger by the smaller and taking the remainder: GCD(a, b) = GCD(b, a mod b), stopping when the remainder is 0. The last non-zero remainder is the GCD. For example: GCD(48, 18) → 48 = 2×18 + 12 → GCD(18, 12) → 18 = 1×12 + 6 → GCD(12, 6) → 12 = 2×6 + 0 → GCD = 6. The LCM is then calculated using: LCM(a, b) = |a × b| / GCD(a, b). For multiple numbers, both GCD and LCM are computed pairwise.

Common use cases

Simplifying fractions — divide both numerator and denominator by their GCD. Example: 48/18 → divide by GCD(48,18)=6 → 8/3. Finding common denominators — the LCM of the denominators gives the least common denominator for adding fractions. Scheduling problems — the LCM tells you when periodic events coincide. If one event repeats every 12 days and another every 18, they coincide every LCM(12,18)=36 days. Cryptography — GCD computations are essential in RSA key generation. Music theory — polyrhythms cycle every LCM of the beat counts.

Privacy

All calculations run 100% in your browser. No data is sent to any server.