The number $555,555$ can decompose, as the product of two factors of three digits, in how many ways?

The number $555,555$ can decompose, as the product of two factors of three digits, in how many ways?

I've seen the answer to the question, and there is only one way: Since $555, 555 = 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 37$, the only way to combine the factors to achieve expressing it as a product of two three-digit numbers is $(3 \cdot 7 \cdot 37) (5 \cdot 11 \cdot 13)$. Regardless of this, I struggle to understand how the answer was formulated. Can someone show me the procedure?

Sorry if the question is poorly phrased, it is a rough translation of the original problem in Spanish.

• list all the divisors in order. $\sqrt{555555} \approx 745.36.$ One of your divisors must be larger than that but still smaller than 1000. The other divisor in your pair will be between 555.56 and 745.36. I guess you can find them by hand, look at all the products of two primes, then three primes. You do not need to do four primes because you already did two – Will Jagy Apr 16 '18 at 2:34
• Yeah, two primes is too small, the biggest is $13 \cdot 37 = 481.$ So, three primes each – Will Jagy Apr 16 '18 at 2:38

Nothing wrong with the approach Will gives in the comments. Here's another way. Obviously $555,555=555\times1001$, but $1001=7\times11\times13$ is a little too large. The way to make it a little smaller is to swap the factor 7 with the factor 5 in 555, which gives you your solution, $(3\times7\times37)(5\times11\times13)$.

The factors $7,11,13$ can't be used together, since $(7)(11)(13)=1001$.

So one of the groups, group $1$ say, must have exactly two of the factors $7,11,13$.

Hence the factors $3$ and $5$ can't both be in group $1$, else the product of the factors in group $1$ would be at least $(3)(5)(7)(11) > (7)(11)(13)$.

Similarly, the factor $37$ can't be in group $1$, else the product of the factors in group $1$ would be at least $(37)(7)(11) > (7)(11)(13)$.

Label the other group as group $2$.

Thus, group $2$ contains

• $37$
• Exactly one of $7,11,13$.
• At least one of $3,5$.

But since $(37)(27) = 999$, the factors in group $2$ other than $37$ must have a product which is at most $27$.

It follows that neither of the factors $11$ or $13$ is in group $2$, since $(11)(3) > 27$, and $(13)(3) > 27$.

So the factor $7$ must be in group $2$, and the factors $11,13$ must be in group $1$.

Since the factor $7$ is in group $2$, the factor $5$ can't be in group $2$, since $(7)(5) > 27$.

Hence, the factor $5$ must be in group $1$, and the factor $3$ must be group $2$.

Thus, group $2$ has the factors $37,7,3$, and group $1$ has the factors $11,13,5$.

It is intelligent brute force. The largest a three digit number can be is $999$ so you need to find a factor of $555,555$ that is between $556$ and $999$. The other will also be in that range so you are done. Next note that $3 \cdot 5 \cdot 7=105$ which is too small by itself and too large multiplied by any of the other factors, so two of $3,5,7$ have to be in one factor and one in the other. $11\cdot 13 \cdot 37 \gt 999$ so again two of those need to be in one factor and one in the other. We are down to $18$ combinations to try, three singletons from $3,5,7$ times all the one or two combinations from $11,13,37$. I missed Will Jagy's point that you need three factors in each set, so that decreases the number to try to $9$.

• I also thought that trying to solve for the same question just that for 2 factors of 2 digits and then I would split one of the digits into 2. Would this help me solve this type of question faster? Also, the question doesn't require me to state the numbers, but it does require me to state the amount of ways I can decompose it. – Brian Blumberg Apr 16 '18 at 2:44
• I don't understand the first sentence. What does it mean to split one of the digits into $2$? Having gotten down to $9$ possibilities it won't take long to try them all. You could note that $3\cdot 11\cdot 37$ is too large, so $37$ must be by itself and $11,13$ must be in the other set. Now just try each of $3,5,7$ times $11\cdot 13=143$ to see which are in range and find that only $5$ works. – Ross Millikan Apr 16 '18 at 2:53
• Yeah, never mind my question. I forgot to delete it after I realized that. Thanks. – Brian Blumberg Apr 16 '18 at 3:01

The prime factor are $3 · 5 · 7 · 11 · 13 · 37$ so there are $2^6=64$ factors and $32$ complement pairs. Just list them all but don't bother with those that are less than $555555/999=556$

Toss out, $1,3,5,7,11,13,37,3*5,3*7,3*11,3*13,3*37,3*5*7,3*5*11,3*5*13, 3*5*37,3*7*11,3*7*13$ (that's 18 that are too small).

$3*7*37=777$ and its compliment is $5*11*13=715$. (That's 1 that is acceptible)

We can continuing tossing out $3*11*13$ and $3*11*37$and $3*13*37$ are too high so we toss them. (That's 21 that are unaccptible)

$3*5*7*11$ is too high so there wonvt be any more factors that are multiples of $3$ in range. Hence no other complements which aren't multiples of $3$ will be in range either.

Of the 9 we haven'haven't considered: $3*5*7*13,3*5*7*37,3*5*11*13,3*5*11*37,3*5*13*37,3*7*11*13,3*7*11*37,3*7*13*37,3*11*13*37$ are all too big.

So that was exhaustive.

We can write $$555,555=5\times111,111$$ and notice that $111=37\times3$, so we have $$555,555=5\times37\times3003$$ and since $1001=7\times11\times13$, the prime factorization is $$555,555=3\times5\times7\times11\times13\times37.$$

If we multiply each of the three combinations $11\times13$, $11\times37$ and $13\times37$ by $3$, we see that only $3\times(13\times37)$ exceeds $1000$ which is a four-digit number.

Hence $37$ must pair with two other one-digit numbers, and $11\times13$ must pair with either $3$ or $5$ since $7\times11\times13>1000$.

If $11\times13$ pairs with $3$, then the other product must be $$37\times(5\times7)>1000$$ which is not a three-digit number.

Therefore, the only possible combination for $555,555=P_1\times P_2$ is $$P_1=5\times11\times13,\quad P_2=3\times7\times37.$$

I think the procedure might be based on Fermat method.

We can calculate that the number $555555$ can be expressed as a difference of two squares:

$746^2 - 31^2=556516-961$

Number $31$ is the distance from $746$ both ways which gives $715$ and $777$ accordingly. From here the smallest prime factor of:

$777$ is number $3$ which equals to $3\cdot259$ and for

$715$ is number $5$ which equals to $5\cdot143$

Further factorisation results in final solution where $143=11\cdot13$ and $259=7\cdot37$ therefore:

$(5\cdot11\cdot13)(3\cdot7\cdot37)$ can satisfy equation.

If $555{,}555=ab$ with $a,b\lt1000$, then we must also have $a,b\gt555$ (e.g., if $b\lt1000$, then $a=555{,}555/b\gt555{,}555/1000\gt555$). Now since $555{,}555=3\cdot5\cdot7\cdot11\cdot13\cdot37$, we may assume, without loss of generality, that $a=37k$. From $a\gt555=15\cdot37$, we see that $k\gt15$, and from $a\lt1000$, we see that $k\le\lfloor1000/37\rfloor=27$. The only product $k$ of the primes $3$, $5$, $7$, $11$, and $13$ that falls in the interval $15\lt k\le27$ is $k=3\cdot7=21$. Thus $a=37\cdot21=777$, $b=5\cdot11\cdot13=715$ is the only factorization of $555{,}555$ into two three-digit numbers.