Factor $10^n - 1$

Question

How can the prime factors of $10^n - 1$ be found?

$9 = 3^2$ is obviously a factor. If $n = p-1$, $p$ is a factor from Fermat's Little Theorem. I am stuck beyond that.

Answer 1

Step 1

3 is always a prime factor.

Step 2

We show that there are infinitely many numbers of the form $11, 111, \ldots$ which are divisible by any $x$, where $x$ is not a factor of $2$ and $5$.

Consider $S = \{11, 111, 1111, \ldots, 111111111111111\}$ (15 ones in the last one). So there are $14$ numbers in this set. Divide each one by $13$, and then the remainder modulo $13$ for each number is from $0$ to $12$. Since there are $14$ remainders (from the set S) and only $13$ possible outcomes, therefore there are $2$ numbers for which, the remainder is the same. Then the difference of these two numbers is now divisible by $13$. This difference is of the form $11111\ldots00000$ ($a$ $1’s$ and $b$ $0’s$). That means the number $1111\ldots111$ (with $a$ $1’s$) from this set is divisible by $13$.

This means there are infinitely many numbers of this form divisible by $13$. The same argument can be extended to any $x$. We cannot have $x$ multiple of $2$, $5$ because of the ending zeroes in the argument.

Step 3

From steps 1 and 2, though we have 3 has a factor of $10^n - 1$, we will not get a pattern, because for arbitrary $x$ (not multiple of 2 and 5), $x$ divides an infinitely many of the repunit numbers.

In short, there is no easy way to predict the factors

Answer 2

You will always get a factor of $9$, and if $n$ is even you will also get a factor of 11. Beyond that you are unlikely to find much of a pattern, except in special cases (such as the FLT example mentioned). Try a few examples on alpha and see.

Answer 3

We have $10^n - 1$ = $99999.....9$. This would be $9\cdot 11111...1$. The large number is called a monic repunit of $n$ digits and if $n$ is composite then let $n = ab$ for some integers $a,b$, then a monic repunit of $a$ digits multiplied by $b$ concatenate strings of $10...01$ with $a-1$ $0$'s is a factor.

For example if $n=15$ then $10^{15} - 1 = 9\cdot 111\cdot 1001001001001$ and $10^{15} - 1 = 9\cdot 11111 \cdot 10000100001$. Further than this, I'm not sure of a factorization. It seems like the factorizations of monic repunits of $p$ digits for some prime $p$ don't behave too well - for example of course $111$ is divisible by $3$, but $11$ is prime.

Answer 4

The string of 1:s (in the decimal representation) which you are left with after factoring out the 9 can be "deconvolved" with smaller strings of 1s as long as it is not of prime length.

for example: $1111 = 101 * 11$ here you can probably see how you can build all strings of even length by just padding with "01" on the first factor. But the same will be true for any multiple of a prime length, for instance "111111 = 1001 * 111" where 3 is a prime and 6 is divisible by it. Maybe the individual factors are factorable also beyond that, but at least it is a start.