6
$\begingroup$

By Grunwald-Wang 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 and the answer of David Loeffler who cites the paper of Moree. 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$.

$\endgroup$
  • 2
    $\begingroup$ Your condition $a^{(p-1)/b} \neq 1$ mod $p$ is equivalent to $a$ not being a $b$-th power mod $p$. I think you can use the Cebotarev theorem with the Galois extension $L/K$ where $K=\mathbf{Q}(\zeta_b)$ and $L$ is the splitting field of $X^b-a$. This will typically have Galois group $G\cong \mathbf{Z}/b\mathbf{Z}$, so the density of primes $\pi$ of $K$ such that $X^b-a$ has a root mod $\pi$ will be $1/b$. Since only the primes $\pi$ with norm $p \equiv 1$ mod $b$ asymptotically contribute to the density, I think this gives you what you want. $\endgroup$ – François Brunault Sep 8 '18 at 9:04
  • $\begingroup$ This is analogous to what happens with the cyclotomic polynomial $\Phi_n$ over $\mathbf{Q}$ : the Galois group $G=(\mathbf{Z}/n\mathbf{Z})^\times$ acts simply transitively on the roots of $\Phi_n$, so the density of primes $p$ such that $\Phi_n$ splits over $\mathbf{F}_p$ is $1/\varphi(n)$. But it is well-known that $\Phi_n$ splits if and only if $p \equiv 1$ mod $n$, so in this case Cebotarev is equivalent to Dirichlet's theorem for these primes. (And the full version of Cebotarev gives you the full Dirichlet theorem for primes $\equiv a$ mod $n$.) $\endgroup$ – François Brunault Sep 8 '18 at 10:46
  • $\begingroup$ @FrançoisBrunault Thank you for your valuable comments. I do not understand one point: indeed, by Frobenius Theorem, we know that the density of primes $p$ for which $X^b=a$ has no solutions in $1-\frac1{|G|}$ where $|G|$ is the cardinality of the Galois group of the extension of $\mathbb Q$ by roots of $X^b=a$. The density of primes in $1+b\mathbb N$ is $1/b$. So, we need the Galois group $G$ to have cardinality $|G|>b$ (in order to have a prime in the intersection). But I do not see why $G$ has so large cardinality. Please explain. $\endgroup$ – Taras Banakh Sep 8 '18 at 11:28
  • $\begingroup$ @FrançoisBrunault Could you give me a reference to the fact that $X^b=1 \mod p$ has a solution if and only if $p=1\mod b$. Thank you. $\endgroup$ – Taras Banakh Sep 8 '18 at 11:41
  • $\begingroup$ @FrançoisBrunault Could you please explan why the Galois group of $X^b-a$ is exactly this semidirect product and why it acts this way on the roots of $X^b-a$. $\endgroup$ – Taras Banakh Sep 8 '18 at 12:06
5
$\begingroup$

$\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$.

$\endgroup$
5
$\begingroup$

Perhaps I miss the point, but: It seems the OP already knows that, under his hypothesis, there is some prime $p$ for which $x^b \equiv a\pmod{p}$ has no solution. He is only asking that $p$ be allowed to be taken from the progression $1\bmod{b}$. But this extra restriction on $p$ is not an extra restriction at all!

As François points out, if $p-1$ is coprime to $b$ then it is easy to see that $x\mapsto x^{b}$ is a bijection on the $(p-1)$-element group $(\mathbb{Z}/p\mathbb{Z})^{\times}$, and so also on the field $\mathbb{Z}/p\mathbb{Z}$. So the only $p$ that can arise above have $p-1$ not coprime to $b$. Since $b$ is assumed prime, $p\equiv 1\pmod{b}$.

EDITED TO ADD: Here's a fairly simple way to see that there are some primes for which $a$ is not a $b$th power. If $b$ is prime and $a \in \mathbb{Z}$ is not a $b$th power (as follows from the OP's assumptions), then $x^b-a$ is irreducible over $\mathbb{Q}$. This is an elementary exercise in Galois theory. (By more intricate arguments, one can completely characterize irreducible binomials over an arbitrary field --- this is a theorem attached to the name of Capelli.) But it's also well-known that an irreducible polynomial of degree $>1$ cannot have a root modulo every prime (or even "almost" every prime); see: Irreducible polynomials with a root modulo almost all primes

$\endgroup$
  • $\begingroup$ Thank you for the great answer and indeed very simple argument! $\endgroup$ – Taras Banakh Sep 8 '18 at 16:29
  • $\begingroup$ @TarasBanakh Glad to help. I'm curious about the application to the Golomb topology. Don't keep us in suspense too long. :-) $\endgroup$ – so-called friend Don Sep 8 '18 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.