Ex 11.2 - Describe an algorithm to compute least common multiple (lcm) - Exercise Set 11.2

part 2 - Ex 11.2, 2 - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Ex 11.2, 2 - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Ex 11.2, 2 - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 5 - Ex 11.2, 2 - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 6 - Ex 11.2, 2 - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 7 - Ex 11.2, 2 - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 8 - Ex 11.2, 2 - Exercise Set 11.2 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo · Class 9 Explore Class 9

Transcript

Ex 11.2, 2 Describe an algorithm to compute the least common multiple (1cm) of two numbers. There are two ways in which we can find least common multiple (1cm) of two numbers Direct Method - from definition Indirect Method – using formula LCM(m, n) × GCD (m, n) = m × n Let’s do both Direct Method The least common multiple, or LCM, is the smallest positive number which is multiple of both numbers LCM of 4 and 6 Multiples of 4=4, 8, 12, 16, 20, 24,… Multiples of 6=6, 12, 18, 24,…[ ; ] The smallest common multiple is 12 So, 𝐥𝐜𝐦(𝟒, 𝟔)=𝟏𝟐 Constructing the algorithm Since multiples can go on and on until infinity, we need to find a way to stop Let’s follow this Find multiples of the larger number in increasing order Check if each multiple is also a multiple of the smaller number Stop at the first number which satisfies this We can write the algorithm now Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) Let a be the larger of m, n, and b the smaller If m = n, LCM = m = n Set candidate to a If candidate is divisible by b, candidate is the LCM. Stop here. Otherwise, increase candidate by a Repeat Steps 3 and 4. Example: Find lcm(8,12) Step 1: Identify the greater and smaller numbers 𝑎=18, 𝑏=12 Step 2: Set the first candidate candidate =18 Step 3: Check whether 12 divides 18 (18)/(12)=1(6)/(12) The remainder is 6 , so 12 does not divide 18 Therefore, 18 is not a common multiple Step 4: Increase candidate by a (Move to the next multiple of 18) candidate = 18 + 18 = 18 × 2 = 36 Step 5: Check whether 12 divides 36 (36)/(12)=3 Since the remainder is 0, so 12 divides 36. So, we stop here Thus, 𝐥𝐜𝐦(𝟏𝟐, 𝟏𝟖)=𝟑𝟔 Let’s do the indirect Method now Indirect Method For two positive integers: 𝐥𝐜𝐦(𝒎,𝒏) × 𝐠𝐜𝐝(𝒎,𝒏)=𝒎 ×𝒏 Dividing both sides by gcd(𝑚,𝑛) : lcm(𝑚,𝑛)=(𝑚 × 𝑛)/(gcd(𝑚, 𝑛)) This gives us a different plan: Find the GCD using an algorithm we already know. Divide the product of the inputs by that GCD. Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) using the GCD Compute 𝐠𝐜𝐝(𝒎,𝒏) using a GCD algorithm. Store this value as 𝑔 Compute: 𝐿=((𝑚)/(𝑔)) × 𝑛 Report 𝐿 as lcm(𝑚,𝑛) Example: Find lcm(8,12) Step 1: Find gcd (8, 12) 𝑎=18, 𝑏=12 LCM of 4 and 6 Multiples of 4=4, 8, 12, 16, 20, 24,… Multiples of 6=6, 12, 18, 24,…[ ; ] The smallest common multiple is 12 So, 𝐥𝐜𝐦(𝟒, 𝟔)=𝟏𝟐 Constructing the algorithm Since multiples can go on and on until infinity, we need to find a way to stop Let’s follow this Find multiples of the larger number in increasing order Check if each multiple is also a multiple of the smaller number Stop at the first number which satisfies this We can write the algorithm now Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) Let a be the larger of m, n, and b the smaller If m = n, LCM = m = n Set candidate to a If candidate is divisible by b, candidate is the LCM. Stop here. Otherwise, increase candidate by a Repeat Steps 3 and 4. Example: Find lcm(8,12) Step 1: Identify the greater and smaller numbers 𝑎=18, 𝑏=12 Step 2: Set the first candidate candidate =18 Step 3: Check whether 12 divides 18 (18)/(12)=1(6)/(12) The remainder is 6 , so 12 does not divide 18 Therefore, 18 is not a common multiple Step 4: Increase candidate by a (Move to the next multiple of 18) candidate = 18 + 18 = 18 × 2 = 36 Step 5: Check whether 12 divides 36 (36)/(12)=3 Since the remainder is 0, so 12 divides 36. So, we stop here Thus, 𝐥𝐜𝐦(𝟏𝟐, 𝟏𝟖)=𝟑𝟔 Let’s do the indirect Method now Indirect Method For two positive integers: 𝐥𝐜𝐦(𝒎,𝒏) × 𝐠𝐜𝐝(𝒎,𝒏)=𝒎 ×𝒏 Dividing both sides by gcd(𝑚,𝑛) : lcm(𝑚,𝑛)=(𝑚 × 𝑛)/(gcd(𝑚, 𝑛)) This gives us a different plan: Find the GCD using an algorithm we already know. Divide the product of the inputs by that GCD. Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) using the GCD Compute 𝐠𝐜𝐝(𝒎,𝒏) using a GCD algorithm. Store this value as 𝑔 Compute: 𝐿=((𝑚)/(𝑔)) × 𝑛 Report 𝐿 as lcm(𝑚,𝑛) Example: Find lcm(8,12) Step 1: Find gcd (8, 12) 𝑎=18, 𝑏=12 Check if each multiple is also a multiple of the smaller number Stop at the first number which satisfies this We can write the algorithm now Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) Let a be the larger of m, n, and b the smaller If m = n, LCM = m = n Set candidate to a If candidate is divisible by b, candidate is the LCM. Stop here. Otherwise, increase candidate by a Repeat Steps 3 and 4. Example: Find lcm(8,12) Step 1: Identify the greater and smaller numbers 𝑎=18, 𝑏=12 Step 2: Set the first candidate candidate =18 Step 3: Check whether 12 divides 18 (18)/(12)=1(6)/(12) The remainder is 6 , so 12 does not divide 18 Therefore, 18 is not a common multiple Step 4: Increase candidate by a (Move to the next multiple of 18) candidate = 18 + 18 = 18 × 2 = 36 Step 5: Check whether 12 divides 36 (36)/(12)=3 Since the remainder is 0, so 12 divides 36. So, we stop here Thus, 𝐥𝐜𝐦(𝟏𝟐, 𝟏𝟖)=𝟑𝟔 Let’s do the indirect Method now Indirect Method For two positive integers: 𝐥𝐜𝐦(𝒎,𝒏) × 𝐠𝐜𝐝(𝒎,𝒏)=𝒎 ×𝒏 Dividing both sides by gcd(𝑚,𝑛) : lcm(𝑚,𝑛)=(𝑚 × 𝑛)/(gcd(𝑚, 𝑛)) This gives us a different plan: Find the GCD using an algorithm we already know. Divide the product of the inputs by that GCD. Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) using the GCD Compute 𝐠𝐜𝐝(𝒎,𝒏) using a GCD algorithm. Store this value as 𝑔 Compute: 𝐿=((𝑚)/(𝑔)) × 𝑛 Report 𝐿 as lcm(𝑚,𝑛) Example: Find lcm(8,12) Step 1: Find gcd (8, 12) 𝑎=18, 𝑏=12 Example: Find lcm(12,18) Step 1: Identify the greater and smaller numbers 𝑎=18, 𝑏=12 Step 2: Set the first candidate candidate =18 Step 3: Check whether 12 divides 18 (18)/(12)=1(6)/(12) The remainder is 6 , so 12 does not divide 18 Therefore, 18 is not a common multiple Step 4: Increase candidate by a (Move to the next multiple of 18) candidate = 18 + 18 = 18 × 2 = 36 Step 5: Check whether 12 divides 36 (36)/(12)=3 Since the remainder is 0, so 12 divides 36. So, we stop here Thus, 𝐥𝐜𝐦(𝟏𝟐, 𝟏𝟖)=𝟑𝟔 Let’s do the indirect Method now Indirect Method For two positive integers: 𝐥𝐜𝐦(𝒎,𝒏) × 𝐠𝐜𝐝(𝒎,𝒏)=𝒎 ×𝒏 Dividing both sides by gcd(𝑚,𝑛) : lcm(𝑚,𝑛)=(𝑚 × 𝑛)/(gcd(𝑚, 𝑛)) This gives us a different plan: Find the GCD using an algorithm we already know. Divide the product of the inputs by that GCD. Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) using the GCD Compute 𝐠𝐜𝐝(𝒎,𝒏) using a GCD algorithm. Store this value as 𝑔 Compute: 𝐿=((𝑚)/(𝑔)) × 𝑛 Report 𝐿 as lcm(𝑚,𝑛) Example: Find lcm(8,12) Step 1: Find gcd (8, 12) 𝑎=18, 𝑏=12 candidate = 18 + 18 = 18 × 2 = 36 Step 5: Check whether 12 divides 36 (36)/(12)=3 Since the remainder is 0, so 12 divides 36. So, we stop here Thus, 𝐥𝐜𝐦(𝟏𝟐, 𝟏𝟖)=𝟑𝟔 Let’s do the indirect Method now Indirect Method For two positive integers: 𝐥𝐜𝐦(𝒎,𝒏) × 𝐠𝐜𝐝(𝒎,𝒏)=𝒎 ×𝒏 Dividing both sides by gcd(𝑚,𝑛) : lcm(𝑚,𝑛)=(𝑚 × 𝑛)/(gcd(𝑚, 𝑛)) This gives us a different plan: Find the GCD using an algorithm we already know. Divide the product of the inputs by that GCD. Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) using the GCD Compute 𝐠𝐜𝐝(𝒎,𝒏) using a GCD algorithm. Store this value as 𝑔 Compute: 𝐿=((𝑚)/(𝑔)) × 𝑛 Report 𝐿 as lcm(𝑚,𝑛) Example: Find lcm(8,12) Step 1: Find gcd (8, 12) 𝑎=18, 𝑏=12 𝐥𝐜𝐦(𝒎,𝒏) × 𝐠𝐜𝐝(𝒎,𝒏)=𝒎 ×𝒏 Dividing both sides by gcd(𝑚,𝑛) : lcm(𝑚,𝑛)=(𝑚 × 𝑛)/(gcd(𝑚, 𝑛)) This gives us a different plan: Find the GCD using an algorithm we already know. Divide the product of the inputs by that GCD. Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) using the GCD Compute 𝐠𝐜𝐝(𝒎,𝒏) using a GCD algorithm. Store this value as 𝑔 Compute: 𝐿=(𝑚 × 𝑛)/(𝑔) Report 𝐿 as lcm(𝑚,𝑛) Example: Find lcm(12,18) Step 1: Find gcd (12, 18) Now, divisors(12) = [1, 2, 3, 4, 6, 12] divisors(18) = [1, 2, 3, 6, 9, 18] And, common-divisor-list = [1, 2, 3, 6] Since larges number is 6 here ∴ g = gcd (12, 18) = 6 Step 2: Use formula 𝐿=(𝑚 × 𝑛)/(𝑔) =(12 × 18)/(6) = 12 × 3 = 36 Therefore: 𝐥𝐜𝐦(𝟏𝟐,𝟏𝟖)=𝟑𝟔 Check LCM × GCD=36 × 6=216 𝑚 × 𝑛=12×18=216

CA Maninder Singh's photo - Co-founder, Teachoo

Made by

CA Maninder Singh

CA Maninder Singh is a Chartered Accountant qualified since 2010 and an educator teaching since 2006. At Teachoo, he draws on his accounting and tax experience to explain Accounts, Income Tax and GST through step-by-step lessons and practical examples.

For an uninterrupted learning experience, students can use Teachoo Black to remove ads and focus better.