Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 12 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|cite|improve this answer

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|cite|improve this answer

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.