1) For each of the following pairs of numbers, use the Euclidean algorithm to compute gcd(a, b) and to find integers x, y such that ax + by = gcd(a, b).
(a) a = 59, b = 26
(b) a = 85, b = 34
(c) a = 378, b = 330
2) Fix integers a, b, d with d ≠ 0.
(a) Prove that if d is a divisor of a or b, then d is a divisor of the product ab; that is, prove that
d | a ∨ d | b ⇒ d | ab.
(b) Show that the converse of the above statement is false by demonstrating a specific counter-example; that is, find specific numbers a, b, d that disprove the statement
d | ab ⇒ d | a ∨ d | b.
In other words, if d | ab and d | a, it is not necessarily true that d | b.
(c) Although the converse is false, we can prove the following proposition, which is very similar: if d is a divisor of ab and gcd(a, d) = 1, then d must be a divisor of b; that is,
d | ab ∧ gcd(a, d) = 1 ⇒ d | b.
Prove this statement directly by assuming the hypotheses are true and proving the conclusion must also be true. (Hint: first use Bezout's identity to write ax + dy = 1 for some x, y ∈ Z, then multiply both sides of this equation by b.)