# Are there infinitely many primes and non primes of the form $10^n+1$?

Prove that there are infinitely many primes and non-primes in the numbers $10^n+1$, where $n$ is a natural number. So numbers are 101, 1001, 10001 etc.

-
People will be more inclined to help you if you ask politely, instead of telling them to do something. Also, is this homework? If so, you should add the homework tag to this question. –  Zev Chonoles Apr 24 '11 at 16:45
@Zev: Since OP just joined today, let us cut them some slack and give them some time to read the FAQ etc. (btw, I did +1 your comment :-)) –  Aryabhata Apr 24 '11 at 17:06
Thanks the protip! :) Also, this isn't a homework, just need to be sure my codegolf problem is appropriate. –  a very random man Apr 24 '11 at 17:23

I am not so sure this is homework.

One part is easy: If $\displaystyle n$ is odd (or divisible by an odd number $\displaystyle \gt 1$), then $\displaystyle 1+10^n$ is composite, using the fact that $\displaystyle x^{2n+1} + y^{2n+1}$ is divisible by $\displaystyle x+y$.

For $\displaystyle 1 + 10^n$ to be prime, $\displaystyle n$ must be a power of a $\displaystyle 2$, which makes it similar to Fermat numbers, and the question of whether there are an infinite number of Fermat primes is open. I believe the current 'expectation' based on heuristic arguments is that there are only finite number of such primes.

I would guess this would be the case with $\displaystyle 1 + 10^{2^m}$ too.

-

I also doubt this is homework.

Notice that if $n$ has an odd prime factor, then we can factor $10^n+1$ as we can factor $x^n+y^n$. Therefore $10^n+1$ must be composite except when $n=2^m$ for some $m$. The sequence $$f(n)=a^{2^n}+1$$ is a generalization of the Fermat numbers, and while we can show that each element is relatively prime since they have a similar multiplicative property, namely $$f(n)-2=a^{2^n}-1=f(n-1)f(n-2)\cdots f(1)f(0)(a-1).$$ It is unknown if there are infinitely many primes for any integer $a>1$. Note that if $a$ is odd, the sequence has pairwise $\gcd$ $2$ rather than $1$.

Also, the problem of finding the next prime of the form $10^n+1$ after the first three, $2$, $11$ and $101$ is discussed on the following physics forum. In short, their numerical calculations did not find another, and they took $n$ quite large.

-