Set $x=10$. If the polynomial can be factored into two other polynomials, then $p$ can be expressed as two decimal factors, and so is not prime, a contradiction. This seems really easy. Is there a flaw?

Flaw: The decimal factors could be $\pm 1$ or $\pm p$ if you set $x=10$.

Indeed, that would be too easy to be true (but I admit it's deceiving). I'm afraid you'll need some complex analysis to kill this one correctly.

Peter wrote: Indeed, that would be too easy to be true (but I admit it's deceiving). I'm afraid you'll need some complex analysis to kill this one correctly. Nope,this problem has very elementary solution,if I am not mistaken,it is enough to observe one inequality between roots and coefficients of the given polynomial...

Inequalities between complex roots is complex analysis, no? You won't need deep theorems, obviously, since it's from the BaMO.

Peter wrote: Inequalities between complex roots is complex analysis, no? You won't need deep theorems, obviously, since it's from the BaMO. Hmm...I didn't know that.Probably I have some misconceptions in definition of complex analysis.I can't figure out what you mean by your last sentence,whatever it means I agree with you,solution is pretty simple... Maybe you would be so kind to post the proof,assuming you have solved this problem.

Well I don't even know a definition of complex analyis, but if you do analysis (inequalities) on complex numbers, I'd be inclined to call that complex analysis. Sorry if that's a wrong wording. From Kalva: Quote: If w is a (complex) root of the polynomial, then since each coefficient is at most 9, we have |pn| ≤ 9(1/|w| + 1/|w|2 + ... + 1/|w|n-1). So if |w| ≥ 9, then |pn| ≤ 9(1/9 + 1/81 + ... ) < 9/8. But pn ≥ 2, so we must have |w| < 9. Suppose the polynomial has a factor with integer coefficients (and positive degree less than n). Then Gauss' lemma tells us that it must be a product of two polynomials with integer coefficients (and each with positive degree less than n). Suppose they are f(x) and g(x). Suppose the (complex) roots of f(x) are z1, ... , zm. Then f(x) = A(x - z1) ... (x - zm) with A and integer. Hence |f(10)| = |A| |10 - z1| ... |10 - zm|. But |A| ≥ 1 and each factor |10 - zi| > 10 - 9 = 1. So |f(10)| > 1. Similarly, |g(10)| > 1. But f(10) and g(10) are integers and their product is the prime p. So we have a contradiction. So the polynomial cannot have any such factor. By the way, it is also in the Resources section on this site.

Isn't this Cohn's irreducibility criterion?