Least common multiple

The least common multiple ( LCM ) is a mathematical term. Its counterpart is the greatest common factor (GCF). Both play a role in fractions and number theory , among other things .

The least common multiple of two whole numbers and is the smallest positive natural number that is both a multiple of and a multiple of . In addition, for the case or the LCM is defined as . ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m=0}$ ${\displaystyle n=0}$ ${\displaystyle \operatorname {kgV} (m,\,n):=0}$

The English term for the smallest common multiple is least common multiple , or lcm for short, and is also used in mathematical texts.

Calculation of the LCM of natural numbers

Example of LCM calculation

• The positive multiples of 12 are: 12, 24, 36, 48, 60, 72, 84, 96, 108, ...
• The positive multiples of 18 are: 18, 36, 54, 72, 90, 108, ...
• The common positive multiples of 12 and 18 are therefore 36, 72, 108, ...
• and the smallest of these is 36; in characters:

${\displaystyle \operatorname {kgV} (12,18)=36}$

Calculation using prime factorization

GCF and LCM can be determined by the prime factorization of the two given numbers. Example:

${\displaystyle 3528=2^{\color {Red}3}\cdot 3^{\color {Red}2}\cdot 7^{\color {Red}2}}$

${\displaystyle 3780=2^{\color {OliveGreen}2}\cdot 3^{\color {OliveGreen}3}\cdot 5^{\color {OliveGreen}1}\cdot 7^{\color {OliveGreen}1}}$

For the LCM one takes the prime factors that occur in at least one of the two decompositions, and as the associated exponent, the larger of the initial exponents:

${\displaystyle \operatorname {kgV} (3528,3780)=2^{\color {Red}3}\cdot 3^{\color {OliveGreen}3}\cdot 5^{\color {OliveGreen}1}\cdot 7^{\color {Red}2}=52.920}$

Calculation using the greatest common divisor (GCD)

The following formula applies:

${\displaystyle \mathrm {ggT} (m,n)\cdot \mathrm {kgV} (m,n)=|m\cdot n|}$

If both numbers are positive or negative, the amount bars are omitted. This can be used to calculate this if the has already been determined (e.g. with the Euclidean algorithm ) (conversely, this formula can also be used to calculate the one from the ). ${\displaystyle \mathrm {kgV} }$ ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {kgV} }$

After determining one of the two numbers , it is usually easiest to divide by the and multiply by the other number. The amount of the result is what you are looking for . Example: ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {kgV} }$

The 24 and 18 is 6 (to calculate the means Euclidean algorithm see the article to GCD ). This is consequently (since both numbers are positive, the amount is omitted) ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {kgV} }$

${\displaystyle (18\div 6)\cdot 24=3\cdot 24=72}$.

The formula at the beginning of the section is easy to understand, by the way, because the product of the numbers can also be expressed as follows: ${\displaystyle \mathrm {ggT} }$

${\displaystyle m\cdot n=a\cdot \mathrm {ggT} (m,n)\cdot b\cdot \mathrm {ggT} (m,n)}$.

Now this can be determined with the using the factors and , since these are coprime and thus their product with which gives the smallest common multiple (the amount is necessary if one of the two numbers is negative): ${\displaystyle \mathrm {kgV} }$ ${\displaystyle \mathrm {ggT} }$ ${\textstyle a}$ ${\textstyle b}$ ${\displaystyle \mathrm {ggT} }$

${\displaystyle \mathrm {kgV} (m,n)=|a\cdot b\cdot \mathrm {ggT} (m,n)|}$

Multiplying both sides by the and using the relationship of the previous equation results in the first equation of the section. ${\displaystyle \mathrm {ggT} }$

${\displaystyle \mathrm {ggT} (m,n)\cdot \mathrm {kgV} (m,n)=\mathrm {ggT} (m,n)\cdot |a\cdot b\cdot \mathrm {ggT} (m,n)|=|m\cdot n|}$

The LCM of several numbers

All prime factors that occur in at least one of the numbers are used with the highest power that occurs, for example:

${\displaystyle 144=2^{\color {Red}4}\cdot 3^{\color {Red}2}}$

${\displaystyle 160=2^{\color {OliveGreen}5}\cdot 5^{\color {OliveGreen}1}}$

${\displaystyle 175=5^{\color {Blue}2}\cdot 7^{\color {Blue}1},}$

so:

${\displaystyle \mathrm {kgV} (144,160,175)=2^{\color {OliveGreen}5}\cdot 3^{\color {Red}2}\cdot 5^{\color {Blue}2}\cdot 7^{\color {Blue}1}=50.400.}$

You could also calculate first and then as a two-digit combination on the whole numbers, this is associative : ${\displaystyle \mathrm {kgV} (144,160)=1440}$ ${\displaystyle \mathrm {kgV} (1440,175)=50.400,}$ ${\displaystyle \mathrm {kgV} }$

${\displaystyle \mathrm {kgV} (m,\,\mathrm {kgV} (n,p))=\mathrm {kgV} (\mathrm {kgV} (m,n),\,p).}$

This justifies the spelling ${\displaystyle \mathrm {kgV} (m,n,p)}$

Applications

Fractions

