Hello, minivan15!
Some brute-force Listing is required, but we can minimize it.1. Find all pairs of positive integers such that
Factor 2160 into two parts.
One part must have a factor of 6.
The two parts must have a GCD of 6.
. .
1. Find all pairs of positive integers 0 < a < b such that gcd(a,b) = 6 and ab = 2160
obviously I could list all integers of this form and check each, I am wondering if there is a more theoretical, efficient way?
2. Let m and n be two integers such that the greatest common divisor, of m and n, gcd(m,n) = 1. What values can the greatest common divisor of (m + n), (m + 7n) take? i.e what values can gcd (m+n, m+7n) take? Why?
3. Let a,b,m,n be positive integers such that a|m (a divides m) and b|m and gcd (m/a, m/b) = 1. Prove that if a|n and b|n, then m|n
yes, I actually was working on it more and reached that conclusion myself
where I went from there was to do my best to narrow down the choices, I said:
let gcd(m + n, m + 7n) = d
as you said, d|6n
gcd(d,6) = 1 or gcd (d,6) does not equal 1
If gcd (d,6) = 1 then by Euclid's Lemma d|n
and if d|n then d|(m + n) iff d|m, but if d|m then d would divide both m and n, contradicting the assumption that gcd(m,n) = 1 for d > 1
so either d = 1 or gcd(d,6) > 1
what I was working on next was to look at the options when gcd (d,6) > 1. I started attempting to show that if d > 6 and gcd(d,6) > 1 then d must be a multiple of b, which seemed simple at first although the more I thought about it the less sure I became...essentially now I am stuck at this part, where should I go from here?
That's good progress. But suppose that instead of taking d to be the gcd of m+n and m+7n, you take it to be a prime divisor of m+n and m+7n. Then d|6n, but you have shown that d does not divide n. Therefore d|6. So the only possibilities for d are d=2 or d=3.
Pushing that argument a bit further, you should be able to show that the only possibilities for gcd(m+n,m+7n) are 1, 2, 3 and 6. After that, you can start playing with numbers to find examples showing that all these possibilities can occur. For example, if m=5 and n=7 then gcd(m,n)=1 and gcd(m+n,m+7n) = gcd(12, 54) = 6.