Use this sequence to prove that there are infinitely many prime numbers. [duplicate]

Solution 1:

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.

Solution 2:

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$.

Solution 3:

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.