Lowest common multiple (LCM) of two numbers
Categories: number theory
The lowest common multiple (LCM) of two integers a and b is the smallest positive integer that is divisible by both a and b.
It is usually written as lcm(a, b).
We can find the LCM of two numbers by looking at the multiples of each number, and comparing them to find the smallest number that appears in both lists. For example, to find the LCM of 12 and 18:
- Multiples of 12 are 12, 24, 36, 48, 60, 72...
- Multiples of 18 are 18, 36, 54, 72, 90, 108...
Comparing the lists, the lowest common multiple is 36 (ie 12 multiplied by 3, or 18 multiplied by 2).
LCM and prime factors
The LCM can be found from the prime factors of the two numbers. For example:
$$ \begin{align} 18 = 2 \times 3 \times 3 \newline 12 = 2 \times 2 \times 3 \end{align} $$
For each prime factor we take the highest multiplicity for either number:
- For 2, the highest multiplicity is 2 that occurs in the number 12.
- For 3, the highest multiplicity is 3 that occurs in the number 18.
The LCM of 12 and 18 is therefore:
$$ 2^2 \times 3^2 = 4 \times 9 = 36 $$
LCM and GCD
The greatest common divisor (GCD) of two integers a and b is the largest positive integer that divides into both a and b.
The LCM can also be found using this formula:
$$ lcm(a, b) = \frac{a.b}{gcd(a, b)} $$
For 12 and 18, the GCD is 6 (6 is the largest number that divides into both 12 and 18), so:
$$ lcm(12, 18) = \frac{12 \times 18}{6} = 36 $$
The linked article gives a method for calculating the GCD, known as Euclid's Algorithm.
See also
Join the GraphicMaths Newletter
Sign up using this form to receive an email when new content is added:
Popular tags
adder adjacency matrix alu and gate angle area argand diagram binary maths cartesian equation chain rule chord circle cofactor combinations complex polygon complex power complex root cosh cosine cosine rule cpu cube decagon demorgans law derivative determinant diagonal directrix dodecagon ellipse equilateral triangle eulers formula exponent exponential exterior angle first principles flip-flop focus gabriels horn gradient graph hendecagon heptagon hexagon horizontal hyperbola hyperbolic function infinity integration by substitution interior angle inverse hyperbolic function inverse matrix irregular polygon isosceles trapezium isosceles triangle kite koch curve l system locus maclaurin series major axis matrix matrix algebra minor axis nand gate newton raphson method nonagon nor gate normal not gate octagon or gate parabola parallelogram parametric equation pentagon perimeter permutations polar coordinates polynomial power probability probability distribution product rule pythagoras proof quadrilateral radians radius rectangle regular polygon rhombus root set set-reset flip-flop sine sine rule sinh sloping lines solving equations solving triangles square standard curves star polygon straight line graphs surface of revolution symmetry tangent tanh transformations trapezium triangle turtle graphics vertical volume of revolution xnor gate xor gate