Q2: Describe an algorithm to compute the least common multiple () of two numbers.
UNDERSTAND THE QUESTION
*The problem asks for a clear step‑by‑step procedure (algorithm) that will give the least common multiple, , 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 (). Both lead to the identity .
Step 1 — INPUT THE TWO NUMBERS
Let the given positive integers be and .
Step 2 — FIND THE PRIME FACTORISATION OF EACH NUMBER
Write and as products of prime powers:
If a prime does not appear in the factorisation of a number, its exponent is taken as .
Step 3 — SELECT THE HIGHEST EXPONENT FOR EACH PRIME
For each prime choose the larger of and :
Step 4 — FORM THE PRODUCT OF THE SELECTED PRIME POWERS
Multiply all primes raised to the selected exponents:
This product is the least common multiple of and .
Step 5 — (ALTERNATIVE USING \GCD) COMPUTE \GCD BY EUCLIDEAN ALGORITHM
If the Euclidean algorithm is preferred, first find using repeated division:
Step 6 — USE THE RELATION BETWEEN \LCM AND \GCD
Finally compute
Both methods give the same result and are valid in Class 9 NCERT.
ANSWER
Algorithm (prime‑factor method):
- Write the prime factorisation of the two numbers.
- For each prime, take the larger exponent occurring in the two factorisations.
- Multiply the primes raised to these largest exponents; the product is the \operatorname{lcm}.
Alternative (using :
- Find ,b) by the Euclidean algorithm.
- Compute \operatorname{lcm}(a,.
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 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 and thus an incorrect \operatorname{lcm}.