Euclid’s and Āryabhaṭa’s Algorithms
Last updated at October 28, 2026 by Teachoo
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