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


By considering this sequence of numbers

$$2^1 + 1,\:\: 2^2 + 1,\:\: 2^4 + 1,\:\: 2^8 +1,\:\: 2^{16} +1,\:\: 2^{32}+1,\ldots$$

prove that there are infinitely many prime numbers.

I am thinking that if I can show that every pair of numbers in the sequence are relatively prime then since each has at least one prime factor this would prove the existence of infinitely many primes.

But I am new to discrete mathematics and number theory so I am not sure on how to proceed.

share|cite|improve this question

marked as duplicate by Alex M., Watson, Shahab, vrugtehagel, Claude Leibovici Mar 23 at 11:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Aren't they Fermat Numbers? Numbers of the form $$2^{2^n} +1$$ – Dhruv Mar 22 at 14:03
It is an open problem to decide if there are infinitely many Fermat primes. Evidence suggests that it may be false. – Ángel Valencia Mar 22 at 16:38
@ÁngelValencia: The OP does not ask about Fermat primes, but about prime numbers in general. – Alex M. Mar 23 at 10:09
up vote 13 down vote accepted

Your sequence is given by $a_n=2^{2^n}+1$. You can observe that

$(a_n-2)\cdot a_n=(2^{2^n}-1)(2^{2^n}+1)=(2^{2^n})^2-1=(2^{2\cdot 2^n})-1=(2^{2^{n+1}})-1=a_{n+1}-2$.

Hence if a prime number divides $a_n$ and $a_{n+1}$, then it divides $2$. But $a_n$ and $a_{n+1}$ are both odd, so they are coprime.

You could try to go further comparing $a_n$ and $a_m$ in general.

share|cite|improve this answer
+1, Thanks for your answer! – JKnecht Mar 22 at 14:23
In the book Prime Number Records ,the 1st chapter gives about 23 different proofs of the infinitude of primes. (Even a topological proof.) It says that Prof. Leo Morse said ,"It is sufficient to exhibit a strictly increasing sequence of pair-wise co-prime natural numbers, for example the Fermat numbers.".... Fermat numbers are $F(n)=1+2^{2^n}$. It is unknown if $F(n)$ is prime for any $n\geq 5$, but that is not needed in this Q. – user254665 Mar 23 at 4:37

If $2^{2^n}\equiv -1\pmod p$, then show that $2^{2^{m}}\not\equiv-1\pmod p$ for any $m<n$.

This is because if $2^{2^m}\equiv -1\pmod p$ then: $$-1\equiv 2^{2^n}=\left(2^{2^{m+1}}\right)^{2^{n-m-1}}\equiv 1\pmod p$$ So $p=2$. But $p$ can't be $2$.

So $2^{2^n}+1$ and $2^{2^m}+1$ can't have any prime factors in common if $m\neq n$.

share|cite|improve this answer
+1, Thanks for your answer! – JKnecht Mar 22 at 14:24

To continue the approach by @JérémyBlanc: Note that $a_n=2^{2^n}+1$ in general. Now, note that $$a_{n}-2=2^{2^{n}}-1=(2^{2^{n-1}}-1)(2^{2^{n-1}}+1)=a_{n-1}(2^{2^{n-1}}-1)=a_{n-1}(a_{n-1}-2)=a_{n-1}a_{n-2}(a_{n-2}-2)=\dots=a_{0}a_{1}a_{2}\dots a_{n}(a_{0}-2)=a_{0}a_{1}a_{2}\dots a_{n-1}$$

$$\therefore a_n-2=a_0a_1a_2\dots a_{n-1}$$ Equivalently, $$ 2^{2^n}-1 = (2^{2^1} - 1) \prod_{m=1}^{n-1} (2^{2^m}+1), $$

Since $a_{n}$ is odd, note that $\gcd(a_n,a_{n}-2)=1$. This implies that any divisor of $a_{n}-2$ is different from any divisor of $a_n$, thus implying for $t<n$, $\gcd(a_n, a_t)=1$.

This implies that all $a_n$ are coprime. As you have noticed, this completes our proof.

share|cite|improve this answer
+1, Thanks for your answer! – JKnecht Mar 22 at 14:22

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