# How does one prove that $(2\uparrow\uparrow16)+1$ is composite?

Just to be clear, close observation will show that this is not the Fermat numbers.

I was reading some things (link) when I came across the footnote on page 21, which states the following:

$$F_1=2+1\to prime$$

$$F_2=2^2+1\to prime$$

$$F_3=2^{2^2}+1\to prime$$

$$F_4=2^{2^{2^{2}}}+1\to ?$$

And so on. Amazingly, it has been found that $F_1$ through $F_{15}$ to be prime, but, at $F_{16}$, the answer is no longer prime (proven?).

In knuth arrow notation:

$$F_{16}=(2\uparrow\uparrow16)+1\to composite$$

But how do you prove this? $F_{16}$ is so large, that I cannot proceed to manually attempt at factoring it, and, most likely, many of its factors will have hundreds (or more) digits!

Interestingly, people have pointed out that there are only $5$ known Fermat numbers are prime, and so, I have come to a different conclusion.

Numbers such as $F_{15}$ or $F_{14}$ are unknown as to whether they are prime or composite. However, it has been proven, somehow, that $F_{16}$ is composite.

But how?

#### Solutions Collecting From Web of "How does one prove that $(2\uparrow\uparrow16)+1$ is composite?"

The number $N = 2^k + 1$ is composite when $k$ has an odd factor $p$, since then $2^p + 1$ will divide $N$.

The converse is false. The first five possibilities, corresponding to $k = 1, 2, 4, 8, 16$ are prime. Euler showed the next one isn’t. No more primes of this form have been found. Some of the next ones have been proved to be composite (but not necessarily factored).

A prime factor of $2^{2^n}+1$ must have the form $k\cdot 2^{n+2}+1$.
It is open whether there are finite or infinite many Fermat primes, the smallest $n$, for which the character of $2^{2^n}+1$ is unknown, is $33$.
To prove that the number $(2\uparrow\uparrow 16)+1$ is composite, you have to find a prime factor (Primilaty check is out of reach with the known prime checking methods), but this factor must have the form $k\cdot 2^{(2\uparrow\uparrow 14)+2}+1$ , so it must be greater than $2\uparrow\uparrow 15$.