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?

  • 1
    If gcd(a,b)=lcm(a,b), then a=±b. This is because gcd(a,b) ≤ min(|a|, |b|) ≤ max(|a|,|b|) ≤ lcm(a,b), with equality holding iff |a| = |b|.2012-03-03
  • 0
    To your revised question: Knowing the prime factorization of $\mathrm{lcm}$ divided by $gcd$ is enough to determine all pairs $(a,b)$. That is equivalent to factorization if the $\gcd$ is $1$, but one can make up situations where the $\gcd$ is large and hard to factor, while factoring $\mathrm{lcm}$ divided by $\gcd$ is easy.2012-03-03
  • 7
    When a questions has some answers, and you change the question so that the answers no longer apply nontrivially, it is better to post a new question.2012-03-03
  • 0
    No, lcm(a,b) and gcd(a,b) do not determine a and b. Consider (a,b)=(3,30) and (a,b)=(6,15).2012-03-03
  • 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
    They should really make that "A new answer has been posted!"-message appear sooner. Anyway, +1 of course :)2012-03-03
  • 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).