Euclidean algorithm for the gcd given a and b with a>b gcd(a, b)=gcd(b, a mod b) algorithm Input: 2 non-negative integers a& b with a>b Output: gcd(a, b while b≠0 Set rta mod b.atb.b<r return(a) Extended Euclidean algorithm Output: d=gcd(a, b)and integers x, y satisfying ax+ by 2323 Euclidean algorithm for the gcd • given a and b with a ≥ b – gcd(a,b) = gcd(b, a mod b) • Algorithm – Input: 2 non-negative integers a & b with a ≥ b – Output: gcd(a, b) – while b ≠ 0 • Set ra mod b, a  b, b  r – return (a) • Extended Euclidean Algorithm – Output: d = gcd(a, b) and integers x, y satisfying ax+by = d