Suppose you want to add the fractions and . To do this, they must be brought to a common denominator by expanding . It could be with Multiply what gives. The lowest possible common denominator (the so-called main denominator ) is . The two fractions are expanded to this denominator and then added: ${\displaystyle {\tfrac {17}{21}}}$ ${\displaystyle {\tfrac {44}{35}}}$ ${\displaystyle 21}$ ${\displaystyle 35}$ ${\displaystyle 735}$ ${\displaystyle \operatorname {kgV} (21,35)=105}$

${\displaystyle {\frac {17}{21}}+{\frac {44}{35}}={\frac {{\color {Red}5}\cdot 17}{{\color {Red}5}\cdot 21}}+{\frac {{\color {Red}3}\cdot 44}{{\color {Red}3}\cdot 35}}={\frac {85}{105}}+{\frac {132}{105}}={\frac {217}{105}}}$

The LCM in rings

This is defined analogously to in rings : A ring element is called the smallest common multiple of two ring elements and if is a common multiple of and and in turn every other common multiple of and is a multiple of . ${\displaystyle \operatorname {ggT} }$ ${\displaystyle \mathrm {kgV} }$ ${\displaystyle v}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle v}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle v}$

Formally, this definition for a ring is written like this: ${\displaystyle R}$

${\displaystyle v=\mathrm {kgV} (a,b)\quad :\Longleftrightarrow \quad a\mid v,\;b\mid v,\;\forall e\in R:(a\mid e,\,b\mid e)\Rightarrow v\mid e}$

This more general definition can be extended to several numbers (even to an infinite number).

Examples

The LCM of polynomials

This cannot only be defined for natural (and whole) numbers. You can z. B. also form for polynomials . Instead of the prime factorization , one takes here the decomposition into irreducible factors: ${\displaystyle \mathrm {kgV} }$

${\displaystyle {\begin{aligned}f(x)&=x^{2}+2xy+y^{2}=(x+y)^{2}\\g(x)&=x^{2}-y^{2}=(x+y)(x-y)\end{aligned}}}$

Then

${\displaystyle \mathrm {kgV} (f,g)=(x+y)^{2}(x-y)}$.

The remainder division that exists also for polynomials, the identification of, common divisors.

Gaussian number ring

In the Gaussian number ring , the greatest common divisor of and is even , because and . Strictly speaking, is a greatest common factor, since all the numbers associated with this number are also greatest common factors. ${\displaystyle \mathbb {Z} +\mathrm {i} \mathbb {Z} }$ ${\displaystyle 2}$ ${\displaystyle 1+3\mathrm {i} }$ ${\displaystyle 1+\mathrm {i} }$ ${\displaystyle 2=-\mathrm {i} (1+\mathrm {i} )^{2}}$ ${\displaystyle 1+3\mathrm {i} =(1+\mathrm {i} )(2+\mathrm {i} )}$ ${\displaystyle 1+\mathrm {i} }$

Not in every ring one or one exists for two elements. If they have one, they can have several . If the ring is an integrity ring , then all are associated with one another , in signs . ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {kgV} }$ ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \sim }$

If an integrity ring is and the elements and have one , then they have one too , and the equation applies ${\displaystyle R}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \mathrm {kgV} }$ ${\displaystyle \mathrm {ggT} }$

${\displaystyle a\cdot b\sim \mathrm {ggT} (a,b)\cdot \mathrm {kgV} (a,b)}$

However, if only one of and exists, then there does not necessarily have to be one . ${\displaystyle \mathrm {ggT} }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \mathrm {kgV} }$

Integrity ring

In the integrity ring have the elements ${\displaystyle R=\mathbb {Z} [{\sqrt {-3}}]}$

${\displaystyle a:=4=2\cdot 2=(1+{\sqrt {-3}})(1-{\sqrt {-3}}),\quad b:=(1+{\sqrt {-3}})\cdot 2}$

none : The elements and are two maximum common factors , because both have the same amount . However, these two elements are not associated with each other, so there is no of and . ${\displaystyle \mathrm {ggT} }$ ${\displaystyle 1+{\sqrt {-3}}}$ ${\displaystyle 2}$ ${\displaystyle \mathrm {ggT} }$ ${\displaystyle a}$ ${\displaystyle b}$

However, the elements mentioned and have their own GCT, namely . However, they have not , because if one would, then from the "GCD LCM equation" that to associated needs to be. However, the common multiple is not a multiple of , so there is none and the two elements have none at all . ${\displaystyle 1+{\sqrt {-3}}}$ ${\displaystyle 2}$ ${\displaystyle 1}$ ${\displaystyle \mathrm {kgV} }$ ${\displaystyle v}$ ${\displaystyle \mathrm {kgV} }$ ${\displaystyle v}$ ${\displaystyle k:=(1+{\sqrt {-3}})\cdot 2}$ ${\displaystyle 4}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \mathrm {kgV} }$ ${\displaystyle \mathrm {kgV} }$

Remarks

An integrity ring in which two elements have one is called a GCT ring or GCT area . In a GCD ring, every two elements also have one . ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {kgV} }$

In a factorial ring , every two elements have one . ${\displaystyle \mathrm {ggT} }$

In a Euclidean ring , the two elements can be determined with the Euclidean algorithm. ${\displaystyle \mathrm {ggT} }$

Web links

Wikibooks: Algorithm Collection - Euclidean Algorithm and LCM  - Learning and Teaching Materials

• Online tool for calculating the GCD and LCM of two or three numbers
• Various online tools for prime factorization, GCF and LCM.
• Video: common and least common multiple (LCM) . Heidelberg University of Education (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19848 .