Let $p$ be a prime. Is there a classification of the numbers $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 for $p$** if $\gcd(k,p^k-1)=1$. Many numbers are good for $p=2$. This seems to be related but not identical to the OEIS sequence [A049093][1]. If $p>2$, all good numbers for $p$ are odd. Most odd numbers are good for $3$; 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.


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