# Least common multiple

In arithmetic and number theory the **least common multiple** or **lowest common multiple** (**lcm**) or **smallest common multiple** of two integers *a* and *b* is the smallest positive integer that is a multiple of both *a* and *b*. If there is no such positive integer, e.g., if *a* = 0 or *b* = 0, then lcm(*a*, *b*) is defined to be zero.

The least common multiple is useful when adding or subtracting vulgar fractions, because it yields the lowest common denominator. Consider for instance

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42},}**

where the denominator 42 was used because lcm(21, 6) = 42.

If *a* and *b* are not both zero, the least common multiple can be computed by using the greatest common divisor (gcd) of *a* and *b*:

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{lcm}(a,b)=\frac{a\cdot b}{\operatorname{gcd}(a,b)}.}**

Thus, the Euclidean algorithm for the gcd also gives us a fast algorithm for the lcm. To return to the example above,

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{lcm}(21,6) ={21\cdot6\over\operatorname{gcd}(21,6)} ={21\cdot 6\over 3}={21\cdot 2}=42.}**

## Efficient calculation

The formula

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{lcm}(a,b)=\frac{(a\cdot b)}{\operatorname{gcd}(a,b)}}**

is adequate to calculate the lcm for small numbers using the formula as written.

Because that (*ab*)/c = *a*(*b*/*c*) = (*a*/*c*)*b*, one can calculate the lcm using the above formula more efficiently, by firstly exploiting the fact that *b*/*c* or *a*/*c* may be easier to calculate than the quotient of the product *ab* and *c*. This can be true whether the calculations are performed by a human, or a computer, which may have storage requirements on the variables *a*, *b*, *c*, where the limits may be 4 byte storage - calculating *ab* may cause an overflow, if storage space is not allocated properly.

Using this, we can then calculate the lcm by either using:

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{lcm}(a,b)=\left({a\over\operatorname{gcd}(a,b)}\right)\cdot b}**

or

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{lcm}(a,b)=a\cdot\left({b\over\operatorname{gcd}(a,b)}\right).\,}**

Done this way, the previous example becomes:

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{lcm}(21,6)={21\over\operatorname{gcd}(21,6)}\cdot6={21\over3}\cdot6=7\cdot6=42.}**

## Alternative method

The unique factorization theorem says that every positive integer number greater than 1 can be written in only one way as a product of prime numbers. The prime numbers can be considered as the atomic elements which, when combined together, make up a composite number.

For example:

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 90 = 2^1 \cdot 3^2 \cdot 5^1 = 2 \cdot 9 \cdot 5 \,\!}**

Here we have the composite number 90 made up of one atom of the prime number **2**, two atoms of the prime number **3** and one atom of the prime number **5**.

We can use this knowledge to easily find the lcm of a group of numbers.

For example: Find the value of lcm(45, 120, 75)

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 45\; \, = 2^0 \cdot 3^2 \cdot 5^1 \,\!}****Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 120 = 2^3 \cdot 3^1 \cdot 5^1 \,\!}****Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 75\; \,= 2^0 \cdot 3^1 \cdot 5^2. \,\!}**

The lcm is the number which has the greatest multiple of each different type of atom. Thus

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \operatorname{lcm}(45,120,75) = 2^3 \cdot 3^2 \cdot 5^2 = 8 \cdot 9 \cdot 25 = 1800. \,\!}**

## See also

## External links

- Online LCM calculator
- Online lcm calculator
- LCM Quiz
- LCM and GCF solvers, work shown These solvers use factorization algorithm described in wikipedia.

ca:Mínim comú múltiple de:Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches es:Mínimo común múltiplo eo:Plej malgranda komuna oblo fr:Plus petit commun multiple ko:최소공배수 it:Minimo comune multiplo nl:Kleinste gemene veelvoud ja:最小公倍数 pl:Najmniejsza wspólna wielokrotność fi:Pienin yhteinen jaettava zh:最小公倍數