NEWAll India NCERT Mock Test Series is now live!Take Free Test
| Exercise 11.2

Q2: Describe an algorithm to compute the least common multiple (lcm⁡\operatorname{lcm}) of two numbers.

UNDERSTAND THE QUESTION

*The problem asks for a clear step‑by‑step procedure (algorithm) that will give the least common multiple, lcm⁡\operatorname{lcm}, of any two positive integers.
*In Class 9 NCERT the concept is introduced via prime‑factorisation and the Euclidean algorithm for the greatest common divisor (gcd⁡\gcd). Both lead to the identity lcm⁡(a,b)×gcd⁡(a,b)=a×b\operatorname{lcm}(a,b)\times\gcd(a,b)=a\times b.

Step 1 — INPUT THE TWO NUMBERS

Let the given positive integers be aa and bb.

Step 2 — FIND THE PRIME FACTORISATION OF EACH NUMBER

Write aa and bb as products of prime powers:
a=p1α1 p2α2…pkαkb=p1β1 p2β2…pkβk\begin{aligned} a&=p_{1}^{\alpha_{1}}\,p_{2}^{\alpha_{2}}\dots p_{k}^{\alpha_{k}} \\[0.6em] b&=p_{1}^{\beta_{1}}\,p_{2}^{\beta_{2}}\dots p_{k}^{\beta_{k}} \end{aligned}
If a prime does not appear in the factorisation of a number, its exponent is taken as 00.

Step 3 — SELECT THE HIGHEST EXPONENT FOR EACH PRIME

For each prime pip_{i} choose the larger of αi\alpha_{i} and βi\beta_{i}:
γi=max⁡(αi,βi)\gamma_{i}=\max(\alpha_{i},\beta_{i})

Step 4 — FORM THE PRODUCT OF THE SELECTED PRIME POWERS

Multiply all primes raised to the selected exponents:
lcm⁡(a,b)=∏i=1kpiγi\operatorname{lcm}(a,b)=\prod_{i=1}^{k} p_{i}^{\gamma_{i}}
This product is the least common multiple of aa and bb.

Step 5 — (ALTERNATIVE USING \GCD) COMPUTE \GCD BY EUCLIDEAN ALGORITHM

If the Euclidean algorithm is preferred, first find gcd⁡(a,b)\gcd(a,b) using repeated division:
gcd⁡(a,b)=last non-zero remainder in the sequence a=r0,  b=r1,  ri=ri−2 mod ri−1.\gcd(a,b)=\text{last non-zero remainder in the sequence }a=r_{0},\;b=r_{1},\;r_{i}=r_{i-2}\bmod r_{i-1}.

Step 6 — USE THE RELATION BETWEEN \LCM AND \GCD

Finally compute
lcm⁡(a,b)=a×bgcd⁡(a,b).\operatorname{lcm}(a,b)=\dfrac{a\times b}{\gcd(a,b)}.
Both methods give the same result and are valid in Class 9 NCERT.

ANSWER

Algorithm (prime‑factor method):

  1. Write the prime factorisation of the two numbers.
  2. For each prime, take the larger exponent occurring in the two factorisations.
  3. Multiply the primes raised to these largest exponents; the product is the \operatorname{lcm}.

Alternative (using gcd⁡)\gcd):

  1. Find gcd⁡(a\gcd(a,b) by the Euclidean algorithm.
  2. Compute \operatorname{lcm}(a,b)=a×bgcd⁡(a,b)b)=\dfrac{a\times b}{\gcd(a,b)}.

COMMON MISTAKES

*Taking the lower exponent of a prime instead of the higher one, which gives a divisor rather than the \operatorname{lcm}.
*Confusing the product a×ba\times b with the \operatorname{lcm}; the \operatorname{lcm} is never larger than the product but usually smaller.
*When using the Euclidean algorithm, stopping before the remainder becomes zero leads to an incorrect gcd⁡\gcd and thus an incorrect \operatorname{lcm}.

Was this solution helpful?