Results 1 to 4 of 4

Math Help - Finding integers when I have their lcm and gcd

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    2

    Finding integers when I have their lcm and gcd

    Find all pairs of integers (m, n) such that their greatest common divisor is 1155 and their least common multiple 86625.


    This problem confuses me quite a bit. I just don't see how i could find these numbers. I am not supposed to use a calculator, so I'm guessing it is done with prime factorization. Any help on which direction to start in would be appreciated.

    gianni
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,394
    Thanks
    1479
    Awards
    1
    Quote Originally Posted by gianni View Post
    Find all pairs of integers (m, n) such that their greatest common divisor is 1155 and their least common multiple 86625.
    Look at the fact: 1155 = 3 \cdot 5 \cdot 7 \cdot 11 thus each of M\;\&\;N must contain each of those four primes.
    Moreover, 8715 = 3^2  \cdot 5^3  \cdot 7 \cdot 11 this tells us the highest possible power of the factors in either of M\text{ or }N.
    Because M \cdot N = \gcd (M,N) \cdot \text{lcm}(M,N) = 3^3  \cdot 5^4  \cdot 7^2 \cdot 11^2, this gives at least one solution: M = 3 \cdot 5  \cdot 7 \cdot 11\;\& \,N = 3^2  \cdot 5^3  \cdot 7 \cdot 11.
    Can you find others?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, gianni!

    Find all pairs of integers (m, n) such that their GCD is 1155 and their LCM is 86,625.

    \begin{array}{cccc}\text{Their GCD is:} & 1,\!155 &=& 3\cdot5\cdot7\cdot11 \\ \\[-4mm]<br />
\text{Their LCM is:} & 86,\!625 &=& 3^2\cdot5^3\cdot7\cdot11 \end{array}

    \begin{array}{c}m,n\text{ each contain {\bf at least} }3\cdot 5\cdot 7\cdot 11 \\ \\[-4mm]<br /> <br />
\text{Together, they contain {\bf at most} }3^2\cdot5^3\cdot7\cdot11\end{array}


    There are two basic solutions:

    . . \begin{array}{ccccc}m &=& 3\cdot5\cdot7\cdot11 &=& 1,\!155 \\ n &=& 3^2\cdot5^3\cdot7\cdot11 &=& 86,\!625 \end{array}

    . . \begin{array}{ccccc}m &=& 3^2\cdot5\cdot7\cdot11 &=& 3,\!465 \\ n &=& 3\cdot5^3\cdot7\cdot11 &=& 28,\!875 \end{array}


    And, of course, the roles of m and n can be reversed.

    Last edited by Plato; March 18th 2009 at 03:02 AM. Reason: Typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    2
    Thank you very much for the help. One more question, how did you go about finding that second pair of solution? I'm curious as to why;

    m = 3^2 * 5^2 * 7 * 11
    n = 3 * 5 * 7 * 11

    would not be a valid pair. Both would be less then 86625 and greater then 1155 wont they?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding solutions in integers with constraints...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 21st 2009, 09:41 PM
  2. Replies: 2
    Last Post: November 8th 2008, 08:05 PM
  3. finding integers
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 20th 2008, 11:09 AM
  4. Finding integers? Point of tangency?
    Posted in the Calculus Forum
    Replies: 5
    Last Post: August 22nd 2008, 01:52 PM
  5. Adding Integers - finding temperature
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 11th 2006, 10:12 AM

Search Tags


/mathhelpforum @mathhelpforum