Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

In a few algebra books it is proved, that for every $n,m \in \mathbb N$ there are polynomials $f(x)$ of degree $n$ which are irreducible mod $m$. They are divisors of $x^{m^n}-x \ \text{(mod }m)$.

Is this still true, if I allow only polynomials with real roots?

Or do you have some counterexamples?

share|cite|improve this question
"real roots" as in "has roots in $\mathbb{R}$"? In this case, choose $n=m=2$. The only irreducible polynomial over $\mathbb{F}_2$ of degree $2$ is $X^2+X+1$. – m_l Apr 22 '12 at 10:22
Thanks for your answer. – David75 Apr 22 '12 at 10:36
Yeah, but, over the field of 2 elements, $x^2+x+1$ is indistinguishable from $x^2+3x+1$, which does have real roots. I reckon that given any polynomial $f$ and any $m$ you can find a polynomial $g$, indistinguishable from $f$ modulo $m$, such that $g$ has only real roots. – Gerry Myerson Apr 22 '12 at 10:44
Good idea. It would be great, if you have a source or a proof for it. – David75 Apr 22 '12 at 11:34
up vote 2 down vote accepted

@Gerry: Oh, very true. I didn't think of that.

The proof is easy, I think. Let $f$ be irreducible mod $m$ of degree $n$. Without loss of generality, let $f$ be monic. If $n$ is odd, $f$ has a real root. If $n$ is even, $M := \text{min}_{x \in \mathbb{R}} f(x) > -\infty$. If $M < 0$, $f$ has a root. If $M>0$, define $g(x) := f(x) - m\lceil\frac{M}{m}\rceil$. Then $f \equiv g$ modulo $m$ and $g$ has a root $\zeta \in \mathbb{R}$ (by means of the intermediate value theorem).

Edit: You can also find a polynomial that splits over $\mathbb{R}$.

Let $\widetilde{g}$ be a polynomial such that $g(x) = \widetilde{g}(x) \cdot ( x - \zeta )$. We can repeat the same procedure with $\widetilde{g}$, but $\text{deg}(\widetilde{g}) = \text{deg}(g)-1$. By induction we are done.

(The statement we proved by induction on $n$ is as follows: Let $f$ be a polynomial of degree $n$ irreducible modulo $m$. Then there exists a polynomial $g \equiv f$ modulo $m$ such that $g$ splits over $\mathbb{R}$.)

share|cite|improve this answer
Ok, but it is not clear, that $f$ has only real roots. Maybe my question was a bit vague. All roots of the polynomial $f$ should be elements in $\mathbb R$. – David75 Apr 22 '12 at 12:28
Ah, you want $f$ to split into linear factors over $\mathbb{R}$? Well, that changes it a bit. :) Will think about it, may edit my answer later. – m_l Apr 22 '12 at 12:31

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.