Prove that any two numbers of the form $2^{2^n}+1$ are coprime to one another.

Question

Full problem statement:

Prove that any two numbers of the follwing sequence are relatively prime:

$2 + 1, 2^2+1, 2^4 + 1, 2^8+1, ... 2^{2^n} + 1 $

So far I have tried to use Euclid's algorithm with mathematical induction. I have also proved that 3 is coprime to any number in the sequence, and have tried to use induction (using n = 0, i.e. 3, as the base case, and showing that the same property must be true for 5, 17, etc.)

Answer 1

Hint: Suppose that $m\lt n$. Then $2^{2^m}+1$ divides $2^{2^n}-1$. For let $x=2^{2^m}$. Then $2^{2^n}-1=x^{2^k}-1$, where $k=n-m$.

Remark: This result gives a nice proof that there are infinitely many primes. Let $F_n=2^{2^n}+1$, and let $q_n$ be the smallest prime divisor of $F_n$. Then by the result of the OP, all the $q_n$ are distinct.

Answer 2

Hint $\rm\,\ \ \ \ \gcd(c+1,\ c^{2k}\!+1)\ =\ gcd(c+1,\:2),\ $ using $\rm\,\ gcd(a,b) = gcd(a, b\ mod\ a)$

Proof $\rm\ \, mod\,\ c+1\!:\,\ \color{#c00}{c\equiv -1}\ \Rightarrow\ \color{#c00}c^{2k}\!+1\: \equiv\ (\color{#c00}{-1})^{2k}\!+1\:\equiv\ 2\ \ $ QED

For $\rm\ c=2^{\Large 2^{A}} $ we have $\rm\ c^{\Large 2k} = 2^{\large 2^{B}}\ $ for $\rm\ 2k\, =\, 2^{\,B-A},\ $ so the above yields

$\rm\qquad\ gcd(2^{\Large 2^{A}}\!+1,\, 2^{\Large 2^{B}}\!+1)\ =\ gcd(2^{\Large 2^{A}}\!+1,2) \,=\, 1\ $ for $\rm\ B > A$

Answer 3

Hint.

1. Define a sequence $F_n$ recursively by $F_n=F_0F_1\cdots F_{n-1}+2$ and $F_0=3$.

2. Prove by induction that $F_n$ is odd.

3. Conclude that the numbers $F_n$ are pairwise relatively prime.

4. Prove by induction that $F_n=2^{2^n}+1$. Spoiler:

Assuming $F_n=2^{2^n}+1$, then

$F_{n+1}=(F_0F_1\cdots F_{n-1})F_n+2$

$=(F_n-2)F_n+2$

=$(2^{2^n}-1)(2^{2^n}+1)+2$

=$(2^{2^n})^2-1+2$

$=2^{2^{n+1}}+1$.