## Math 310: Problem set 4

Instructions: This problem set is due Thursday, September 21, 2006. Your goal is not only to give correct answers but to communicate your ideas well. Make sure you use good English.
1. The goal of this problem is to prove the theorem that every integer n > 1 is either prime or a product of primes. To do this, let S be the set of integers n > 1 such that n is not prime nor is it a product of primes.
• Prove that S has no least element.
• Explain why this means that S is empty and hence that the theorem is true.
2. Find all integer solutions (if any) to 21x + 15y = 12. Justify your answer.
3. Find all integer solutions (if any) to 21x + 15y = 11. Justify your answer.
4. Let a and b be integers such that ab is not zero. Let g=gcd(a,b) and let m=a/g and n=b/g. Prove that gcd(m,n) = 1.
5. Let a and b be integers such that ab is not zero. Let g=gcd(a,b) and let m=a/g and n=b/g. Is it true that gcd(a,n) = 1? Either prove that it is true or give a specific counterexample (i.e., give specific numbers for a and b which shows that it is false).
6. Let m, n and c be integers such that mn is not zero but c > 0. Is it true that c(gcd(m,n)) = gcd(mc,nc)? Either prove that it is true or give a specific counterexample (i.e., give specific numbers for m, n and c which shows that it is false).