6
$\begingroup$

I know that $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab$, so if we know $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$ and we want to find out $a$ and $b$, besides factoring $ab$ and find possible values, can we find these two integers faster?

  • 0
    Or $(a,b)=(2,3)$ and $(a,b)=(1,6)$.2012-03-21

5 Answers 5

7

If you scale the problem by dividing through by $\rm\:gcd(a,b)\:$ then you are asking how to determine coprime factors of a product. This is equivalent to factoring integers.

Your original question, in the special case $\rm\:gcd(a,b) = lcm(a,b),\:$ is much easier:

Hint $\:$ In any domain $\rm\:gcd(a,b)\ |\ a,b\ |\ lcm(a,b)\ $ so $\rm\:lcm(a,b)\ |\ gcd(a,b)\ \Rightarrow $ all four are associate. Hence all four are equal if they are positive integers. If they are polynomials $\ne 0$ over a field then they are equal up to nonzero constant multiples, i.e. up to unit factors.

3

If $a \neq b$ then $\gcd(a,b) \leq \min\{a,b\} < \max\{a,b\} \leq \mathrm{lcm}(a,b) = \gcd(a,b)$, contradiction...

Edit: This answer was posted when the question was finding $a,b$ when $\gcd(a,b) = \mathrm{lcm}(a,b)$. For a good answer to the new question, see Bill's answer.

3

There are $2^m$ possible answers, where $m$ is the number of distinct primes dividing the ratio of LCM to GCD. If $ \eqalign{ \text{gcd}(x,y) &= \prod p_i^{a_i} \\ \text{lcm}(x,y) &= \prod p_i^{b_i} } $ (with $a_i\le b_i$) and $ \eqalign{ x &= \prod p_i^{c_i} \\ y &= \prod p_i^{d_i} } $ then each $c_i$ is either $a_i$ or $b_i$, and each $d_i$ must be the other one. This is because $a_i=\min(c_i,d_i)$ and $b_i=\max(c_i,d_i)$. To invert this process, we have more than one solution whenever $a_i\ne b_i$. This gives two choices for each of the $m$ values of $i$ where $a_i, or $2^m$ total possibilities.

  • 1
    Nice. I was just about to write an answer about the number of possible answers, but you've saved me the effort (+1).2013-04-04
2

For $a,b\geq 0$, $\gcd(a,b)\leq \min(a,b)$ and $\text{lcm}(a,b)\geq \max(a,b)$ so that the only way we can have $\gcd(a,b)=\text{lcm}(a,b)$ is when $a=b=\gcd(a,b)=\text{lcm}(a,b).$

  • 0
    Sorry my original description is incorrect...2012-03-03
2

Given gcd(a,b) and lcm(a,b), the possible values for a (which are the same as the possible values for b, by symmetry) are the unitary divisors of lcm(a,b)/gcd(a,b) multiplied by gcd(a,b). So suppose gcd(a,b) = 3 and lcm(a,b) = 6300. Factoring 6300/3 gives $2^2\cdot3\cdot5^2\cdot7$ and so the possible values are the members of $\{3,2^2\cdot3,3^2,2^2\cdot3^2,3\cdot5^2,2^2\cdot3\cdot5^2,3^2\cdot5^2,2^2\cdot3^2\cdot5^2,3\cdot7,2^2\cdot3\cdot7,3^2\cdot7,2^2\cdot3^2\cdot7,3\cdot5^2\cdot7,2^2\cdot3\cdot5^2\cdot7,3^2\cdot5^2\cdot7,2^2\cdot3^2\cdot5^2\cdot7\}$ (taking, in each case, all factors of a prime together, then multiplying by 3).