# Existence of irreducible polynomials

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?

-
"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
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

@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}$.)

-
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