# three problems I am stuck on

Printable View

• March 4th 2009, 11:01 AM
minivan15
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
• March 4th 2009, 02:28 PM
Soroban
Hello, minivan15!

Quote:

1. Find all pairs of positive integers $0 < a < b$ such that $\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.

. . $\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}$

• March 4th 2009, 07:56 PM
minivan15
great, thank you! Any ideas on the other two?
• March 5th 2009, 01:51 AM
Opalg
Just to get you started on 2., if d divides m+n and m+7n, then d must divide (m+7n)–(m+n) = 6n.
• March 5th 2009, 02:03 AM
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?
• March 5th 2009, 04:16 AM
Opalg
Quote:

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.
• March 5th 2009, 02:57 PM
minivan15
great! I worked it out, thank you very much for your help!