# Thread: three problems I am stuck on

1. ## three problems I am stuck on

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

2. Hello, minivan15!

1. Find all pairs of positive integers $\displaystyle 0 < a < b$ such that $\displaystyle \text{gcd}(a,b) = 6\,\text{ and }ab = 2160$
Some brute-force Listing is required, but we can minimize it.

Factor 2160 into two parts.
One part must have a factor of 6.
The two parts must have a GCD of 6.

. . $\displaystyle \begin{array}{c|c} \text{Factors} & {GCD} \\ \hline 6 ,360 & 6 \\ {\color{red}\rlap{//////}}12,180 & {\color{red}\rlap{//}}12 \\ 18,120 & 6 \\ 24,90 & 6 \\ 30,72 & 6 \\ {\color{red}\rlap{/////}}36,60 & {\color{red}\rlap{//}}12 \\ {\color{red}\rlap{/////}}48,45 & {\color{red}\rlap{/}}3 \end{array}$

3. great, thank you! Any ideas on the other two?

4. Just to get you started on 2., if d divides m+n and m+7n, then d must divide (m+7n)–(m+n) = 6n.

5. 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?

6. Originally Posted by minivan15
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.

7. great! I worked it out, thank you very much for your help!