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

SolutionSet 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