LCM: Counting number of digits

Question

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

I can not figure out a way to solve this. I thought that the answer might be $6+6-10=2$, but that is clearly wrong. I also tried coming up with various examples but to no avail. Is there a rigorous way to solve this without guessing?

Answer 1

Hint: for any two positive integers $m,n$ we have $m\times n=\gcd(m,n)\times\mathrm{lcm}(m,n)$.

Answer 2

We know the product of two numbers LCM and GCD is the product of the two numbers. We are told that the numbers are in the interval $[10^5,10^6-1]$ and their LCM is in the interval $[10^9,10^{10}-1]$.

So the largest possible GCD (ignoring the details of which two numbers or what their particular LCM is) is the largest possible ratio of the product of two numbers in the interval $[10^5,10^6-1]$ to a number in the interval $[10^9,10^{10}-1]$. (That is, the largest possible ratio of the product to the LCM.) A ratio (of independent numbers) is maximized when the numerator is maximized and the denominator is minimized, so the maximum of the ratio is $(10^6-1)^2/10^9 = 999.998{\dots}$. So no GCD of such a pair of integers can have as many as four digits.

OP gives the pair $900\,500$ and $900\,750$ in a comment to another answer, having GCD $250$, so we directly exhibit that there is a suitable pair having three digit GCD. Therefore, three is the maximum number of digits for the GCD of a pair of integers with the given constraints.

---

A short computer search finds the greatest GCD of two such numbers is $998$, for the pair $(998\,998, 999\,996)$ with LCM $1\,000\,995\,996$.

If you choose to run your own search, it is significantly faster to look for pairs with GCD $999$ then with GCD $998$, leveraging the coarse upper bound we found above. Then search for pairs $(x,y)$ with $x \leq y$, $x = ug$ and $y = vg$ both multiples of the assumed GCD, $g$, (so actually iterating over values of $u$ and $v$) with $\gcd(u,v) = 1$ and $\mathrm{lcm}(x,y) = g u v$ in the right range. (You can use the ranges to restrict $u$ and $v$ further so that very few $(u,v)$ pairs are ever actually checked.