MATH203: Past Exam Question Find the gcd of a = 80 and b = 28 using Euclid's algorithm. Quiz Forum 6/2/2020 Unifiedcamp 2 Answer(s) 848 views
Answers ( 2 )
By CyberKing
Answer:
GCD(80, 28) = 4
Solution
Set up a division problem where a is larger than b.
a ÷ b = c with remainder R.
Do the division. Then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.
*. 80 ÷ 28 = 2 R 24 (80 = 2 × 28 + 24)
*. 28 ÷ 24 = 1 R 4 (28 = 1 × 24 + 4)
*. 24 ÷ 4 = 6 R 0 (24 = 6 × 4 + 0)
Def Euclid(a,b):
r=1
while r!=0:
If a>b:
c = a/b
r = a%b
a = b
b = r
print(str(int(c)) + 'R' + str(r))
Indentation might not be correct using a phone to type.. So yh
#pius adams Ijachi