The Euclidean algorithm, which is used to find the greatest common divisor of two non-zero integers, is essentially several applications of the division algorithm. The key arithmetic observation that makes the division algorithm so helpful is the following: If a, b E Z are non-zero and we use the division algorithm to write a = bq+r, for some q, rez, then ged(a, b) = ged(b, r). In class, we brazenly used this fact without proof. It is time to prove that this is always true.(a) Assume that a = bq + r. Let D(a, b) be the set of common divisors of a and b, and let D(br) be the set of common divisors of b and r. Show that D(a, b) = D(0,r). Note that you are asked to show that two sets are equal. Thus, you must show that if D(a, b) C D(b, r) and D(0,r) C D(a, b). (b) Use your result from (a) to conclude that ged(a, b) = ged(b, r).