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?
-
1If 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
-
0To 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
-
7When 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
-
0No, 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
-
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).$$
-
0They should really make that "A new answer has been posted!"-message appear sooner. Anyway, +1 of course :) – 2012-03-03
-
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).