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

Question

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?

Answer 1

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).

The wikipedia page is a reliable reference. https://en.wikipedia.org/wiki/Fermat_number#Primality_of_Fermat_numbers

Answer 2

The status of the fermat numbers is shown very well here : http://www.prothsearch.net/fermat.html

The numbers you are interested are very special Fermat numbers.

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$.

Such a factor cannot be verified by the usual modulo division, so we need special number-theoretical tricks. If we do not have such tricks, it is hopeless to find a factor.