GCD and LCM Calculator: Prime Factors and Euclid
By Hesaplayıcı
The GCD and LCM calculator finds the greatest common divisor (GCD) and the least common multiple (LCM) of 2 to 10 whole numbers. Enter the numbers. The calculator writes each as a product of primes, builds the GCD and LCM from them, and checks the GCD with Euclid's algorithm. For example, GCD(24, 30) = 6 and LCM(24, 30) = 120.
Worked example: GCD and LCM of 24 and 30
GCD (greatest common divisor)
6
- LCM (least common multiple)
- 120
- Count of numbers
- 2
Step by step
n₁ = product of its prime factors
24 = 2³ × 3 = 24
n₂ = product of its prime factors
30 = 2 × 3 × 5 = 30
GCD (greatest common divisor)
GCD = product of the common prime factors, each with its lowest power
GCD = 2 × 3 = 6
LCM (least common multiple)
LCM = product of all prime factors, each with its highest power
LCM = 2³ × 3 × 5 = 120
GCD(x, y) = GCD(y, x mod y)
GCD(24, 30): 30 = 1 × 24 + 6; 24 = 4 × 6 + 0 = 6
How to use
- In Numbers, type 2 to 10 whole numbers. Separate them with spaces, commas or new lines: 24, 30. Do not use thousands separators.
- You can also paste a column from a spreadsheet; each line becomes one number.
- Press Calculate. You get the GCD, the LCM and the steps.
Formula
n = p₁^e₁ × p₂^e₂ × …, the prime factors of each numberGCD = product of the common prime factors, each with its lowest powerLCM = product of all prime factors, each with its highest powerGCD(x, y) = GCD(y, x mod y), Euclid’s algorithmn₁ × n₂ = GCD(n₁, n₂) × LCM(n₁, n₂), for two numbers
n₁, n₂ are the numbers you enter, p₁, p₂ the prime factors of a number and e₁, e₂ their powers. A common prime factor is one that every number has. x mod y is the remainder of x divided by y. In Euclid’s algorithm you divide the larger number by the smaller, then the divisor by the remainder; when the remainder is 0, the last divisor is the GCD. For three or more numbers, the calculator takes the GCD of the first two with the next number in the same way.
Worked example
The worked example on this page finds the GCD and the LCM of 24 and 30. The steps give the prime factors of both numbers first, then the GCD and the LCM, and last the division lines of Euclid’s algorithm. Both ways give the same GCD.
Limits
The calculator takes whole numbers from 1 to 10¹²; zero, negative numbers, decimals and fractions are not accepted. You can enter 2 to 10 numbers. Results are exact and never rounded. When the LCM passes 9,007,199,254,740,991 (2⁵³ − 1), the calculator shows an error instead of a rounded number: enter smaller or fewer numbers. It does not add or subtract fractions.
Frequently Asked Questions
How do you find the GCD?
Write each number as a product of primes. Multiply the primes that every number has, each with its lowest power. Since 24 = 2³ × 3 and 30 = 2 × 3 × 5, GCD(24, 30) = 2 × 3 = 6.
How do you find the LCM?
Take every prime that appears in at least one number, once, with its highest power, and multiply them. LCM(24, 30) = 2³ × 3 × 5 = 120.
What are the GCD and LCM of coprime numbers?
The GCD of two coprime numbers is 1 and their LCM is their product. 25 and 18 are coprime: the GCD is 1 and the LCM is 450.
What if one number divides the other?
Then the GCD is the smaller number and the LCM is the larger one. For example, GCD(4, 12) = 4 and LCM(4, 12) = 12.
Is the GCD the same as the GCF or HCF?
Yes. Greatest common divisor, greatest common factor and highest common factor are three names for the same number.
Calculation rules
- The GCD is the product of the prime factors that every number has, each with its lowest power; the LCM is the product of every prime factor of any number, each with its highest power. The calculator also finds the GCD with Euclid’s algorithm: both ways give the same result.
- Numbers must be whole numbers from 1 to 10¹². Results are exact and never rounded. When the LCM passes 9,007,199,254,740,991 (2⁵³ − 1), the calculator gives an error instead of a rounded number.
- For two numbers, GCD × LCM equals the product of the numbers. A GCD of 1 means the numbers are coprime.