GCD & LCM Calculator (with prime factorizations)
Enter a list of integers. The calculator returns the GCD (Euclidean algorithm), LCM, and full prime factorization of each input. Handles arbitrary-size integers via BigInt.
Prime factorizations
- 12 = 22 ร 3
- 18 = 2 ร 32
- 24 = 23 ร 3
How it works
GCD: the largest shared factor
The GCD of two integers is the largest integer that divides both without remainder. GCD(12, 18) = 6 because 6 divides both and no larger number does. GCD(7, 13) = 1 because they share no factors (such pairs are 'coprime').
We use the Euclidean algorithm: gcd(a, b) = gcd(b, a mod b), recursively. It's been known for ~2300 years and remains the fastest standard method. For three or more numbers, gcd(a, b, c) = gcd(gcd(a, b), c).
LCM: the smallest shared multiple
The LCM is the smallest positive integer that's a multiple of both. LCM(4, 6) = 12 because 12 is the first number that 4 and 6 both divide.
Formula: lcm(a, b) = (a ร b) / gcd(a, b). For 4 and 6: 24 / 2 = 12. For three numbers: lcm(a, b, c) = lcm(lcm(a, b), c).
If any number is 0, LCM is 0 (every number divides 0, but the 'smallest positive' is undefined). The calculator returns 0 for that case.
Why this matters
Fractions: to add 1/4 + 1/6, find LCM(4, 6) = 12 as the common denominator. 1/4 = 3/12, 1/6 = 2/12, sum = 5/12.
Scheduling: if event A repeats every 4 days and event B every 6 days, they coincide every LCM(4, 6) = 12 days.
Cryptography: GCD-based algorithms (extended Euclidean) underpin RSA key generation and modular inverse calculations.
Music theory: rhythms with periods 3 and 4 sync up after 12 beats (LCM).
Frequently asked questions
โบWhat if my numbers are coprime?
GCD = 1 and LCM = product of all numbers. Coprime means no shared prime factors.
โบCan I include negative numbers?
Yes. We treat absolute values for GCD/LCM calculations. -12 and 18 give GCD 6 and LCM 36, same as 12 and 18.
โบWhat if I enter 0?
GCD(0, n) = |n| (since every integer divides 0, and n is the largest such for that pair). LCM with 0 is 0 by convention. With all zeros, GCD/LCM are undefined.
โบHow big can my numbers be?
We use BigInt internally, so arithmetic on integers of any size is exact. Practical limit is your typing speed and screen space.
โบWhy is the prime factorization useful?
GCD = product of common primes (taking the smaller exponent). LCM = product of all primes appearing in any number (taking the larger exponent). The factorizations make these relationships visible.
โบWhat's the relationship between GCD and LCM?
For two numbers: a ร b = gcd(a, b) ร lcm(a, b). So if you know any three of {a, b, gcd, lcm}, you can compute the fourth. Doesn't generalize cleanly to three or more numbers.
โบCan I use this for polynomial GCD?
Not in this tool โ we handle integers only. For polynomials, you'd use a CAS like SymPy or Maxima.
โบDoes the data leave my browser?
No. Calculation runs locally; nothing is sent to a server.
Related tools
Last updated: