Euclid’s Subtraction Algorithm - Explanation with Examples - Class 9 - Euclid’s and Δ€ryabhaαΉ­a’s Algorithms

part 2 - Euclid’s Subtraction Algorithm - Euclid’s and Δ€ryabhaαΉ­a’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Euclid’s Subtraction Algorithm - Euclid’s and Δ€ryabhaαΉ­a’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Euclid’s Subtraction Algorithm - Euclid’s and Δ€ryabhaαΉ­a’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 5 - Euclid’s Subtraction Algorithm - Euclid’s and Δ€ryabhaαΉ­a’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo Β· Class 9 Explore Class 9

Transcript

Euclid’s Subtraction Algorithm The central observation is 𝐠𝐜𝐝(π’Ž,𝒏)=𝐠𝐜𝐝(𝒏,π’Žβˆ’π’) when π’Žβ‰₯𝒏. Algorithm to find 𝐠𝐜𝐝(π’Ž,𝒏) If π‘š<𝑛, interchange the numbers so that π‘šβ‰₯𝑛 If 𝒏=𝟎, report π‘š and stop Otherwise, replace the pair (π‘š,𝑛) by (𝒏,π’Žβˆ’π’) Repeat from Step 1. The replacement uses the old values of π‘š and 𝑛. Let’s do an example Example – Find 𝐠𝐜𝐝(πŸ‘πŸ•πŸ“,πŸ–πŸπŸ“) Since larger should be first, we interchange the numbers gcd(375,825) = gcd(825,375) We make a table, and put the larger number first again whenever needed. Reduction | Current pair | Subtraction | Next pair, larger first 1 | (825, 375) | 825-375=450 | (450, 375) 2 | (450, 375) | 450-375=75 | (375, 75) 3 | (375, 75) | 375-75=300 | (300, 75) 4 | (300, 75) | 300-75=225 | (225, 75) 5 | (225, 75) | 225-75=150 | (150, 75) 6 | (150, 75) | 150-75=75 | (75, 75) 7 | (75, 75) | 75-75=0 | (75, 0) Thus, gcd (375, 825) = 75 Why stop when one number is zero? For positive π‘š gcd(π‘š,0)=π‘š Any non-zero number can be divided by 0 Because (0)/(100)=0, (0)/(βˆ’2)=0 Thus, every positive divisor of π‘š also divides 0 The greatest such divisor is π‘š. Why subtraction can still be slow Consider 𝐠𝐜𝐝(πŸ—πŸ—, 𝟐) Subtracting 2 repeatedly produces: 99, 97, 95, 93,…,5, 3, 1 It takes 49 subtractions to reduce 99 to 1: 99βˆ’49 Γ— 2=1 The remaining pair is (2,1), followed by: (2, 1)β†’(1, 1)β†’(1, 0) Thus, this subtract-until-zero version uses 51 subtraction reductions Thus, For an odd input 2π‘˜+1, with π‘˜β‰₯1, subtracting 2 repeatedly takes π‘˜ reductions to reach 1 , followed by the two final reductions. So, the number of steps can still grow with the input's value. The key question becomes: Can we replace many repeated subtractions by one division? We answer that with our next algorithm

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.