'shifted' polynomial preserves validity of Eisenstein irreducibility criterion of original, in finite fields?

This is not really research level, but I know not where else to ask it.

The Eisenstein criterion for polynomial irreducibility over rationals or integers permits shifting the original (primitive) polynomial by substituting (x + a) in place of the original variable x, for some integer a. If the shifted polynomial is irreducible, then so was the original, since this shifting is an automorphism on the ring of polynomials over the rationals.

Is the same shifting permitted over finite fields, such that the irreducibility of the shifted polynomial p(x) over finite field GF(q) with a < q guarantees the irreducibility of the original polynomial?

Also, a second question, somewhat related, if a polynomial is irreducible over Z, is it irreducible over any finite field?

• $x^2+1$ is irreducible over $\mathbb Z$ but equals $(x+2)(x+3)$ over $\mathbb F_5$. – Dilip Sarwate Jan 21 '13 at 23:31

If $F$ is any field, and $p$ is any polynomial over $F$, and $a$ is any element of $F$, then $p(x)$ is irreducible over $F$ if and only if $p(x+a)$ is irreduible over $F$. This has nothing to do with Eisenstein. The proof will be a good exercise for you.

EDIT: $x^2+1$ is irreducible over the integers but not over the integers modulo $2$.

• p(x+a) = sum(j_k.(x+a)**k), p(x) = sum(j_k.x**k). p(x+a) = p(x) + ( p(a) - j_0 ) + ( h(x,a) - j_0 ). I tried but I got stuck here. Alfonso's equations doesn't really make sense to me. – Cris Stringfellow Jan 21 '13 at 23:58
• Give Alfonso's equations another look. Alfonso is telling you that if $q$ is a shift of $p$ then factors of $q$ are (identical) shifts of factors of $p$. – Gerry Myerson Jan 22 '13 at 2:49
• Okay I will look at this again. – Cris Stringfellow Jan 22 '13 at 6:00
• so if q(x) = p(x + a) then if q(x) has factors, then p(x+a) has factors. q(x) = r(x)s(x), then p(x) = r(x-a)s(x-a) [because p(x) = q(x-a)], so if s(x) is a constant, then s(x-a) is constant, so if q(x) is irreducible, then p(x) is irreducible, and vice versa. Is that correct? – Cris Stringfellow Jan 22 '13 at 20:11
• Yes. ${}{}{}{}$ – Gerry Myerson Jan 22 '13 at 22:42

For the first question, the answer is of course yes, because if $q(x) = p(x+a)$, then $p(x) = q(x-a)$, so if $q(x)=r(x)s(x)$, then $p(x)=r(x-a)s(x-a)$.

For the second question, the answer is no, for example $x^2+1$ is irreducible over $\mathbb{Z}$, but $(x+1)(x+1) = x^2 + 1$ over $\mathbb{Z}_2$.

• I don't think you're answering his second question. My suspicion is that the second question is whether a polynomial irreducible over the integers is irreducible over some finite field. (I have learned through experience that sometimes when people write "any" they mean "some" rather than "all".) The answer to the question is no, and the simplest example is $x^4 + 10x^2 + 1$, which is irreducible over the integers but is reducible mod $p$ for every prime number $p$. – KCd Jan 21 '13 at 23:52
• I think you are right KCd. I believe I meant 'if it is irreducible over integers, does that mean that it is never reducible?' -- I still don't understand how that can be. Can't there be a few primes under which a polynomial is irreducible and then we can say, that is it, it is now irreducible under every prime. Why aren't integers good enough for making it irreducible everywhere. – Cris Stringfellow Jan 21 '13 at 23:57
• Cris, given any finite set of primes, there is a polynomial which is irreducible modulo all of those primes, but reducible modulo infinitely many other primes. Given any two finite sets of primes, there is a polynomial irreducible modulo each prime in the first set, and reducible modulo each prime in the second set. – Gerry Myerson Jan 22 '13 at 2:52
• Cris: To see how how a polynomial irreducible over the integers could be modulo all primes,let's look at $x^4 - 10x^2 + 1$. (I wrote previously $x^4+10x^2+1$, which also works, but I change signs for a reason I'll explain later.) It has four real roots: $\pm\sqrt{2}\pm\sqrt{3}$ for all 4 choices of signs. If you collect these in parts you get 3 factorizations:$(x^2-2\sqrt{2}x-1)(x^2+2\sqrt{2}x-1)$, $(x^2-2\sqrt{3}x-1)(x^2+2\sqrt{3}x-1)$, and $(x^2-(5+2\sqrt{6})(x^2-(5-2\sqrt{6}))$. Although these factorizations were found over the real numbers (continued...) – KCd Jan 22 '13 at 16:04
• they would make sense mod $p$ if 2 is a square, 3 is a square, or 6 is a square mod $p$ (when use the mod $p$ square root in place of $\sqrt{2}$, $\sqrt{3}$, or $\sqrt{6}$ to give meaning to the relevant factorization mod $p$). From elementary number theory, it is known that for any two integers $a$ or $b$ and any prime number $p$, either $a$, $b$, or $ab$ is a square modulo $p$. Therefore at least one of those factorizations into quadratics will make sense mod $p$, no matter what prime $p$ you use. For instance, taking $p = 7$, 2 is a square mod 7: $2 \equiv 3^2 \bmod 7$. [continued...] – KCd Jan 22 '13 at 16:06