# 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
- Infinitude of Primes - A Topological Proof
- Infinitude of Primes - A Topological Proof without Topology
- Infinitude of Primes Via *-Sets
- Infinitude of Primes Via Coprime Pairs
- Infinitude of Primes Via Fermat Numbers
- Infinitude of Primes Via Harmonic Series
- Infinitude of Primes Via Lower Bounds
- Infinitude of Primes - via Fibonacci Numbers
- New Proof of Euclid's Theorem
- Infinitude Of Primes From Legendre's Formula
- Infinitude of Primes - via Bertrand's Postulate
- Infinitude of Primes - An Impossible Injection
- Infinitude of Primes - from Infinitude of Mutual Primes
- Infinitude of Primes Via Euler's Product Formula
- Infinitude of Primes Via Euler's Product Formula for Pi
- Infinitude of Primes Via Powers of 2
- Infinitude of Primes As a Quickie
- A One-Line Proof of the Infinitude of Primes
- Infinitude of Primes - A. Thue's Proof
- Why The Number of Primes Could Not Be Finite?

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

66000645