Facing a number theoretical problem related to least common multiple Recently I have faced the following problem.
I'm given 3 integers a,b and L where LCM(a,b,c)=L and c is another integer.
It is worthy of mentioning that the value of c will be smallest i.e if there are many possible values of c then we have to choose the one which is smallest.
I myself solved this problem partially using the following fact
LCM(a,b,c)=LCM(LCM(a,b),c)=L.Also I used the following procedure.
Firstly,I found out LCM(a,b).Secondly, I divide L by LCM(a,b). 
My procedure works for some cases.For example, if a=3,b=5 and L=30,the value of c will be 2 and my above procedure give correct result for this case.
But there are some cases for which my procedure does't work.Here is a example.
If a=10,b=15 and L=600 then the value of c will be 200 but my procedure give the value of c, 20.
How can I get correct result for the given second case for which my procedure doesn't work? 
 A: For each prime $p$ dividing $L$, test the power of $p$ that divides $L$ and lcm$[a,b]$: say $p^s$ exactly divides $L$ and $p^r$ exactly divides lcm$[a,b]$. If $r=s$, then $p$ will not divide $c$ (your method gives this). But if $r<s$, then $p^s$ must divide $c$ (your method gives only $p^{s-r}$). Do this for every prime $p$ dividing $L$, and you will have assembled $c$.
A: use prime factorization
$L=600=2^33^15^2$
$a=10=2^13^05^1$
$b=15=2^03^15^1$
with an appropriate choice of the exponents
$c=200=2^33^05^2$
A: This question was cross posted on CS.SE but realize that it has relevance here as well.
Realize that $\text{lcm}(a,b,c) = \frac{abc}{\gcd(ab,bc,ac)}$, which can be seen by writing prime decompositions and noting that $$i+j+k-\text{min}
(i+j,j+k,i+k)=\text{max}(i,j,k)\,.$$
Then $$c = \frac{L}{ab} \gcd(ab,bc,ac)$$ and $$\gcd(ab,bc,ac) = \gcd(ab,\gcd(bc,ac)) = \gcd(ab, c\cdot\gcd(a,b)) = \gcd(a,b) \cdot \gcd\left(\frac{ab}{\gcd(a,b)}, c\right)$$
Therefore,
$$c =\frac{L}{ab}\gcd(a,b)\cdot\gcd\left(\frac{ab}{\gcd(a,b)},c\right) =  \frac{L}{\text{lcm}(a,b)}\gcd(\text{lcm}(a,b),c)$$.
Thus, $c$ is minimized when $\gcd(\text{lcm}(a,b),c)$ is minimized. As you note, this $\gcd$ can occasionally be 1 but not always.
Thus we want $c = k\frac{L}{\text{lcm}(a,b)}$ for some integer $k$, but note that the issue arises because, for all possible choices of $k$, $$\gcd\left(\text{lcm}(a,b),k\frac{L}{\text{lcm}(a,b)}\right) \ge \gcd\left(\text{lcm}(a,b),\frac{L}{\text{lcm}(a,b)}\right)$$ which may be greater than 1, and in fact $\gcd(\text{lcm}(a,b),c)$ is minimized when: $$\gcd\left(\text{lcm}(a,b),k\frac{L}{\text{lcm}(a,b)}\right) = \gcd\left(\text{lcm}(a,b),\frac{L}{\text{lcm}(a,b)}\right)$$ and note that this equality is always true when $k = \gcd\left(\text{lcm}(a,b),\frac{L}{\text{lcm}(a,b)}\right)$.
Therefore, $c = \frac{L}{\text{lcm}(a,b)}\gcd\left(\text{lcm}(a,b),\frac{L}{\text{lcm}(a,b)}\right)$ will always be a minimum and notably can be computed in polynomial time.
