When is $\mathrm{gcd}(k,p^k-1)=1$ true?

Question

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. 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 have found an equational proof that $p^k$-rings with $p=0$ are commutative when $\gcd(k,p^k-1)=1$ (see Equational proofs of Jacobson's Theorem). Now, I wonder how many cases I have already covered.

Answer 1

It is easier to describe non-good (bad) numbers with respect to a given prime $p$. For each such number $k$, there exists a prime $q$ such that $q\mid k$ and $q\mid (p^k - 1)$. It follows that $k$ is multiple of $m_p(q):=q\cdot \mathrm{ord}_q(p)$, where $\mathrm{ord}_q(p)$ is the multiplicative order of $p$ modulo $q$ (which is a divisor of $q-1$). Hence, the set of bad $k$ is formed by the union $$\bigcup_{q\in\mathbb{P}\atop q\ne p} m_p(q) \mathbb{N}^+.$$

UPDATE#2. It also follows that

• for any odd $k$, there exists a prime $p$ such that $k$ is good for $p$;

• any even $k$ is bad for all primes $p\geq 3$ since $2\mid \gcd(k,p^k-1)$;