In the box on the Euclidean algorithm, we made a number of assertions without proof. Prove each of the following:
a) The Euclidean algorithm as stated always works. In particular, gcd(6, c) = gcd(o, 6), where c is the nonzero remainder of a/b.
b) gcd(a,&) = gcd(a, -b).
c) gcd(ai,a 2 ,.. . ,o„) = gcd(gcd(oi, a 2 ),a 3 , a 4 ,.. . ,o n ) for n > 2.
d) The GCD is really a function on sets of integers; i.e., order doesn't matter. Show the commutative law for GCD: gcd(a, b) = gcd(6, a). Then, show the more difficult statement, the associative law for GCD: gcd(gcd(a, b),c) = gcd(a,gcd(6, c)). Finally, show that together these laws imply that the GCD of a set of integers is the same, regardless of the order in which the GCD's of pairs of integers are computed.
e) If S and T are sets of integers, then gcd(5 U T) = gcd(gcd(5), gcd(T)).