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
The Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) of several numbers
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:
Then GCD can be found as the product of all available prime factors taken with the minimum power
And LCM - as the product of all available prime factors, taken with the maximum power.
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.
Comentários