I want to show that for any integers $a$ and $n,$ ($n > 1$) there are infinitely many primes $p$ such that $$x^n \equiv a \text{ (mod } p).$$
When $n$ is odd, I used the fact that if $(a,p)=1$ and if $a^{\frac{p-1}{(n,p-1)}} \equiv 1 \text{ (mod } p), $ then $x^n \equiv a \text{ (mod } p)$ has $(n,p-1)$ solutions. Then Dirichlet's theorem on Arithmetic Progressions , there are infinitely many primes $p \equiv 2 \text{ (mod } n)$ and hence $(n,p-1) = 1.$
How do I complete the case when $n$ is odd?
P.S.: This problems also appears as problem #3 on Chapter 5, page 342 of Borevich-Shafarevich's Number Theory book.
The proof is analogous to Euclid's proof that there are infinitely many primes. We do not need Dirichlet's theorem.
Let $M$ be the set of primes $p$ such that there exists an integer $x$ with $x^n\equiv a \bmod p$. Let $P(x)=x^n-a$. Then we can write the congruence as $P(x)\equiv 0 \bmod p$. Suppose that $M$ is finite, i.e., $M=\{ p_1,\ldots ,p_k\}$. For each integer $m$, $P(mp_1p_2\cdots p_k)$ is an integer with no prime factors, which must equal then $1$ or $-1$. However, since $P$ has degree $n\geq 2$, it takes each of the values 1 and -1 at most $n$ times, a contradiction.