GCD, LCM and prime factorisation
Enter two or more whole numbers separated by spaces. For a single number you get its factorisation, divisors and whether it is prime.
Result
- Coprime?
- no
Euclid’s algorithm for 84 and 126:
126 = 1 · 84 + 42
84 = 2 · 42 + 0
| Number | Factors | Prime? | Divisors |
|---|---|---|---|
| 84 | 2² · 3 · 7 | no | 12 |
| 126 | 2 · 3² · 7 | no | 12 |
| 210 | 2 · 3 · 5 · 7 | no | 16 |
GCD and LCM
The greatest common divisor (GCD) is the largest number that divides all the given numbers. The least common multiple (LCM) is the smallest number that each of them divides. For two numbers, GCD · LCM = a · b.
The GCD comes from Euclid’s algorithm: divide the larger number by the smaller with a remainder, and repeat with the divisor and the remainder until the remainder is zero. The last non-zero divisor is the GCD.
Prime factorisation
Every whole number above 1 can be written in exactly one way as a product of primes: 360 = 2³ · 3² · 5. The factorisation also gives the number of divisors: (3+1)·(2+1)·(1+1) = 24.
Common questions
What is the LCM useful for?
For example finding a common denominator for fractions, or when two repeating events will coincide again.
How big can the numbers be?
GCD and LCM work up to 40 digits. Factorisation and divisors work up to 10¹⁵.