# MAS114: Challenge Problem 5

### Problem

Show that any two numbers of the form $$2^{2^n}+1$$ are coprime (where $$n$$ is a nonnegative integer), and thus give an alternative proof that there are infinitely many primes.

### Solution

Only Rahul Yadav solved this, and his solution went roughly as follows:

Note that $2^{2^a}-1\mid\left(2^{2^a}-1\right)\left(2^{2^a}+1\right)=2^{2^{a+1}}+1,$ and so by induction $$2^{2^a}-1\mid 2^{2^b}-1$$ whenever $$a < b$$.

But through that calculation we can also see that $$2^{2^a}+1\mid 2^{2^{a+1}}-1$$, and hence $$2^{2^a}+1\mid 2^{2^b}-1$$ whenever $$a < b$$.

That means that $2^{2^b}+1 = \left(2^{2^b}-1\right)+2 \equiv 2 \pmod{2^{2^a}-1},$ and so $\gcd(2^{2^a}+1, 2^{2^b}+1) = \gcd(2^{2^a}+1, 2) = \gcd(1, 2) = 1,$ which is what we need.

That means that, as $$n$$ increases, each new number $$2^{2^n}+1$$ is coprime to those before, and hence has a new prime factor.