How to compute gcd(x,y) Observation:gcd(x,y)=ged(x-y,y)=gcd(x-2y,y)=.... Suppose x>y,x=ky+d where d<y,thus gcd(x,y)=ged(ky+d,y)=gcd(ky+d-ky,y)=gcd(d,y) Euclid's Algorithm: integer euclid(pos.integer m,pos.integer n) x=m,y=n while(y>0) r=x mod y x=y y=r return x 22 How to compute gcd(x,y)  Observation: gcd(x,y) = gcd(x-y, y) = gcd(x-2y, y) = ….  Suppose x>y, x=ky+d where d<y, thus gcd(x,y)=gcd(ky+d, y)=gcd(ky+d-ky, y)=gcd(d,y)  Euclid’s Algorithm: integer euclid(pos. integer m, pos. integer n) x = m, y = n while(y > 0) r = x mod y x = y y = r return x