Carmichael numbers with smallest strong pseudoprime base 8

Question

Recently I analyzed the OEIS extended table of the first $10000$ Carmichael numbers.

As Wikipedia writes: Carmichael numbers may be strong pseudoprimes to some bases - for example, 561 is a strong pseudoprime to base 50 — but not to all bases.

For the listed Carmichael numbers I computed their prime factorizations, the smallest base for which they are strong pseudoprimes and the smallest base for which they are no strong pseudoprimes. Here is a frequency table for the smallest strong pseudoprime bases:

Base 2:   369
Base 3:   555
Base 4:   246
Base 5:   208
Base 6:   151
Base 7:   109
Base 8:     0
Base 9:  1125

Eye-catching is the zero result for base 8. Question:

Is there any proof or conjecture, that the smallest strong pseudoprime base for a Carmichael number cannot be $8?\;$ If not what is known about the smallest Carmichael number with this property?

Note: There are Carmichael numbers which are strong pseudoprimes for base $8$, the smallest is $15841.$

Answer 1

It is fairly straightforward to prove. Recall the definition of strong pseudoprime: A strong pseudoprime to the base $a$ is an odd composite $n=2^rs+1$ with $s$ odd such that either $a^s\equiv 1 \bmod n$, or $a^{2^ts}\equiv -1$ for some integer $t$, with $r>t\ge 0$.

Let us assume that $n$ is a Carmichael number which is a strong pseudoprime to the base $8$. We will show that the Carmichael number is also a strong pseudoprime to the base $2$.

One way that could happen is if $8^s\equiv 1$, which means that $2^{3s}\equiv 1$. But since $n$ is a Carmichael number, we also know that $2^{2^rs}\equiv 1$. Therefore, the order of $2$ divides $3s$ and also divides $2^rs$, therefore it divides $\operatorname{gcd}(3s,2^rs)=s$. So $2^s\equiv 1$.

Alternatively, we may have $8^{2^ts}\equiv -1$, which means that $2^{2^t3s}\equiv -1$. This means that $(2^{2^ts})^6\equiv 1$. We also have that $(2^{2^ts})^{2^{r-t}}\equiv 1$, meaning that the order of $2^{2^ts}$ must divide $\operatorname{gcd}(6,2^{r-t})=2$. This is true for each prime $p|n$. So for each prime we have $2^{2^ts}\equiv\pm 1$. We can rule out the $+1$ case since we know $(2^{2^ts})^3\equiv -1$.Therefore $2^{2^ts}\equiv -1$ mod all $p$, thus mod $n$, thus $n$ is a strong pseudoprime to the base $2$.