# Divisors of $10^{100} -1$

Determine three prime numbers that divide $10^{100} -1$.

My attempt is to use Fermat's little theorem:

$$a^{p-1} \equiv 1 \pmod{p}$$

In our case: $$a^{100} \equiv 1 \pmod{101}$$

This gives us 101 as the first prime divisor.

But how can I get more? (According to Wolfram 3, 11 and 41 are also prime divisors but how can I proof that?)

• $a^n-b^n$ factors in several ways when $n$ is composite. You have $10^{100}-1^{100}$, but also $(10^{10})^{10}- (1^{10})^10$. You can Commented Aug 24, 2016 at 17:50
• $3$ and $11$ should be pretty clear, consider $10 \mod 3$ and $10 \mod 11$. Commented Aug 24, 2016 at 17:51
• $3$ is somewhat straight forward. $10^{100}$ minus one is a bunch of nines. Commented Aug 24, 2016 at 18:08
• – lhf
Commented Dec 9, 2021 at 0:30

Try 3 and 11 by using divisibility criteria. Note that $10^{100}-1$ is a sequence of 100 digits all equal to $9$.

$3$ is obviously the second prime.

And $11$ is the third, which you can easily prove by induction for $10^{2n}-1$:

• Base case: $10^2-1=99$ is divisible by $11$
• Inductive step: $10^{2(n+1)}-1=101\cdot(10^{2n}-1)$

You have to find prime numbers $p$ such that $p-1$ is a divisor of $100$ – or a divisor $d$ of $100$ such that $d+1$ is prime, and that do not divide $10$. The list of divisors of $100$ is $$\begin{matrix}1&5&25\\2&10&50\\4&20&100\end{matrix}$$ So you obtain $\;\{3,11,101\}$.

Let us examine 41. We will show that 41 | 10^100 -1. First we consider the 5th power. 10^5 = 2439 * 41 + 1 so that 41 | 10^5 -1 and further 10^5 -1 | (10^5)^20 - 1 = 10^100 - 1

• And what made you think of $41$, of all the numbers? Explaining this might help the OP solve this type of problems in the future. As it is, this answer relies on a lot of "magic". Commented Jan 2, 2017 at 15:10