4
$\begingroup$

A lot is known about the Fermat numbers $2^{2^k}+1$. For example, the first few $$ 2^1+1=3,\;2^2+1=5,\;2^4+1=17,\;2^8+1=257,\;2^{16}+1=65537 $$ are known to be prime, and Euler showed that the next ($2^{32}+1$) is not prime, being divisible by 641.

But what about the subset of special Fermat numbers formed by "tetration" or "power towers"? $$ 2+1 = 3\\ 2^2+1 = 5\\ 2^{2^2}+1 = 2^4+1=17\\ 2^{2^{2^2}}+1 = 2^{16}+1=65537\\ 2^{2^{2^{2^2}}}+1 = 2^{65536}+1 $$ I thought I had a vague memory of once reading that someone had conjectured that these are all prime (I guess people at one point conjectured that more generally all Fermat numbers were prime) and I also thought I had a vague memory of once reading that $2^{65536}+1$ had been proved composite.

However, I've been finding it difficult to get an answer to my question via a Google search. So, is it known whether $2^{65536}+1$ is prime or composite?

$\endgroup$
  • 2
    $\begingroup$ I would not say that "a lot is known" about Fermat numbers. As far as I know, the existence of other Fermat primes has neither been proven nor ruled out. $\endgroup$ – Sylvain JULIEN Aug 19 at 19:33
6
$\begingroup$

It's composite. It's divisible by 825753601.

Edit: It's also divisible by 188981757975021318420037633.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Factors of $2^{2^{16}}+1$ must be of the form $k\cdot2^{18}+1$. Here $k=3150$ which was found with a short computer search. $\endgroup$ – Thomas Browning Aug 19 at 19:38
  • $\begingroup$ ...And the number 825753601 is very searchable by Google. It looks like this may have been first noticed by Selfridge in 1953? In any case, thanks for your reply! $\endgroup$ – idmercer Aug 19 at 19:41
  • $\begingroup$ See also factordb.com/index.php?query=2%5E65536%2B1 $\endgroup$ – Max Alekseyev Aug 19 at 22:31
  • 2
    $\begingroup$ That 27-digit factor was found by Brent, Crandall, and Dilcher in 1997, maths-people.anu.edu.au/~brent/pd/rpb175tr.pdf $\endgroup$ – Gerry Myerson Aug 20 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.