By [Grunwald-Wang Theorem](https://en.wikipedia.org/wiki/Grunwald%E2%80%93Wang_theorem), if for some odd number $n$ the equation $x^n=a$ has no solutions in $\mathbb Z$, then the equation $x^n=a\mod p$ has no solutions for some prime number $p$. I am interested if we can always choose $p$ is the arithmetic sequence $1+n\mathbb N$ (at least for prime $n$). 



> 
> **Question.** Let $b$ be a prime number and $a\in\mathbb N\setminus\{n^{k+1}:n,k\in\mathbb N\}$. Is it true that the equality $x^b=a\mod p$ has no solutions for some prime number $p\in 1+b\mathbb N$?
> 
> 
> 


**Remark.** This question has affirmative answer under GRH (a Generalized Riemann Hypothesis), see [this MO-problem](https://mathoverflow.net/questions/310061/a-stronger-form-of-the-dirichlet-theorem-on-prime-numbers-in-arithmetic-sequence) and the answer of David Loeffler who cites [the paper of Moree](http://matwbn.icm.edu.pl/ksiazki/aa/aa89/aa8912.pdf). So, the problem is to find an affirmative answer to my question without GRH. For my purposes it suffices to assume that the number $a$ is taken from the set $d\mathbb N$ for some $d\in\mathbb N$.



A simultaneous generalization of the Grunwald-Wang and Dirichlet Theorems on primes
$\newcommand{\Z}{\mathbf{Z}}$
$\newcommand{\Q}{\mathbf{Q}}$
$\newcommand{\F}{\mathbf{F}}$
$\newcommand{\OK}{\mathcal{O}\_K}$


**EDIT**. To prove the existence of at least one prime (or infinitely many primes) meeting the OP's requirement, there is a much simpler argument, see the answer by a so-called friend Don. My answer is more about computing the density of such primes.


The answer is yes, this is a consequence of the Cebotarev theorem for Galois extensions of number fields.


Let $b \geq 2$ be an integer, and let $a \in \Z \backslash \{0\}$. Let $L$ be the splitting field of the polynomial $P=X^b-a$ over $\Q$. Then $L$ contains the $b$-th roots of unity and thus the cyclotomic field $K=\Q(\zeta\_b)$. Let $G$ be the Galois group of $L/K$. The action of $G$ on the roots of $P$ is easy to understand. Namely, if $\alpha$ is a root of $P$ (in other words $\alpha$ is a $b$-th root of $a$), then every other root is of the form $\alpha'=\zeta\_b^k \alpha$ for some $k \in \Z/b\Z$. It follows that for any $\sigma \in G$ we have $\sigma(\alpha)=\zeta\_b^{\lambda(\sigma)} \alpha$ for some $\lambda(\sigma) \in \Z/b\Z$. This provides a group morphism $\lambda : G \to \Z/b\Z$ which does not depend on the choice of $\alpha$, and is injective since $G$ fixes the $b$-th roots of unity. Now if $b$ is odd and for any prime divisor $p$ of $b$, the integer $a$ is not a $p$-th power in $\Z$, then $\lambda$ is surjective (see Lang, *Algebra*, Chapter 6, Thm 9.4), so in this case the action of $G$ on the roots of $P$ is simply transitive. (The situation is more complicated in the case $b$ is even, since $\sqrt{-1} \in \Q(\zeta\_4)$ and $\sqrt{2} \in \Q(\zeta\_8)$ for example. You could try to look at Jacobson--Vélez, *The Galois group of a radical extension of the rationals*. At least, this is also true when $b=2$, in which case the argument below applies.)


Let us recall some algebraic number theory. Let $p$ be a prime not dividing $b$. Let $\Phi\_b$ be the cyclotomic polynomial and $\overline{\Phi\_b} \in \F\_p[X]$ its reduction mod $p$. It is known that $\overline{\Phi\_b}$ is a product of $r$ distinct irreducible polynomials of degree $e$, where $e$ is the order of $p$ in $(\mathbf{Z}/b\mathbf{Z})^\times$ and $re=\varphi(b)$, see Demazure, *Cours d'algèbre*, Prop 9.17. In particular $\overline{\Phi\_b}$ has a root in $\F\_p$ if and only if $p \equiv 1$ mod $b$. Accordingly $p$ is the product of distinct prime ideals $\pi\_1,\ldots,\pi\_r$ in the ring of integers $\OK$ of $K$, and each such ideal has norm $p^e$. In particular, the prime ideals with $e \geq 2$ will have density zero (with respect to the norm), and we only need to care about prime ideals above the primes $p \equiv 1$ mod $b$. For such a prime $p$, note that $\OK/\pi \cong \F\_p$ for any prime $\pi$ above $p$, so the equation $x^b = a$ has a root mod $p$ if and only if it has a root in $\OK$ modulo some (or any) prime $\pi$ above $p$.


Now we want to apply the Cebotarev theorem to the Galois extension $L/K$. By the above, we have to count the number of $\sigma$ in $G$ which fix at least one root of $P$, and this happens if and only if $\sigma = 1$. We get that the density of prime ideals $\pi$ of $\OK$ such that $x^b=a$ has a root modulo $\pi$ is equal to $1/b$. It follows that the density of primes $p \equiv 1$ mod $b$ such that $a$ is not a $b$-th power mod $p$ is equal to $1-1/b$.


More generally, one can prove as an exercise that given a divisor $d$ of $b$, the density of primes $p \equiv 1$ mod $b$ such that $a^{(p-1)/b}$ has order $d$ in $(\Z/p\Z)^\times$ is equal to $\varphi(d)/b$. This says in particular that $a^{(p-1)/b}$ is a primitive $b$-th root of unity in $\Z/p\Z$ for at least $\varphi(b)/b$ of the primes $p \equiv 1$ mod $b$.


Alternatively, we could have used the Cebotarev theorem for the Galois extension $L/\Q$. It is an instructive exercise since the Galois group is more complicated: it is isomorphic to the semi-direct product $(\Z/b\Z) \rtimes (\Z/b\Z)^\times$. Its action on the roots of $P$ is given (up to isomorphism) by affine transformations $x \mapsto \alpha x+\beta$ with $\alpha \in (\Z/b\Z)^\times$ and $\beta \in \Z/b\Z$. If $b$ is an odd prime we get that the density of primes $p$ such that $x^b=a$ has no root mod $p$ is equal to $1/b$. Using the fact that each such prime must be $\equiv 1$ mod $b$ (if $b$ is prime to $p-1$ then $x \mapsto x^b$ is a bijection of $\Z/p\Z$) together with Dirichlet's theorem for primes congruent to $1$ mod $b$, we recover the above result. But I find the first argument easier, and it works for arbitrary $b \geq 2$.


