11
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ $$999999999999=\frac{10^{12}-1}9$$ Now, if $n|m,(a^n-1)|(a^m-1)$ $\endgroup$ – lab bhattacharjee Aug 16 '14 at 18:19
7
$\begingroup$

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)$$

$\endgroup$
3
$\begingroup$

Hint:

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

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

You can figure out the rest ;D

$\endgroup$
  • $\begingroup$ Thank you, but how do you know this? Is there something obvious that I'm missing? $\endgroup$ – candido Aug 16 '14 at 18:09
  • $\begingroup$ And $1000001=101\cdot 9901$. $\endgroup$ – Dietrich Burde Aug 16 '14 at 18:09
  • $\begingroup$ Yes: $1,000,001 = 1,000,000 + 1$ so $999,999·1,000001 = 999,999,000,000 + 999,999$ wich "fit" preciselly into $999,999,999,999$ $\endgroup$ – Darth Geek Aug 16 '14 at 18:11
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.