Variants of Eisenstein irreducibility In his article where he stated what we know as Eisenstein's irreducibility criterion (which actually was first proved by Schönemann, as was Scholz's reciprocity law and Hensel's Lemma), he claimed that the result also holds in the following case: assume that
$$ f(x) = x^m + a_{m-1}x^{m-1} + \ldots + a_0, $$
where the $a_i$ are integers divisible by $p$, and where $p^2 \nmid a_j$ for some 
$0 \le j \le m-1$. There is an obvious counterexample provided by the quadratic polynomial $f(x) = (x-p)^2 = x^2 -2px + p^2$, so that could be the end of that story. But it isn't: I've read somewhere that some form of this criterion holds for polynomials of degree $\ge 3$, and that the degrees of the possible factors of counterexamples can be predicted in terms of this index $j$. Unfortunately, I don't remember the exact statement (those who are familiar with Newton polygons will probably be able to figure out a correct version) or where I've seen this. Can anyone help?
 A: Such a generalization (Dumas' theorem) was discussed here: Is a polynomial with 1 very large coefficient irreducible?
A good source to learn about it is Prasolov's book on polynomials: http://tinyurl.com/prasolov - see page 53, Dumas' theorem (and a bit before this theorem).
A: I've meanwhile found something in


*

*S. MacLane,  The Schönemann-Eisenstein irreducibility criteria in terms of prime ideals, Trans. Amer. math. Soc. 43 (1938), 226--239.


MacLane referred, among others, to the article


*

*E. Netto,  Ueber die Irreductibilität ganzzahliger ganzer Functionen, 
Math. Ann. 48 (1897), 81--88


There, Netto proved the following: A polynomial
$$ f(x) = x^n + a_{n-1} p x^{n-1} + \ldots + a_{k+1} p z^{k+1}
          + a_k p^2 z^k + \ldots + a_0 p^2 $$
with degree $n > 2k$, in which the $a_j$ are integers such that 
$p \nmid a_0$, does not have a factor of degree less than $k+1$.
This is similar to Gjergji's second example, but allows the divisibility by $p^2$ that I had had in mind. 
A: Franz, if memory serves correct there is extensive discussion of variants of Eisenstein's criterion and relations with Newton polygon's etc in some of Filaseta's work, e.g. in his interesting book (draft) "The theory of irreducible polynomials". It was previously available at [1] but you may now need to write him for a password to access it. He also has some software available, e.g. Java applets for computing Newton polygons, etc.
[1] http://www.math.sc.edu/~filaseta/gradcourses/Math788F/latexbook/
A: Basically all such criteria boil down to some argument involving the Newton polygon as Kevin Buzzard mentions in the comments. While something as general as your statement has trivial counter examples the following generalization holds:

Let $R$ be a unique factorization domain and $f(x) =a_nx^n+\cdots +a_0\in R[x]$ with $a_0a_n\neq 0$. If the Newton polygon of $f$ with
  respect to some prime $p\in R$ consists of the only line segment from $(0,m)$ to $(n, 0)$
  and if $gcd(n,m) = 1$ then $f$ is irreducible in $R[X]$.

I've heard this called the Eisenstein-Dumas criterion of irreducibility (it also proves the example given in the comments). Another generalization of Eisenstein's criterion is the following:

If $p|a_0,a_1,\dots,a_k$ but $p^2\not | a_0$ then $f(x)$ has an irreducible factor of degree $\geq k+1$

(This is how you prove for example, that a polynomial like $x^n+5x^{n-1}+3$ is irreducible, after checking that it has no linear factors.) If not answering your question, at least I hope that this refreshes your memory of the statement you claim above. :)
