3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ $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 $\endgroup$
    – B. Goddard
    Commented Aug 24, 2016 at 17:50
  • 2
    $\begingroup$ $3$ and $11$ should be pretty clear, consider $10 \mod 3$ and $10 \mod 11$. $\endgroup$
    – Michael Biro
    Commented Aug 24, 2016 at 17:51
  • 3
    $\begingroup$ $3$ is somewhat straight forward. $10^{100}$ minus one is a bunch of nines. $\endgroup$
    – Piotr Benedysiuk
    Commented Aug 24, 2016 at 18:08
  • $\begingroup$ See also math.stackexchange.com/a/3685873/589 $\endgroup$
    – lhf
    Commented Dec 9, 2021 at 0:30

4 Answers 4

Reset to default
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

$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)$
$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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". $\endgroup$
    – Alex M.
    Commented Jan 2, 2017 at 15:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .