Results 1 to 7 of 7

Math Help - three problems I am stuck on

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    55

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,814
    Thanks
    703
    Hello, minivan15!

    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}<br />
\text{Factors} & {GCD} \\ \hline<br /> <br />
6 ,360 & 6 \\<br />
{\color{red}\rlap{//////}}12,180 & {\color{red}\rlap{//}}12 \\<br />
18,120 & 6 \\ <br />
24,90 & 6 \\<br />
30,72 & 6 \\<br />
{\color{red}\rlap{/////}}36,60 & {\color{red}\rlap{//}}12 \\<br />
{\color{red}\rlap{/////}}48,45 & {\color{red}\rlap{/}}3<br />
\end{array}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    great, thank you! Any ideas on the other two?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Just to get you started on 2., if d divides m+n and m+7n, then d must divide (m+7n)(m+n) = 6n.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by minivan15 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2008
    Posts
    55
    great! I worked it out, thank you very much for your help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. two problems I am really stuck on
    Posted in the Trigonometry Forum
    Replies: 0
    Last Post: November 13th 2011, 12:59 PM
  2. stuck on these 3 problems
    Posted in the Geometry Forum
    Replies: 1
    Last Post: March 1st 2010, 10:32 PM
  3. Stuck on a few problems
    Posted in the Statistics Forum
    Replies: 2
    Last Post: October 1st 2009, 07:06 PM
  4. Stuck on these problems
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 29th 2008, 05:19 AM
  5. Stuck on a few problems
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: September 6th 2008, 08:29 PM

Search Tags


/mathhelpforum @mathhelpforum