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.
Prime Numbers – How to Factor 10^n – 1
prime factorizationprime numbers
prime factorizationprime numbers
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.
Best Answer
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