Let $p$ be a prime. Is there a classification of the $k \geq 1$ such that $\gcd(k,p^k-1)=1$? If not, can we at least produce an explicit infinite subset? What is known about these $k$?

For the lack of a better name, let me call $k$ good if $\gcd(k,p^k-1)=1$. For $p=2$ many numbers are good. This seems to be related but not identical to the OEIS sequence [A049093][1]. For $p > 2$ all good numbers are odd. For $p=3$ most odd numbers are good; for $k \leq 1000$ the only $24$ exceptions are `39, 55, 117, 165, 195, 253, 273, 275, 351, 385, 429, 495, 507, 585, 605, 663, 715, 741, 759, 819, 825, 897, 935, 975`. There is no OEIS sequence for these. For $p=5$ it is similar, but for $p > 5$ the story becomes different.

*Background.* I can prove a certain theorem in abstract algebra for all pairs $(p,k)$ with $\gcd(k,p^k-1)=1$. Now, I wonder how many cases I have already covered. I am not a number theorist, so I apologize if this question turns out to be stupid.


  [1]: https://oeis.org/A049093