Euclidβs and ΔryabhaαΉaβs Algorithms
Euclidβs and ΔryabhaαΉaβs Algorithms
Last updated at October 28, 2026 by Teachoo
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