1. Let a, b, c ≡Z+.
(a) Prove that if a|b, then ac|bc for all c.
(b) If a|bc, can you conclude that either a|b or a|c? Justify your answer with a proof or a counter example.
(c) Prove that gcd(a, a + b) = gcd(a, b).
2. The division algorithm says that when a is divided by b, a unique quotient and remainder is obtained. For a fixed integer b where b>=2, consider the function
f : Z → Z given by f(a) = r where r is the unique remainder obtained when a is divided by b.
(a) What is the range of f? Based on your answer, is f onto?
(b) Determine whether f a 1-1 function.
3. Let a = 5200 and b = 1320.
(a) If a is the dividend and b is the divisor, determine the quotient q and remainder r.
(b) Use the Euclidean Algorithm to find gcd(a, b).
(c) Use your work in part (b) to write gcd(a, b) as a linear combination of a and b.
(d) Give the prime factorization of each of a and b.
(e) Use your answer to part (d) to nd gcd(a, b) and lcm(a, b).
4. Show that there do not exist integers x and y for which 110x + 315y = 12.
5. If a and b are odd integers, prove that a2 +b2 is divisible by 2 but is NOT divisible by 4.
6. Prove that for any prime number p,√p is irrational, by fi rst supposing √p can be expressed as a/b.