Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $a \in \mathbb{Z}$, $n \in \mathbb{N}^*$ be integers, and set $P=X^n - a$. Let us consider the three following statements :

1) $P$ has a root in $\mathbb{Z}$ (i.e. $a$ is an nth power)

2) $P$ has a root in $\mathbb{Z}/d\mathbb{Z}$ for all $d \ge 1$ (i.e. $a$ is an nth power mod $d$ for all $d$)

3) $P$ has a root in $\mathbb{Z}/p\mathbb{Z}$ for all prime $p$ (i.e. $a$ is an nth power mod $p$ for all prime $p$)

I would like to prove that they are equivalent, but I still can't prove $3 \Rightarrow 1$.

Here's what I already know :

  • Obviously we have $1 \Rightarrow 2 \Rightarrow 3$

  • Proving $2 \Rightarrow 1$ is not very difficult ($2 \Rightarrow$ all $p$-adic valuations of a are multiples of $n$)

  • I think I can prove $3 \Rightarrow 1$ in the case $n = 2$. But my proof seems quite involved (and frankly a bit of an overkill) for this question : Roughly, if $a$ is not a square, I use the quadratic reciprocity law and Dirichlet's theorem to prove that there exist a prime $p$ for which the Legendre symbol of $a$ mod $p$ is $-1$.

So I guess my questions are : Can we prove $3 \Rightarrow 1$ ? Is there an "elementary" proof ? Thanks in advance for any comment or answer.

share|cite|improve this question
How are you using quadratic reciprocity? This is an $n$th power. – quanta May 6 '11 at 16:08
@ quanta : I was using quadratic reciprocity in the case $n = 2$. That is why I couldn't tackle the general case (I don't know much about higher order explicit reciprocity laws). Seeing the answer below, I realize now that my attempt was misguided. – Joel Cohen May 6 '11 at 16:19
Related:… – Qiaochu Yuan May 6 '11 at 16:59
Yes, this completely answers my question. Quite surprising and interesting... – Joel Cohen May 6 '11 at 17:25
up vote 16 down vote accepted

These statements are not equivalent. I claim that 3), but not 1) or 2), hold for the polynomial $x^8 - 16$ (see the Wikipedia article on the Grunwald-Wang theorem). The fact that 1) doesn't hold is obvious. Note that $16$ is an eighth power in $\mathbb{Z}/2\mathbb{Z}$, but not in $\mathbb{Z}/32\mathbb{Z}$, so 2) doesn't hold. Factor the polynomial as

$$(x^2 - 2)(x^2 + 2)(x^2 - 2x + 2)(x^2 + 2x + 2).$$

For any odd prime $p$, it's not hard to see that either $2, -2$, or $-1$ is a quadratic residue $\bmod p$. Depending on which of these is a quadratic residue, one of the quadratic fators above splits. Hence $x^8 - 16$ has a root $\bmod p$ for all odd primes $p$ and 3) holds.

Edit: Nevertheless, here is a positive result.

Proposition: Let $P(x) \in \mathbb{Z}[x]$ be a monic irreducible polynomial of degree $n > 1$. Then there exists a prime $p$ such that $P(x)$ has no roots $\bmod p$.

Proof. Given a prime $p$ not dividing the discriminant of $P$, consider the action of the Frobenius map $x \mapsto x^p$ on the roots of $P(x)$ in $\overline{ \mathbb{F}_p }$. Any orbit of this action gives an irreducible factor of $P(x)$, and conversely: hence the cycle type of the Frobenius map determines the factorization of $P(x)$ into irreducible factors $\bmod p$. Now, it is known (see the Wikipedia article) that any cycle type of a Frobenius map agrees with the cycle type of some element of the Galois group $G$ of $P$. Conversely, if the Galois group $G$ has an element of a particular cycle type, there is a prime $p$ such that the Frobenius element at $p$ has that cycle type by the Frobenius density theorem.

So it remains to show that $G$ has an element with no fixed points. Since $P$ is irreducible, $G$ acts transitively on its roots. By Burnside's lemma, it follows that

$$ \sum_{g \in G} |\text{Fix}(g)| = |G|.$$

But the identity element has $n > 1$ fixed points, so it must be the case that $|\text{Fix}(g)| = 0$ for some $g$ or else the LHS would be at least $(n-1) + |G|$.

The upshot is that the equivalence between 2) and 3) holds whenever $x^n - a$ would be irreducible if $a$ weren't an $n^{th}$ power, which holds (for example) when $n = 2, 3$.

Note that it is not true that $P(x)$ remains irreducible modulo some prime: this is equivalent to the claim that the Galois group contains a $n$-cycle, which is always true when $n = 2, 3$ and false in general for higher values of $n$. However, it is true for a generic polynomial in the sense that the generic polynomial of degree $n$ has Galois group $S_n$.

share|cite|improve this answer
My mistake. Hensel's Lemma does not hold if $p$ divides $n$. Oh well, thank you for your counterexample. – Joel Cohen May 6 '11 at 17:16
Very interesting addition to your original answer. So it seems one cannot avoid using some sort of density principle. – Joel Cohen May 6 '11 at 19:33
The fact that the argument goes without considering the ramified primes separately bothers me a bit. Let say $p$ is a prime that divides the discriminant of $P(x)$, then $P(x)$ will have multiple roots mod $p$. What does it mean "any cycle type of a Frobenius map agrees with the cycle type of some element of the Galois group G of P" in this case? – Jiangwei Xue May 7 '11 at 8:07
@Jiangwei: whoops. That first sentence should be "given a prime $p$ not dividing the discriminant of $P$." – Qiaochu Yuan May 7 '11 at 8:19

Also, the simplest example of a polynomial that is irreducible over $\mathbb Q$ but reducible modulo every prime is the traditional fave, $x^4+1$.

Edit: as suggested by a comment (thx! @Pierre-Yves G.), one proof of this begins by noting that $x^4+1$ is the 8th cyclotomic polynomial. Since $\mathbb F_{p^2}^\times$ is cyclic, there will be an 8th root of unity in $\mathbb F_{p^2}$ exactly when $8|p^2-1$, which would mean that $x^4+1$ factors into at worst quadratic factors over $\mathbb F_p$. Since $\mathbb Z/8^\times$ is a 2,2 group, $p^2=1$ mod $8$ for every odd prime $p$. ($x^4+1=(x+1)^2$ at $p=2$.)

share|cite|improve this answer
Dear Paul: I think it would be nice if you could add a proof of your statement (or at least a link to such a proof). – Pierre-Yves Gaillard Oct 13 '11 at 1:50
This is a nice example. Thanks. – Joel Cohen Oct 13 '11 at 21:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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