Find the prime-power decomposition of 999999999999

Question

I'm working on an elementary number theory book for fun and I have come across the following problem:

Find the prime-power decomposition of 999,999,999,999 (Note that $101 \mid 1000001$.).

Other than just mindlessly guessing primes that divide it, how should I go about finding the solution? I am curious as to how this hint about 101 dividing 1000001 helps. There is also a factor table for integers less than 10,000 in the back of the book, so really the objective is to get 999,999,999,999 down to a product of numbers with less than 5 digits, then I can just use the table.

Thank you!

Answer 1

Hint:

$$999,999·1,000,001 = 999,999,999,999$$

$$999·1,001 = 999,999$$

You can figure out the rest ;D

Answer 2

With $1000001=101\cdot 9901$ and $999999=3^3\cdot 7 \cdot 11 \cdot 13 \cdot 37$ we obtain all prime factors of $999999999999=999999\cdot 1000001$.

Answer 3

For starters, it's $999,999\times1,000,001$, so if you can factor each of those, you're done.

Obviously $999,999=3\times3\times111,111$, and that last is obviously divisible by $3$, getting $999,999=3\times3\times3\times37,037$. Then you've obviously got divisibility by $37$, so $999,999=3\times3\times3\times37\times1001$. Factoring $1001$ isn't hard since if you start checking small prime factors you see it's divisbly by $7$, so $1001=7\times143$, and $143=11\times13$.

Now deal with $1,000,001$. Since you're handed the fact that it's divisible by $101$, you've got $1,000,001=101\times 9901$. If I'm not mistaken, $9901$ is prime, but I don't know how to show that except by brute force: divide by every prime number $\le \sqrt{9901}\approx99.5$.

Answer 4

As it was pointed in a commment $$999,999,999,999=10^{12}-1$$

Now, using difference of squares, we have $$10^{12}-1=(10^6-1)(10^6+1)=(10^3-1)(10^3+1)(10^6+1)$$

By sum/difference of cubes we have $$10^{12}-1=(10-1)(10^2+10+1)(10+1)(10^2-10+1)(10^2+1)(10^4-10^2+1)\\ =9 \cdot 111 \cdot 11\cdot 91 \cdot 101 \cdot 9901$$

Each of those numbers is easy to factor now.

P.S.

You can factor further $91$: $$91=100-9=10^2-3^2=(10-3)(10+3)$$