Let $n$ be a Fermat-pseudoprime with respect to $a$. Let $p$ be a prime divisor of $n$ and let $k\in\mathbb{Z}_{>0}$. Show that if $p^k\mid n$, then $p^k\mid (a^{p-1}-1)$.
I tried showing this as follows. It holds that $2^{n-1}\equiv 1\mod n$. And since $p^k\mid n$, it will also hold that $2^{n-1}\equiv 1\mod p^k$. So this is where I get stuck, since I want to reduce the power of 2 from $n-1$ to $p-1$.
This follows from the structure of the group $G=\Bbb{Z}_{p^k}^*$. More specifically from the fact that $G$ is cyclic of order $p^{k-1}(p-1)$.
It is clear that $a$ must be coprime to $p$, so we can think of $a$ as an element of $G$. Let $m$ be the order of $a$ in this group. By Lagrange's theorem $m\mid p^{k-1}(p-1)$. On the other hand we know that $a^{n-1}\equiv1\pmod{p^k}$, so $m$ must also be a factor of $n-1$.
Getting warmer! As $p^k\mid n$, it follows that $p\nmid n-1$. Therefore also $p\nmid m$. This means that $m$ must be a factor of $p-1$, which is exactly what is required.