The improved (division) version of Euclid's algorithm for gcd(m,n):
-
If m<n, reverse the numbers and compute gcd(n,m).
-
If n=0, report the answer as m.
-
Otherwise, reduce the problem to computing gcd(n,mmodn), where mmodn is the remainder when m is divided by n.
(i) gcd(375,825)
Since 375<825, Step 1 reverses the numbers: compute gcd(825,375).
825=2×375+75, so 825mod375=75. Step 3 reduces the problem to gcd(375,75).
375=5×75+0, so 375mod75=0. Step 3 reduces the problem to gcd(75,0).
Since n=0, Step 2 gives the answer gcd(375,825)=75.
Number of reductions: 2. So gcd(375,825)=75.
(ii) gcd(51000,81000)
Since 51000<81000, Step 1 reverses the numbers: compute gcd(81000,51000).
81000=1×51000+30000, so 81000mod51000=30000. Step 3 reduces the problem to gcd(51000,30000).
51000=1×30000+21000, so 51000mod30000=21000. Step 3 reduces the problem to gcd(30000,21000).
30000=1×21000+9000, so 30000mod21000=9000. Step 3 reduces the problem to gcd(21000,9000).
21000=2×9000+3000, so 21000mod9000=3000. Step 3 reduces the problem to gcd(9000,3000).
9000=3×3000+0, so 9000mod3000=0. Step 3 reduces the problem to gcd(3000,0).
Since n=0, Step 2 gives the answer gcd(51000,81000)=3000.
Number of reductions: 5. So gcd(51000,81000)=3000.
(iii) gcd(1789287,237656)
1789287=7×237656+125695, so 1789287mod237656=125695. Step 3 reduces the problem to gcd(237656,125695).
237656=1×125695+111961, so 237656mod125695=111961. Step 3 reduces the problem to gcd(125695,111961).
125695=1×111961+13734, so 125695mod111961=13734. Step 3 reduces the problem to gcd(111961,13734).
111961=8×13734+2089, so 111961mod13734=2089. Step 3 reduces the problem to gcd(13734,2089).
13734=6×2089+1200, so 13734mod2089=1200. Step 3 reduces the problem to gcd(2089,1200).
2089=1×1200+889, so 2089mod1200=889. Step 3 reduces the problem to gcd(1200,889).
1200=1×889+311, so 1200mod889=311. Step 3 reduces the problem to gcd(889,311).
889=2×311+267, so 889mod311=267. Step 3 reduces the problem to gcd(311,267).
311=1×267+44, so 311mod267=44. Step 3 reduces the problem to gcd(267,44).
267=6×44+3, so 267mod44=3. Step 3 reduces the problem to gcd(44,3).
44=14×3+2, so 44mod3=2. Step 3 reduces the problem to gcd(3,2).
3=1×2+1, so 3mod2=1. Step 3 reduces the problem to gcd(2,1).
2=2×1+0, so 2mod1=0. Step 3 reduces the problem to gcd(1,0).
Since n=0, Step 2 gives the answer gcd(1789287,237656)=1.
Number of reductions: 13. So gcd(1789287,237656)=1.
(iv) gcd(2587392,157656)
2587392=16×157656+64896, so 2587392mod157656=64896. Step 3 reduces the problem to gcd(157656,64896).
157656=2×64896+27864, so 157656mod64896=27864. Step 3 reduces the problem to gcd(64896,27864).
64896=2×27864+9168, so 64896mod27864=9168. Step 3 reduces the problem to gcd(27864,9168).
27864=3×9168+360, so 27864mod9168=360. Step 3 reduces the problem to gcd(9168,360).
9168=25×360+168, so 9168mod360=168. Step 3 reduces the problem to gcd(360,168).
360=2×168+24, so 360mod168=24. Step 3 reduces the problem to gcd(168,24).
168=7×24+0, so 168mod24=0. Step 3 reduces the problem to gcd(24,0).
Since n=0, Step 2 gives the answer gcd(2587392,157656)=24.
Number of reductions: 7. So gcd(2587392,157656)=24.
Final answers: (i) 75, (ii) 3000, (iii) 1, (iv) 24. Note that (iii), with 7-digit numbers, needed only 13 reductions, while the subtraction version needed 7 reductions for the much smaller pair 375 and 825 in (i).