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$.
 A: \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}
A: 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.
A: 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$.
