Suppose, $N$ is a composite Fermat-pseudoprime to base $a$ :
$$a^{N-1}\equiv 1\ (\ mod \ N)$$
If $N$ is NOT strong Fermat-pseudoprime to base $a$, a non-trivial factor of $N$ can be found efficiently. So, lets assume $N$ is strong Fermat-pseudoprime to base $a$.
Is there always a number $b$, such that $b^{N-1}\equiv 1 \ (\ mod\ N)$ holds, but $N$ is NOT strong Fermat-pseudoprime to base $b$ ? If such a base can be found, a non-trivial factor of $N$ can be found efficiently.
If $N$ is a Carmichael-number, the answer is yes because every $b$ with $(b,N)=1$, such that $N$ is NOT strong Fermat-pseudoprime to base $b$ does the job.