7

Proving that $$(1+10^n)$$ cannot be a prime number

when $n>2$

Soham
  • 9,990
E.H.E
  • 23,280
  • Is this known? Easy if $n$ is odd. Computer found none beyond 101...searched pretty far. – lulu Sep 23 '15 at 11:46
  • If $n$ is odd, proving divisibility by $11$ is a doddle. For even $n>2$, I can't see a way right now. Testing reveals that the numbers are divisible by one of $17,29,73,101$ and then the numbers become too large for the online calculator I'm using. I can't see a clear pattern here. – Deepak Sep 23 '15 at 11:48
  • For $n-$odd it can be factored. Also if $n=l\cdot 2^k, k>0,l>1$ it can be factored. But when $n=2^k,k>0$ it seems to be prime. – Svetoslav Sep 23 '15 at 11:52
  • Fairly clear that $n$ has to be a power of $2$, but I can't rule those out. – lulu Sep 23 '15 at 11:53
  • 1
    @Svetoslav $353|10^{16}+1$ – lulu Sep 23 '15 at 11:54
  • @GudsonChou I have checked it for limited values of $n$. – E.H.E Sep 23 '15 at 11:54
  • 1
    This might have an amazingly simple solution that none of us have thought of yet (doh!) but since it's already generated quite a lot of discussion, I'm upvoting it - not often do we get such simple questions that are not so simple to crack. – Deepak Sep 23 '15 at 11:55
  • I've checked it fairly deep (8 digits). But I see no way to attack $n=2^k$. – lulu Sep 23 '15 at 11:56
  • @lulu you are right. So we only have to exclude this case somehow. – Svetoslav Sep 23 '15 at 11:56
  • @Svetoslav No, it's not this one case. $19841|10^{32}+1$ and $1265011073|10^{64}+1$. – lulu Sep 23 '15 at 11:58
  • @lulu I mean the case $n=2^k,k>0$ – Svetoslav Sep 23 '15 at 11:59
  • Oh, sorry. Agreed. But I've looked over the factors and can see no pattern (which doesn't mean there isn't one). $257|10^{128}+1$ so maybe there's a Fermat prime angle that works at least sometimes. – lulu Sep 23 '15 at 12:01
  • I think that a pruned down version of this (with the "obvious" cases excluded) is a ripe candidate for Math Overflow - but then again, I think it's now quite certain this is an open problem, so it might not be well-received. – Deepak Sep 23 '15 at 12:20
  • A prove that there are no primes $10^n+1$ with $n>2$ is probably out of reach. And it will also be very difficult to find such a prime, if it exists (See my answer below) – Peter Sep 23 '15 at 12:54
  • @Deepak the problem is actually open and probably remains open until someone finds such a prime.It is hard to imgaine that it can be proven that there is no such prime. – Peter Sep 23 '15 at 12:59
  • For the fermat numbers, the situation is similar. $65,537$ is the largest known Fermat prime, and the numbers $2^{2^k}+1$ with $5\le k \le 32$ are composite. The smallest fermat number with unknown character is $2^{2^{33}}+1$. Most mathematicians believe that there are only finite many fermat numbers, some believe that are none besides the known, but some mathematicians believe that there infinite many. – Peter Sep 23 '15 at 13:03

1 Answers1

14

The number $$10^n+1$$ can only be prime if $n$ is of the form $2^k$.

A simple proof of this fact

Suppose, $n$ has an odd prime factor $p$. Denote $q:=\frac{n}{p}$ Then $10^q+1$ is a non-trivial factor of $10^n+1=10^{qp}+1=(10^q)^p+1$ because for every number $t$ dividing $10^q+1$, we get $10^n+1=(10^q)^p+1\equiv (-1)^p+1\equiv 0\ (\ mod\ t\ )$

The generalized fermat numbers have been studied deeply. The smallest number $10^n+1$, for which it is NOT known if it is composite or prime, is

$$10^{2^{24}}+1$$

The numbers $10^{2^k}+1$ with $2\le k\le 23$ are composite.

So, a prime of the form $10^n+1$ with $n>2$ would have at least a magnitude comparable to the largest known prime. It would have at least $2^{24}+1=16,777,217$ digits!

See here :

http://www.prothsearch.net/GFN10.html

for more informations

Peter
  • 84,454