Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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|. –  ShreevatsaR Mar 3 '12 at 17:15
    
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. –  André Nicolas Mar 3 '12 at 17:44
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. –  Bill Dubuque Mar 3 '12 at 17:44
    
No, lcm(a,b) and gcd(a,b) do not determine a and b. Consider (a,b)=(3,30) and (a,b)=(6,15). –  Did Mar 3 '12 at 20:22
    
Or $(a,b)=(2,3)$ and $(a,b)=(1,6)$. –  TonyK Mar 21 '12 at 18:58

5 Answers 5

up vote 6 down vote accepted

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.

share|improve this answer

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.

share|improve this 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<b_i$, or $2^m$ total possibilities.

share|improve this answer
    
Nice. I was just about to write an answer about the number of possible answers, but you've saved me the effort (+1). –  robjohn Apr 4 '13 at 17:36

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).$$

share|improve this answer
    
They should really make that "A new answer has been posted!"-message appear sooner. Anyway, +1 of course :) –  TMM Mar 3 '12 at 17:20
    
Sorry my original description is incorrect... –  LBJ Mar 3 '12 at 17:25

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.