Euclid’s algorithm Euclid’s algorithm can be used to find the gcd of two integers a and

b. Suppose a>b and let {qi} and {ri} be integer quotients and remainders respectively. The algorithm rests on two principles. First, if b divides

a, then gcd(a,b)¼b. Second, if a¼qbþr, then gcd(a,b)¼gcd(b,r). One can find gcd(a,b) by repeatedly applying the second relation:

a ¼ q0b þ r1 0  r15jbj;

b ¼ q1r1 þ r2 0  r25r1;

r1 ¼ q2r2 þ r3 0  r35r2;

.. .

rk ¼ qkþ1rkþ1 þ rkþ2 0  rkþ25rkþ1:

The process continues until one finds an integer n such that rn þ1¼0, then rn¼gcd(a,b). Find gcd(10480,3920).