Divisors of $10^{100} -1$

Question

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?)

Answer 1

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

Answer 2

$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)$

Answer 3

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

Answer 4

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