The Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of several numbers

This calculator finds the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of two or more integers by performing prime factorization

PLANETCALC, The Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of several numbers

The Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of several numbers

The Greatest Common Divisor (GCD)
 
The Greatest Common Divisor (GCD) calculation formula
 
The Least Common Multiple (LCM)
 
The Least Common Multiple (LCM) calculation formula
 
The file is very large. Browser slowdown may occur during loading and creation.

GCD and LCM of several numbers

Recall that the GCD, or the greatest common divisor, is the largest natural number by which all given numbers are divisible without a remainder, and the LCM, or the least common multiple, is the smallest natural number that is divisible by each of the original numbers without a remainder. In the case of two numbers, the GCD can be found using Euclid's algorithm, and the LCM can be calculate by dividing the product of two numbers by the GCD.

In the case of several numbers, you can use the recursive formulas GCD (a, b, c) = GCD (GCD (a, b), c) and LCM (a, b, c) = LCM (LCM (a, b), c) , but there is also a more elegant way, which is used in the calculator above. To use it, you need to factor the given numbers into prime factors, i.e. perform their factorization.

Suppose we have a prime factorization of the numbers a and b:

 a = p^{\alpha_1} _1p^{\alpha_2} _2 ... p^{\alpha_n} _n \\b = p^{\beta_1} _1p^{\beta_2} _2 ... p^{\beta_m} _m

Then GCD can be found as the product of all available prime factors taken with the minimum power

 p^{min (\alpha_1, \beta_1)}_1p^{min (\alpha_2, \beta_2)}_2 ... p^{min (\alpha_n, \beta_n)}_np^{min (\alpha_m , \beta_m)}_m

And LCM - as the product of all available prime factors, taken with the maximum power.

 p^{max (\alpha_1, \beta_1)}_1p^{max (\alpha_2, \beta_2)}_2 ... p^{max (\alpha_n, \beta_n)}_np^{max (\alpha_m , \beta_m)}_m

In the absence of a particular factor in any of the numbers, it is considered to be taken with a power of zero.

The method works the same for more than two numbers. In addition to calculating the actual GCD and LCM of several numbers, the calculator above illustrates this method. The table in the calculator shows the decomposition of the given numbers into prime factors, and the calculation formulas show which factors were taken to find the GCD and LCM.

URL copied to clipboard
PLANETCALC, The Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of several numbers

Comments