How to compare products of prime factors efficiently?
Let's say that $n$ and $m$ are two very large natural numbers, both expressed as product of prime factors, for example:
$n = 3×5×43×367×4931×629281$
$m = 8219×138107×647099$
Now I'd like to know which is smaller. Unfortunately, all I have is an old pocket calculator that can show at most (say) ten digits. So while there are enough digits to enter each factor individually, $n$ and $m$ are both too large to fit in the calculator. To my disappoint, they are also so close that even their logarithms are indistinguishable looking at the first 10 digits.
Question: how would one go to determine which one of two integers is smaller in a case like this? Any easier alternative than calculating the full decimal expansion of both products with pen and paper?
If you can prove that the two numbers are fairly close, then you could use modular arithmetic.
For example, we know that the two numbers are indistinguishable by looking at only $10$ digits. Specifically, we can work out: $$ n/10000=\frac1{10000}\times3×5×43×367×4931×629281=7345230022\\ m/10000=\frac1{10000}\times8219×138107×647099=7345230022 $$ (both correct to $10$ significant figures). This means that $m$ and $n$ differ by less than $10000$. Working modulo $10000$: $$ 3\times5\times43\times367=236715\equiv-3285\\ -3285\times4931=-16198335\equiv1665\\ 629281\equiv-719\\ 1665\times-719=-1197135\equiv2865 $$ Therefore: $$ n\equiv2865\mod10000 $$ Now: $$ 8219\equiv-1781\\ 138107\equiv-1893\\ 647099\equiv-2901\\ -1781\times-1893=3371433\equiv1433\\ 1433\times-2901=-4157133\equiv2867 $$ Therefore: $$ m\equiv2867\mod10000 $$ Now we've worked out the last four digits of $m$ and $n$. Since we know that $m$ and $n$ differ by less than $10000$, we must have that $m>n$.
Update: As Paŭlo points out, it isn't enough just to know that $n$ and $m$ differ by less than $10000$ and that $n\equiv2865,m\equiv2867$. For example, $12865$ and $2867$ differ by less than $10000$ and satisfy the same congruences, yet $12865>2867$. In this case, however, our calculations are enough to give us the answer. From our first calculation, we know that:
$$ 73452300215000\le m,n\le73452300225000 $$ This, coupled with the facts that $n\equiv2865,m\equiv2867\mod10000$, is enough to tell us that $m>n$.