8
$\begingroup$

Is $10^n+1$ composite for all $n\in \mathbb{N}$ greater then $2$?

I tried many values of $n$, and $10^n+1$ is composite each time (excpet $n=1,2$).

Is my conjecture correct? Thank you.

  • 5
    According to [this](http://en.wikipedia.org/wiki/List_of_prime_numbers#Generalized_Fermat_primes_base_10) it is an open question.2012-12-15
  • 0
    101 appears to always divide the result when $n \equiv 2(\mod 4)$2012-12-15
  • 0
    @orlandpm: Yes, because $10^{4n+2}=100^{2n+1}\equiv (-1)^{2n+1}\pmod{101}\equiv -1\pmod{101}$.2012-12-15
  • 1
    For odd values of $n$, $11|10^n+1$.2012-12-15

1 Answers 1

8

If $n = 2^l m$ where m is odd, then $$\displaystyle (10^{2^l})^m + 1 \equiv 0 \bmod (10^{2^l} + 1)$$.

So the interesting question is if $10^n + 1$ is composite when $n$ is a power of $2$.

Unfortunately I don't know what happens when $n$ is a power of $2$.

  • 1
    Heuristically [they are probably all composite](http://en.wikipedia.org/wiki/Fermat_number#Heuristic_arguments_for_density). WolframAlpha can verify them all up to $10^{2048}+1$.2012-12-15
  • 0
    The proof given in the link can be adapted to $10^{2^n}$ case too. So you are right. However I cant seem to understand in what sense it is a good heuristic... Thanks for that link :)2012-12-15
  • 1
    The heuristic is the [prime number theorem](http://en.wikipedia.org/wiki/Prime_number_theorem) which basically says that the probability that $n$ is prime is $\frac{1}{\log{n}}$. So when $n=10^{2^x}+1$ and we sum over all $x \gt 11$ this series converges.2012-12-15
  • 0
    Note that this is the exact analogue of the question of when $2^n+1$ is prime: then also $n$ must itself be a power of two, leading to the "Fermat primes".2012-12-15
  • 0
    @DanBrumleve: the fact that the series converges predicts that there are only finitely many such primes. The fact that the series (starting at x=11) is very small suggests that there are none.2012-12-15