Harbourne's Math 310 Problem set 4

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.
  - Suppose that it did. Let m be this minimum element. Then m is not prime (since, by definition, no element of S is a prime), so it factors as m = ab, with 1 < a < m and 1 < b < m. Thus neither a nor b is in S, since each is less than m. But this means a is either prime or a product of primes and the same for b, which means that m is a product of primes. But this would mean m is not in S. Thus there can be no least element of S.
- Explain why this means that S is empty and hence that the theorem is true.
  - By the well ordering principle, if S is not empty then it has a least element. Since we just saw that it has no least element, S must be empty. This means there are no integers n > 1 for which our theorem fails to be true, hence the theorem is true.
  Comment: I had hoped that people would use the proof in class (showing that every integer n > 1 has a prime factor) as a model for doing Problem 1 above. If you compare the proof here with the one in class you'll see they have a lot in common.
Find all integer solutions (if any) to 21x + 15y = 12. Justify your answer.
- We first find one solution, either by Euclid's algorithm or by guess and check or whatever (for example, 21-15=6 so 21*2+15*(-2) = 12, which gives x=2, y=-2 as a solution). Then Proposition 5, p. 34, says that the set of all solutions is { (2+5t,-2-7t) : t is an integer }.
Find all integer solutions (if any) to 21x + 15y = 11. Justify your answer.
- There are no solutions, since for any integers x and y, 21x+15y is divisible by 3, but 11 is not divisible by 3.
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.
- Pick integers u and v such that au + bv = g, which we can do by Bezout's Identity, for example. Divide through by g to get mu + nv = 1. Thus 1 is an integer linear combination of m and n, but any common factor of m and n must also divide every integer linear combination of m and n, and hence must divide 1. Thus 1 is the largest common factor of m and n; i.e., 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).
- This is false. Let a = 18, b = 12, so g = 6. But gcd(18,2) is not 1.
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).
- This is true. In fact Problem 4 above is just the special case for which gcd(m,n) = 1. To prove this more general case, note that c(gcd(m,n)) is a common factor of both cm and cn. Thus c(gcd(m,n)) is less than or equal to gcd(mc,nc). On the other hand, we can solve mx + ny = gcd(m,n), hence also mcx + ncy = c(gcd(m,n)). Thus c(gcd(m,n)) is a positive integer linear combination of mc and nc. But we proved in class that gcd(mc,nc) is the smallest integer linear combination of mc and nc which is positive, which means that gcd(mc,nc) is less than or equal to c(gcd(m,n)). Thus we must have c(gcd(m,n)) = gcd(mc,nc).