For fixed positive integers $a$ and $k$, prove that there are infinitely many primes $p$ for which $p\equiv 1\pmod{k}$ and $a$ is a $k$th power modulo $p$.
I know that this problem could be solved by considering the $k$'th cyclotomic polynomial, but I don't know how.
On
I've found an elementary solution after all.
Rephrasing the question in terms of polynomials, it asks to prove that $\Phi_k(n)$ and $n^k-a$ share infinitely many prime divisors.
There is actually a theorem of Nagell that is a generalization of this:
Theorem. (Nagell) Let $f_1,...,f_n\in\mathbb{Z}[X]$ nonconstant. Prove that there are infinitely many primes $p$ for which each $f_i$ has a root $\bmod p$.
Proof: The idea is to reduce the problem to the well-known Schur theorem, which is precisely this theorem for $n=1$.
As such, we will be looking for polynomials $g_1,...,g_n\in\mathbb{Q}[X]$ for which $f(g_i(X))$ all share some nonconstant divisor. For this, let's fix $x_1,...,x_n\in\mathbb{C}$ some roots of $f_1,...,f_n$ and we search for some polynomials $g_i\in\mathbb{Q}[X]$ and $z\in\mathbb{C}$ s.t. $g_i(z)=x_i$, $\forall i\in\overline{1,n}$$\qquad (1)$.
Employing the primitive element theorem, notice that $x_i$ are all algebraic over $\mathbb{Q}$ thus there is an algebraic number $z$ for which $\mathbb{Q}(x_1,...,x_n)=\mathbb{Q}(z)$, hence there exist polynomials $g_i$ that are satisfying (1). We can make $z$ into an algebraic integer by just multiplying it by a suitable integer.
Now, we need to resolve some integer issues. Firstly, take $N\in\mathbb{N^*}$ for which $h_i=Ng_i\in\mathbb{Z}[X]$ and $d$ large enough such that $F_i(X)=N^df_i\left(\frac{h_i(X)}{N}\right)\in\mathbb{Z}[X]$.
The final step is to consider $P$ the minimal polynomial of $z$ in $\mathbb{Z}[X]$. As $z$ is an algebraic integer, $P$ is monic. By Gauss's lemma, $F_i$'s are divisible by $P$ in $\mathbb{Z}[X]$. Now we can just use Schur's theorem to find infinitely many prime divisors for $P$, and the theorem is proved. $\square$
Edit: I found a much simpler proof. I’ll let the old one stay at the end of the post, but this one is much better.
As in the old proof, let $K$ be the splitting field of the polynomial $x^k-a$, let $\alpha$ be a primitive element that is integral over $\mathbb{Z}$ and $f$ be its (monic) minimal polynomial.
$K$ contains a primitive $k$-th root of unity so there are rational polynomials $A,B$ such that $\Phi_{k}(A(x))=B(x)f(x)$. $K$ contains a $k$-th root of $a$ so there are rational polynomials $C,D$ such that $C(x)^k-a=f(x)D(x)$.
Let $p$ be a large enough prime number such that the coefficients of $A,B,C,D$ are $p$-integers (ie they have a nonnegative $p$-adic valuation). Assume that there exists some integer $n$ such that $p|f(n)$. Then $p$ divides $\Phi_{k}(b)$ where $b$ is the reduction in $\mathbb{F}_p$ of $A(n)$, and $p$ divides $d^k-a$ where $d$ is the reduction in $\mathbb{F}_p$ of $C(n)$.
As in the old answer, we can conclude that $b$ has order $k$ mod $p$ (because $k \in (\Phi_k(x),\prod_{d|k}{\Phi_d(x)}) \supset (x^k-1,(x^k-1)’)$) and that $d$ is a $k$-th root of $a$ mod $p$.
Old answer: Right… this proof may be a little more sophisticated than what you may be comfortable with. It uses some nontrivial abstract algebra and algebraic number theory. Maybe there’s a simpler argument (did the article imply that there was an elementary proof?) – but I can believe otherwise too.
Let $K$ be the splitting field of the polynomial $x^k-a$, $d$ its degree, $D$ its absolute discriminant, $R$ its ring of integers, $\alpha \in R$ a primitive element with minimal (monic) polynomial $f$, $R_1=\mathbb{Z}[\alpha]$, then let $p$ be a prime number coprime to $NDk$, where $N$ is the cardinality of the finite group $R/R_1$.
There are polynomials $g,h$ of degree at most $d-1$ with integer coefficients such that $g(\alpha)$ is $N$ times a $k$-th root of $a$, and $h(\alpha)$ is $N$ times a primitive $k$-th root of unity.
We claim that if $p$ divides $f(n)$ for some integer $n$, then $p$ works, and this concludes.
Indeed, if $\alpha-n$ is coprime to $p$ in $R$, then it is not in any prime ideal of $R$ above $p$, and thus neither are its Galois conjugates (the $\beta-n$ where $\beta$ is any root of $f$), and thus $f(n)=\prod_{\beta}{(\beta-n)}$ is in no prime ideal above $p$ so cannot be divisible by $p$.
Let $q \subset R$ be some prime ideal above $p$ such that $\alpha-n \in q$. We can see directly that $R_1/(R_1 \cap q) \rightarrow R/q$ is a bijection (it’s clearly injective, and the range has characteristic $p$ but its cokernel has a cardinality dividing $|R/R_1|=N$), and $R_1=\mathbb{Z}[\alpha]$ with $\alpha-n \in q$, $q \cap \mathbb{Z}=p\mathbb{Z}$, so that $R_1/(q \cap R_1)=\mathbb{F}_p$.
Thus $g(n)$ is in $\mathbb{Z}$ and is congruent mod $q \cap R_1$ to $g(\alpha)$, so $g(n)^k$ is congruent to $N^ka$ mod $q \cap R_1 \cap \mathbb{Z}=p\mathbb{Z}$.
Finally, $y=h(n)$ is congruent mod $q \cap R_1$ to $h(\alpha)$, which is a root of $\Phi_{k,N}:=N^{\varphi(k)}\Phi_k(X/N)$, so $\Phi_{k,N}(h(n))$ is congruent mod $q \cap R_1 \cap \mathbb{Z}=p\mathbb{Z}$ to $0$.
Now, it is not hard to see that $n \in (x^n-1,(x^n-1)’)$, and thus that $n \in (\Phi_n,\prod{l|n, l<n}{\Phi_l})$, and thus $kN^{\varphi(k)} \in (\Phi_{k,N},\prod_{l|k,l < k}{\Phi_{l,N}})$.
It follows that in $\mathbb{F}_p$, $k$ is the order of $yN^{-1}$, so $p$ is congruent to $1$ mod $p$.