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

RiemannIntegralzzz Apr 5, 2021

#1**+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$.

thedudemanguyperson Apr 5, 2021

#2**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