# Finding integers when I have their lcm and gcd

• Mar 17th 2009, 01:27 PM
gianni
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
• Mar 17th 2009, 02:29 PM
Plato
Quote:

Originally Posted by gianni
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?
• Mar 17th 2009, 04:43 PM
Soroban
Hello, gianni!

Quote:

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]
\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]

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

• Mar 17th 2009, 10:25 PM
gianni
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?