Euclid's Algorithm

Question 1

Compute the gcd of 90 and 24

Answer 1

Divide previous two and keep remainder

90/24 remainder is 18
24 /18 remainder = 6
18/ 6 remainder = 0

gcd is 6

Question 2

Why is euclid memory efficient?

Answer 2

Only store maximum three balues at once

Question 3

Extended Euclid: output

Answer 3

gcd(a,b), u, v such that gcd(a,b) = au + bv

Question 4

Extended Euclid: Compute 90 and 24.

Answer 4

gcd(90,24) = 90u + 24v

90 = 243 + 18
24 = 181 + 6
18 = 6*3+0

18 = 90-243
6 = 24-181

6 = 24-(90-243)1
6 = -90+24*4

so u = -1 and v = 4