Last updated at October 28, 2026 by Teachoo
Transcript
Question 1 (i) Compute the following using the improved version of Euclidβs algorithm. (i) gcd(375, 825) Larger number should be first. So, we write gcd(375, 825) = gcd(825, 375) Finding remainder after doing (πππ)/(πππ) 2 375 / 825 750 75 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) 75/375 375 And, since one number is 0 gcd (75, 0) = 75 Thus, gcd (825, 375) = 75