Infinitude of Primes Via Powers of 2

The following statement directly implies infinitude of primes:

For a positive integer $n$ the expression $f(n)=2^{2^{n+1}}+2^{2^n}+1$ has at least $n+1$ distinct prime factors.

Proof

The proof is by induction and employs the following identity

(1)

$x^{4}+x^{2}+1=(x^2-x+1)(x^2+x+1).$

Note that, setting, $g(x)=x^{4}+x^{2}+1,$ $f(n)=g(2^{2^{n-1}}).$ The two factors of

(2)

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

are mutually prime, since each is an odd number while their difference equals $2\cdot 2^{2^{n-1}}$ and, so, the only divisors it has are the powers of $2.$

Now, $f(1)=2^{2^2}+2^{2^1}+1=21=3\cdot 7,$ a number with exactly $2=1+1$ factors.

Assuming the statement holds for an integer $k\ge 1,$ i.e., that $f(k)=2^{2^{k+1}}+2^{2^k}+1$ has at least $k+1$ distinct prime factors, observe that, according to (2),

$\begin{align} f(k+1)&=2^{2^{k+2}}+2^{2^{k+1}}+1\\ &= (2^{2^{k+1}}+2^{2^{k}}+1)(2^{2^{k+1}}-2^{2^{k}}+1)\\ &=f(k)(2^{2^{k+1}}-2^{2^{k}}+1), \end{align}$

with the second factor having divisors different from those of $f(k),$ which, by the inductive hypothesis has at least $k+1$ distinct prime divisors.

Remark

It was shown by Richard Green from the Unversity of Colorado that the above proof, although simple, can still be made more transparent.

Let's assume that the two factors in (1), $x^2-x+1$ and $x^2+x+1$ have a common prime multiple, say, $p.$ Then $p$ divides their difference $2x.$ Now note that both numbers $x^2-x+1$ and $x^2+x+1$ are odd for any integer $x.$ making $p$ also odd and, therefore, a divisor of $x$. But this can't be because $p$ then could not divide either if the two factors.

The induction then follows as before.

References

A. Engel, Problem-Solving Strategies, Springer Verlag, 1998, 121-122

Infinitude of Primes

70557295