Āryabhaṭa’s Division Algorithm - All Steps & Solved Problems - Class 9 - Euclid’s and Āryabhaṭa’s Algorithms

part 2 - Āryabhaṭa’s Division Algorithm - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Āryabhaṭa’s Division Algorithm - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Āryabhaṭa’s Division Algorithm - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 5 - Āryabhaṭa’s Division Algorithm - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 6 - Āryabhaṭa’s Division Algorithm - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 7 - Āryabhaṭa’s Division Algorithm - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 8 - Āryabhaṭa’s Division Algorithm - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 9 - Āryabhaṭa’s Division Algorithm - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 10 - Āryabhaṭa’s Division 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

Āryabhaṭa’s Division Algorithm This is Improved version of Euclid’s algorithm. Instead of performing subtraction so many times, we perform division For example: So, dividing 99 by 2 leaves remainder 1 Thus, instead of subtracting 2 forty-nine times from 99, we directly find the remainder What does "mod" mean? 𝒎 𝐦𝐨𝐝 𝒏 means the remainder when 𝑚 is divided by 𝑛. Examples: 17mod5 17=3×5+2 ⇒ =2, [, ; , 33=4×7+5 ⇒ 33mod7=5.] If division is exact: 20=4×5+0 ⇒ 20mod5=0. The improved reduction 49 2/99 8 19 18 What does "mod" mean? 𝒎 𝐦𝐨𝐝 𝒏 means the remainder when 𝑚 is divided by 𝑛. Examples: 17 𝑚𝑜𝑑 5 = 2 33 𝑚𝑜𝑑 7 = 5 20 𝑚𝑜𝑑 5 = 0 4 7 33 28 5/ 20 20 The improved reduction Replace: gcd(𝑚,𝑛)=gcd(𝑛,𝑚−𝑛) with: 𝐠𝐜𝐝(𝒎,𝒏)=𝐠𝐜𝐝(𝒏,𝒎 𝒎𝒐𝒅 𝒏) Improved Algorithm If 𝑚<𝑛, interchange the numbers If 𝑛=0, report 𝑚 and stop Otherwise, find 𝑟=𝑚 mod 𝑛 Replace (𝑚,𝑛) by (𝑛,𝑟) Repeat After each division, the remainder becomes the next divisor. Example 1 – gcd(99, 2) Larger should be first, and that is the case here Finding remainder after doing (𝟗𝟗)/(𝟐) Since remainder is 1 Thus, gcd (99, 2) = gcd (2, 1) Again, finding remainder after doing (𝟐)/(𝟏) Since remainder is 0 So, gcd (2, 1) = gcd (1, 0) And, since one number is 0 gcd (1, 0) = 1 Thus, gcd (99, 2) = 1 Example 2 – gcd(825, 375) Larger should be first, and that is the case here Finding remainder after doing (𝟖𝟐𝟓)/(𝟑𝟕𝟓) Since remainder is 75 Thus, gcd (825, 375) = gcd (375, 75) Again, finding remainder after doing (𝟑𝟕𝟓)/(𝟕𝟓) Since remainder is 0 So, gcd (375, 75) = gcd (75, 0) And, since one number is 0 gcd (75, 0) = 75 Thus, gcd (825, 375) = 75 Example 3 – gcd(60, 16) Larger should be first, and that is the case here Finding remainder after doing (𝟔𝟎)/(𝟏𝟔) Since remainder is 12 Thus, gcd (60, 16) = gcd (16, 12) Again, finding remainder after doing (𝟏𝟔)/(𝟏𝟐) Since remainder is 4 Thus, gcd (16, 12) = gcd (12, 4) Since remainder is 0 So, gcd (12, 4) = gcd (4, 0) And, since one number is 0 gcd (4, 0) = 4 Thus, gcd (60, 16) = 4 After each division, the remainder becomes the next divisor. Example 1 – gcd(99, 2) Larger should be first, and that is the case here Finding remainder after doing (𝟗𝟗)/(𝟐) Since remainder is 1 Thus, 49 2/99 8 19 18 gcd (99, 2) = gcd (2, 1) Again, finding remainder after doing (𝟐)/(𝟏) Since remainder is 0 So, gcd (2, 1) = gcd (1, 0) And, since one number is 0 gcd (1, 0) = 1 Thus, gcd (99, 2) = 1 Example 2 – gcd(825, 375) Larger should be first, and that is the case here Finding remainder after doing (𝟖𝟐𝟓)/(𝟑𝟕𝟓) Since remainder is 75 Thus, gcd (825, 375) = gcd (375, 75) Again, finding remainder after doing (𝟑𝟕𝟓)/(𝟕𝟓) Since remainder is 0 So, gcd (375, 75) = gcd (75, 0) And, since one number is 0 gcd (75, 0) = 75 Thus, gcd (825, 375) = 75 Example 3 – gcd(60, 16) Larger should be first, and that is the case here Finding remainder after doing (𝟔𝟎)/(𝟏𝟔) Since remainder is 12 Thus, gcd (60, 16) = gcd (16, 12) Again, finding remainder after doing (𝟏𝟔)/(𝟏𝟐) Since remainder is 4 Thus, gcd (16, 12) = gcd (12, 4) Since remainder is 0 So, gcd (12, 4) = gcd (4, 0) And, since one number is 0 gcd (4, 0) = 4 Thus, gcd (60, 16) = 4 Thus, gcd (99, 2) = 1 Example 2 – gcd(825, 375) Larger should be first, and that is the case here Finding remainder after doing (𝟖𝟐𝟓)/(𝟑𝟕𝟓) Since remainder is 75 Thus, gcd (825, 375) = gcd (375, 75) Again, finding remainder after doing (𝟑𝟕𝟓)/(𝟕𝟓) Since remainder is 0 So, gcd (375, 75) = gcd (75, 0) And, since one number is 0 gcd (75, 0) = 75 Thus, gcd (825, 375) = 75 Example 3 – gcd(60, 16) Larger should be first, and that is the case here Finding remainder after doing (𝟔𝟎)/(𝟏𝟔) Since remainder is 12 Thus, gcd (60, 16) = gcd (16, 12) Again, finding remainder after doing (𝟏𝟔)/(𝟏𝟐) Since remainder is 4 Thus, gcd (16, 12) = gcd (12, 4) Since remainder is 0 So, gcd (12, 4) = gcd (4, 0) And, since one number is 0 gcd (4, 0) = 4 Thus, gcd (60, 16) = 4 2 375 / 825 750 75 Again, finding remainder after doing (𝟑𝟕𝟓)/(𝟕𝟓) Since remainder is 0 So, gcd (375, 75) = gcd (75, 0) And, since one number is 0 gcd (75, 0) = 75 Thus, gcd (825, 375) = 75 Example 3 – gcd(60, 16) Larger should be first, and that is the case here Finding remainder after doing (𝟔𝟎)/(𝟏𝟔) Since remainder is 12 Thus, gcd (60, 16) = gcd (16, 12) Again, finding remainder after doing (𝟏𝟔)/(𝟏𝟐) Since remainder is 4 Thus, gcd (16, 12) = gcd (12, 4) Since remainder is 0 So, gcd (12, 4) = gcd (4, 0) And, since one number is 0 gcd (4, 0) = 4 Thus, gcd (60, 16) = 4 75/375 375 Example 3 – gcd(60, 16) Larger should be first, and that is the case here Finding remainder after doing (𝟔𝟎)/(𝟏𝟔) Since remainder is 12 Thus, gcd (60, 16) = gcd (16, 12) Again, finding remainder after doing (𝟏𝟔)/(𝟏𝟐) Since remainder is 4 Thus, gcd (16, 12) = gcd (12, 4) Since remainder is 0 So, gcd (12, 4) = gcd (4, 0) And, since one number is 0 gcd (4, 0) = 4 Thus, gcd (60, 16) = 4 16 / 60 48 12 Since remainder is 4 Thus, gcd (16, 12) = gcd (12, 4) Again, finding remainder after doing (𝟏𝟐)/(𝟒) Since remainder is 0 So, gcd (12, 4) = gcd (4, 0) And, since one number is 0 gcd (4, 0) = 4 Thus, gcd (60, 16) = 4 1 12/16 12 Since remainder is 0 So, gcd (12, 4) = gcd (4, 0) And, since one number is 0 gcd (4, 0) = 4 Thus, gcd (60, 16) = 4

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.