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!
Best Answer
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)$$