Return to Answer

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. It also follows that $k$'s bad for all primes $p$ form the set $$\bigcup_{q\in\mathbb{P}\atop q\geq 3} q(q-1) \mathbb{N}^+.$$

Correspondingly, the density of $k$'s that are good for at least one prime equal $$\prod_{q\in\mathbb{P}\atop q\geq 3} \left(1-\frac1{q(q-1)}\right)\approx 0.7479.$$ Such $k$'s can be described as those that are not divisible by $q-1$ for every odd prime $q\mid k$.

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)$;

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{Z}.$$

UPDATE. It also follows that $k$'s bad for all primes $p$ form the set $$\bigcup_{q\in\mathbb{P}\atop q\geq 3} q(q-1)\mathbb{Z}.$$

Correspondingly, the density of $k$'s that are good for at least one prime equal $$\prod_{q\in\mathbb{P}\atop q\geq 3} \left(1-\frac1{q(q-1)}\right)\approx 0.7479.$$ Such $k$'s can be described as those that are not divisible by $q-1$ for every odd prime $q\mid k$.

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. It also follows that $k$'s bad for all primes $p$ form the set $$\bigcup_{q\in\mathbb{P}\atop q\geq 3} q(q-1) \mathbb{N}^+.$$

Correspondingly, the density of $k$'s that are good for at least one prime equal $$\prod_{q\in\mathbb{P}\atop q\geq 3} \left(1-\frac1{q(q-1)}\right)\approx 0.7479.$$ Such $k$'s can be described as those that are not divisible by $q-1$ for every odd prime $q\mid k$.

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{Z}.$$

UPDATE. It also follows that $k$'s bad for all primes $p$ form the set $$\bigcup_{q\in\mathbb{P}\atop q\geq 3} q(q-1)\mathbb{Z}.$$

Correspondingly, the density of $k$'s that are good for all primes equal $$\prod_{q\in\mathbb{P}\atop q\geq 3} \left(1-\frac1{q(q-1)}\right)\approx 0.7479.$$ Such $k$'s can be described as those that are not divisible by $q-1$ for every odd prime $q\mid k$.

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{Z}.$$

UPDATE. It also follows that $k$'s bad for all primes $p$ form the set $$\bigcup_{q\in\mathbb{P}\atop q\geq 3} q(q-1)\mathbb{Z}.$$

Correspondingly, the density of $k$'s that are good for at least one prime equal $$\prod_{q\in\mathbb{P}\atop q\geq 3} \left(1-\frac1{q(q-1)}\right)\approx 0.7479.$$ Such $k$'s can be described as those that are not divisible by $q-1$ for every odd prime $q\mid k$.