Is there a prime power $p^k$ with $k$ $>$ $2$ such that it is a Fermat Pseudoprime?

Question

Does there exist a prime power $p^k$ with $k$ $>$ $2$ which is a Fermat Pseudoprime to bases $2$, $3$, $5$, or $7$? $5^2$ $=$ $25$ is a base $7$ Fermat pseudoprime is an example of a square of a prime being a pseudoprime to one of the first $4$ prime bases. No examples with $p^3$ or higher are known. Can someone please think of a few? Thanks.

Answer 1

Assume $a^{p^k-1}\equiv 1\pmod{p^k}$.

So the order of $a$ must divide $p^{k}-1$ and $\phi(p^k)=p^{k}-p^{k-1}=(p-1)p^{k-1}$. Thus the order of $a$ must divide $p-1$ since it can't have any factor of $p$.

So you need: $$a^{p-1}\equiv 1\pmod{p^k}$$

Let $g$ be a generator modulo $p^k$, we can pick $a$ to be $g^{i p^{k-1}}$ for any $b$.

For example, for $p=5,k=3$ you can choose $g=2$ then $a=2^{25}=57$ and $57^{124}- 1$ is divisible by $125$.

(For $p=3$ you always get $a=p^k-1$ which is a trivial case.)

Now, whether you can find examples of small $a$ is unclear...