Least common multiple
The least common multiple (LCM ) is a mathematical term. His counterpart is the greatest common divisor (gcd ). Both play a role among others in the fractions and number theory.
The least common multiple of two integers and is the smallest natural number which is a multiple of both as well as a multiple of.
The English name lcm ( least common multiple ) for the LCM is also used in mathematical texts.
Example of LCM calculation
- The multiples of 12, 12, 24, 36, 48, 60, 72, 84, 96, 108, ...
- The multiples of 18 are: 18, 36, 54, 72, 90, 108, ...
- The common multiple of 12 and 18 are thus 36, 72, 108, ...
- And the smallest of these is 36; sign in:
Calculation on the factorization
Gcd and lcm can be determined through the factorization of the two given numbers. example:
For the LCM, take the prime factors that occur in at least one of the two decompositions, and as associated exponent the larger of the output exponent:
The LCM of several numbers
One uses all prime factors that occur in any of the figures, with the highest occurring power, for example:
Ie:
You could also first calculate and then because as a binary operation on the natural numbers, the LCM is associative:
This justifies the notation
Applications
Fractions
Suppose we want to add the fractions and. These must be reduced to a common denominator by expanding. Of course one could simply multiply by what follows. The smallest possible common denominator ( the so-called denominator ) is but. The two breaks are expanded on these denominator and then added:
Applications in other algebraic structures
This can be defined not only for natural ( and whole ) numbers. It can form, for example, for polynomials. Instead of the prime factorization you take here, the decomposition into irreducible factors:
Then
The division with remainder, which also exists for polynomials, facilitates the identification of common divisors.
Analogous to the gcd is defined: a ring element is called the least common multiple of two ring elements and if a common multiple of and is and in turn every other common multiple of and is a multiple of.
Formally, one writes this definition for a ring like this:
This general definition can be extended to multiple numbers ( even infinitely many ).
Examples
Gaussian number ring
In the Gaussian number ring is the greatest common divisor of and just because and. Strictly speaking, a greatest common divisor, since all associated to this figure numbers are also greatest common divisor.
Not every ring there for two elements a gcd or a kgV. If they have a gcd, they can have multiple gcd. When the ring is an integral domain, then all gcd are associated with each other in character.
Is an integral domain and have the elements and a common multiple, then they also have a gcd, and it holds the equation
If it is only known that gcd exists of and then does not necessarily exist a common multiple.
Integrity ring
In the integrity of the ring elements have
No gcd: The elements and two maximum common divisor, since both have the same amount. However, these two elements are not associated to each other, so there are no gcd of and.
These elements and have but turn a gcd, namely. However, they have no common multiple because if a lcm would be, then it follows from the " gcd - lcm - equation " that needs to be associated. However, the common multiple is not a multiple of, so do not have a common multiple and the two elements no kgV.
An integral domain in which any two elements have a gcd, ie gcd gcd ring or area. In a GCD ring per two elements also have a kgV.
In a factorial ring each have two elements have a gcd
In a Euclidean domain can be the gcd of two elements with the Euclidean algorithm to determine.
Relationship between LCM and the greatest common divisor
It applies the following formula:
This makes it possible to calculate the LCM if the gcd is ( eg using the Euclidean algorithm) already determined. Conversely, one can calculate with this formula also the gcd of the LCM.