1. Prove that there are no integers x and y such that 333x + 456y = 4.

2. Find the smallest positive integer x so that 157x leaves remainder 10 when divided by 24. Show your work.

3. For all integers a, b, c, prove that GCD(a, c) = 1 and GCD(b, c) = 1 if and only if GCD(ab, c) = 1.

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

(4) 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.