Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
1  
@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
2  
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
add comment

2 Answers

up vote 10 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.