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.