+0

# Least Common Multiple/Greatest Common Denominator

+1
48
2
+485

If the least common multiple of two 6-digit integers has 10 digits, then their greatest common divisor has at most how many digits?

Apr 5, 2021

#1
+423
+1

Note that $\lcm(a,b)\cdot \gcd(a,b)=ab$. Note $ab$ has less than $10^6\cdot 10^6=10^{12}\to 12$ digits. And $\frac{\text{12 digits}}{\text{10 digits}}$ has less than $\frac{10^{11}}{10^{8}}=10^{3}$ digits. The answer is then $2$.

Apr 5, 2021
#2
+485
0

Sorry, the answer was actually 3, which I solved myself, after it said your solution was incorrect. Thank you for trying however! Here is the solution:

Call the two integers a and b. So, $lcm[a,b]*gcd[a,b]=ab$, so $gcd[a,b]=\frac{ab}{lcm[a,b]}$.

We know that $a<10^6$ and $b<10^6$, so $ab<10^12$. We also know that $lcm[a,b] \geq 10^9$. Therefore, $gcd[a,b]<10^3$, so it has at most $\boxed{3}$ digits.

RiemannIntegralzzz  Apr 5, 2021