Last updated at October 28, 2026 by Teachoo
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