Cross-post: This very elementary question [was first posted](https://math.stackexchange.com/questions/1687641/) 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](https://oeis.org/A005574)) and pseudoprimes ([A135590](https://oeis.org/A135590)).


However, if we move to $n=b^4+1$ we still find many primes ([A000068](https://oeis.org/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?


Or maybe this has been asked/answered before in the literature?



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


[On the Distribution of Pseudoprimes](http://www.ams.org/journals/mcom/1981-37-156/S0025-5718-1981-0628717-0/S0025-5718-1981-0628717-0.pdf), Math. Comput. 37, 587-593 (1981)


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](http://www.janfeitsma.nl/math/psp2/statistics).
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.


