Reasonable exceptions allowed on $q$. Example solution: $n=2$.


Suppose $q$ is odd. Let $p$ be so $pq\equiv -1$ (mod 8). Then $q\neq$ 2nd power (mod $p$) is the same as $\left(\frac{q}{p}\right)=-1$. We can obtain this from quadratic reciprocity law:
$$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)\equiv(-1)^{\frac{p-1}{2}\frac{q-1}{2}}=(-1)^{\frac{pq+1}{4}}(-1)^{\frac{p+q}{2}}=(-1)^{\frac{p+q}{2}}$$ where the last equality holds since $pq\equiv -1$ (mod 8) $\Rightarrow$ $\frac{pq+1}{4}\equiv 0$ (mod 2).


Then the condition $\left(\frac{q}{p}\right)=-1$ is equivalent to $\left(\frac{p}{q}\right)=-(-1)^{\frac{p+q}{2}} = -(-1)^{\frac{-q^{-1}+q}{2}}$, where the $q^{-1}$ is taken (mod 8). In particular, for any $p\equiv -(-1)^{\frac{q-q^{-1}}{2}}$ (mod $q$) and $pq\equiv -1$ (mod 8), we will have $q\neq$ 2nd power (mod $p$).




---


I was trying to repeat this argument for higher powers. I can find conditions so that, say, $n$-th residue symbol will equal to 1 (for certain $n$ anyways). However, that does not guarantee that $q$ will not be a $n$-th power (mod $p$).


Any thoughts appreciated.



Given n and q, how to find p so q$\neq$n-th power (mod p)?
This is an elaboration on Gerry Myerson's comment. By Chebotarev's (or Frobenius') density theorem, there is a positive proportion of primes for which $x^n-q$ has no linear factor (assuming $q$ is such that this is irreducible over $\mathbb{Q}).$ In fact, this proportion is not too hard to estimate, but this will lead us too far afield. So, systematic search succeeds, and usually pretty quickly (for each $p$ use Berlekamp's algorithm, or some variant thereof, to factor).


