In: Advanced Math
Let a and b be integers which are not both zero.
(a) If c is an integer such that there exist integers x and y with ax+by = c, prove that gcd(a, b) | c.
(b) If there exist integers x and y such that ax + by = 1, explain why gcd(a, b) = 1.
(c) Let d = gcd(a,b), and write a = da′ and b = db′ for some a′,b′ ∈ Z. Prove that gcd(a′,b′) = 1.