## 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.
- 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.

- Find all integer solutions (if any) to 21x + 15y = 12.
Justify your answer.
- Find all integer solutions (if any) to 21x + 15y = 11.
Justify your answer.
- 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.
- 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).
- 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).