A structure around $n \equiv p^k \pmod q$?

Question

The following question is motivated by an answer that got deleted.

So I ask, is the following true?

Let $q$ be prime and integer $n$ be given with $2 \le n \lt q$ . Then there exist a prime factor $p$ of $n$ and an integer $k \ge 1$ such that

$\quad n \equiv p^k \pmod q$

If this is true, is there a more precise statement and/or some available links?

My work

For the number $10 = 2 \times 5 \lt 19$,

$\quad 2^{17} \equiv 10 \pmod {19}$

but

$\quad 5^{k} \equiv 10 \pmod {19}$

has no solutions.

Answer 1

If I'm reading your question right, and my calculations are correct, $q = 31$, $n = 10$ is a counterexample, since the powers of $2$ modulo $31$ are $1$, $2$, $4$, $8$, $16$, and the powers of $5$ are $1$, $5$, $25$.

Here is the code I wrote:

import sympy

for q in sympy.primerange(1,100):
    for n in range(2, q):
        for p in sympy.factorint(n):
            for k in range(q):
                if pow(p, k, q) == n:
                    print(f"If {q = } and {n = }, then {n} = {p}^{k} (mod {q})")
                    break
            else:
                continue
            break
        else:
            print(f"There is no p dividing {n} such that {n} = p^k (mod {q}).")

With the first 10 examples it finds being:

There is no p dividing 10 such that 10 = p^k (mod 31).
There is no p dividing 20 such that 20 = p^k (mod 31).
There is no p dividing 6 such that 6 = p^k (mod 41).
There is no p dividing 12 such that 12 = p^k (mod 41).
There is no p dividing 15 such that 15 = p^k (mod 41).
There is no p dividing 24 such that 24 = p^k (mod 41).
There is no p dividing 30 such that 30 = p^k (mod 41).
There is no p dividing 14 such that 14 = p^k (mod 43).
There is no p dividing 26 such that 26 = p^k (mod 43).
There is no p dividing 28 such that 28 = p^k (mod 43).