# Factor $10^6-1$ completely

I know kind of a very elementary method to factor this number. Consider the following: $$10^6-1 = (10^3-1)(10^3+1)=9 \times 11 \times (10^2+10+1)(10^2-10+1) = 9 \times 11 \times 111\times 91$$ I would then factor each number individually.

Is there a faster method? The great hint is that this number is a rep unit number = $$9\ \times 111111$$.

• In the last line it is $9$ times a rep unit number and you are one $1$ short. – Ross Millikan Oct 12 '18 at 15:19
• @RossMillikan what do you mean? do you mean that $10^6 -1$ is not 11111? – Maged Saeed Oct 12 '18 at 15:22
• You can get to the last step easier if you rewrite it as $10^6-1=999.999= 9\cdot 111.111=9\cdot 11 \cdot 10.101$ – Zacky Oct 12 '18 at 15:22
• @RossMillikan just updated it. – Maged Saeed Oct 12 '18 at 15:23
• It is $999,999$, not $111,111$ – Ross Millikan Oct 12 '18 at 15:31

You have gotten as far as the difference of sixth powers will take you. Now $$111$$ is divisible by $$3$$ by the sum of digits test, you know $$9=3^2,$$ and you are down to $$3^3\cdot 11 \cdot 37 \cdot 91$$. I don't see anything better than trial division at this point. For $$37$$ you only need to go up to $$5$$ to see it is prime. For $$91$$ you need to go to $$7,$$ you find $$91=7\cdot 13$$ and you are done. Maybe you know the last two off the top of your head.
\begin{align} 10^6 - 1 &= 1000000-1\\ &= 999999 \\ &= 3^2 \times 111111 \\ &= 3^2 \times 111\times 1001 \\ &= 3^2 \times 111 \times (1100 - 99)\\ &= 3^2 \times 111 \times 11 \times (100-9)\\ &= 3^2 \times 111 \times 11 \times 91 \\ &= 3^2 \times (3 \times 37)\times 11 \times 7 \times 13 \end{align}
If you have a computer, you could use this idea for an algorithm to factor:$$10^n -1 \equiv 0 \mod p \iff 10^n \equiv 1 \mod p$$ This will be more feasible for large values of $$n$$ because most programming languages have an efficient modular exponentiation function that already exists. If a prime $$p$$ satisfies this equivalence, it's a prime factor, though you will have to run additional trials to find the degree of $$p$$.