In this question, well figure out how to find the greatest common divisor of three integers.

(a) Prove: for any positive integers a, b, d, if d | a and d | b, then d | GCD(a, b).

(b) Given positive integers a, b, c, we define GCD(a, b, c) to be the positive integer d such that:

i. d | a and d | b and d | c

ii. for any positive integer e, if e | a and e | b and e | c, then e d.

Prove: GCD(a, b, c) = GCD(a, GCD(b, c)).

(Hint: you might find question (a) useful here)

(c) Use question (b) to help you calculate GCD(272715979, 347551889, 247214621).

(d) For all integers a, b, c, e, prove that the Diophantine equation ax + by + cz = e has a solution if and only if GCD(a, b, c) | e.

The procedure of proof should follow the following format. The answer should like that.

Example

Proposition: For any a,b, if at least one of a,b is not zero, then GCD(a/GCD(a,b), b/GCD(a,b)) = 1

Proof. Let a and b be arbitrary integers.

(1)Since at least one of a,b is non-zero, by definition GCD(a,b) exists and is a positive integer.

(2)By Bzouts Lemma, there exist x and y such that ax + by = GCD(a,b)

(3)By (1), GCD(a,b) is a non-zero integer.

(4)From (2), ax + by = GCD(a,b), and by (3), we can divide both sides by GCD(a,b), so (a/GCD(a,b))x + (b/GCD(a,b))y = 1

(5)By the characterization of GCD, since 1 divides both a/GCD(a,b) and b/GCD(a,b), and from

(6) we know (a/GCD(a,b))x + (b/GCD(a,b))y = 1, it follows that GCD(a/GCD(a,b), b/GCD(a,b)) = 1.