# Can $b^4+1$ be a pseudoprime to base 2 (except for Fermat numbers)?

Cross-post: This very elementary question was first posted to Mathematics Stack Exchange but the response I got there (even after offering a bounty) was not useful.

For the purpose of this question, a pseudoprime is a composite number $n$ satisfying $2^{n-1} \equiv 1 \ (\text{mod}\,n)$, also known as a (composite) odd, weak Fermat pseudoprime to base two.

If we look at $n$ of the form $n=b^2+1$ we find many primes ($b$ in OEIS A005574) and pseudoprimes (A135590).

However, if we move to $n=b^4+1$ we still find many primes (A000068), but the only pseudoprimes we have been able to find are of the form $b=2^{2^k}$ which makes $n=b^4+1$ a Fermat number (which is obviously either prime or pseudoprime).

Question: If $b^4+1$ is composite but we still have $2^{b^4} \equiv 1 \ (\text{mod}\ b^4+1)$, will $b$ necessarily be of the form $2^{2^k}$?

If there is no obvious reason why this should be true, can someone provide some heuristics on the "expected" asymptotic behavior of such numbers $b$? A computer search seems to demonstrate that there are no examples $b \le 2\cdot 10^{10}$. Maybe there is a smarter way to locate an example?

• For comparison, there are many base 2 pseudoprimes of the form $n = b^3 + 1$, including $n = 1729$ and $n = 46657$. – Jeremy Rouse Mar 23 '16 at 17:54
• @JeremyRouse Yes, that is cool! Originally, I was mostly motivated by finding actual primes and how often a "probable prime" to base 2 would come out composite, and maybe for that reason I had not really considered $b^3+1=(b+1)(b^2-b+1)$. Now I am about to submit $12, 36, 138, 270, 546, 4800, \ldots$ to Sloane's OEIS. – Jeppe Stig Nielsen Mar 24 '16 at 0:32
• @JeremyRouse Somewhat interestingly, the $46657$ you mention is also the first pseudoprime we find with $b^2+1$ which means of course that we have a sixth power whose successor $n=6^6+1$ is a pseudoprime. If we disregard again Fermat numbers A000215, this appears to be the only case $n=b^a+1$ with exponent $a\ge 4$ one finds "immediately". – Jeppe Stig Nielsen Mar 26 '16 at 20:30

that for large $x$, the number of pseudoprimes $\leq x$ is $$\frac{x}{e^{(1+o(1))\log{x}\frac{\log{\log{\log{x}}}}{\log{\log{x}}}}}$$ If Pomerance's conjecture holds, for sufficiently large $x$ there are more than $x^{\frac{3}{4}}$ pseudoprimes $\leq x$. Now there are also about $x^{\frac{1}{4}}$ integers of the form $n^4+1$ in this range which are not Fermat numbers. Since $\frac{3}{4} + \frac{1}{4} = 1$, common heuristics suggest that for large enough $x$ there are coincidences, i.e. numbers which are both of the form $n^4+1$ (and not Fermat numbers) and pseudoprimes. Here we make the plausible assumption that the properties "$n$ is a pseudoprime" and "$n$ is of the form $b^4+1$, but not a Fermat number" are independent of one another.
The lack of examples for small numbers is easily explained by the $o(1)$ term converging to $0$ only slowly -- in fact there are only $118968378$ pseudoprimes below $x = 2^{64}$, which is just about $x^{0.419} < x^{0.75}$, cf. this table. The probability that two random subsets of $\{1, \dots, 2^{64}\}$ of cardinalities $118968378$ and $2^{16}$ intersect nontrivially is pretty low.
Exact counts of pseudoprimes up to the fourth power of your search limit $2 \cdot 10^{10}$ are not yet known, but it seems likely that $x$ must be considerably larger to push the count of pseudoprimes $\leq x$ above $x^{\frac{3}{4}}$. Thus finding an example of a pseudoprime of the desired form by means of computation may be very hard.
• This was the kind of answer I was hoping for. For comparison, with $b^2+1$, looking at the subsets of $\{1,\ldots,2^{64}\}$, this time they have sizes $118968378$ and $2^{32}$, and the intersection turns out (long search completed) to have cardinality $31$ (excluding one Fermat number, $65536^2+1$). And with $b^3+1$ (Jeremy Rouse's comment to the question) subsets of sizes $118968378$ and $2^\frac{64}{3}$ (quick search!) give an intersection of size $11$. Some statistician may tell us if this is compatible (at some level of confidence) with the idea of stochastic independence of these sets. – Jeppe Stig Nielsen Mar 26 '16 at 23:40