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?
If we know the GCD and LCM of two integers, can we determine the possible values of these two integers?
-
0Or $(a,b)=(2,3)$ and $(a,b)=(1,6)$. – 2012-03-21
5 Answers
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.
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.
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
-
1Nice. 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
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).$
-
0Sorry my original description is incorrect... – 2012-03-03
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).