well i think is an easy one...lets say that $g(x)=x^g+a_{g-1}x^{g-1}+...+a_{0}$ and $q(x)=x^q+b_{q-1}x^{q-1}+...+b_{0}$ then $a_{0}b_{0}=3$ so WLOG $b_{0}$ is multiple of 3 so lets prove by induction that $b_{n}$ is multiple of 3 first lets see that $b_{0}$ is and we know that the coefficient of $x^1$ in $p(x)$ is 0 so $b_{0}a_{1}+b_{1}a_{0}=0$ or $b_{0}a_{1}=-b_{1}a_{0]}$ and $a_{0}$ is not multiple of 3 so $b_{1}$ must be and that way you can get the result. that is looking for the coefficient 0 of $x^{n}$ in $p(x)$ and having that $b_{i}=3k$ for $i=0,1,...,n-1$ all that is sufficient if the coefficient is 0 in $x^{q}$ and doesnt occur if $q=n-1$ if that is true then $g(x)=x+g$ with g not multiple of 3. so then $g^n+5g^{n-1}=g^{n-1}(g+5)=-3$ for some integrer g, but then $g^{n-1}$ divides 3, so $g=1$ or $g=+/-3,n=2$ and both are wrong is it right? ?

We want to prove that $f(x)$ is irreducible over $\mathbb{Z}$. Since $f(x)$ largest degree's term is $1$, its factors' largest degree's terms are $1$. By the Extended Eisenstein Criterion, $f(x)$ has an irreducible factor over $\mathbb{Z}$ with degree larger that $n-2$. So it has an irreducible factor over $\mathbb{Z}$ with degree $n-1$ or $n$. Let's suppose $f(x)$ has an irreducible factor $\mathbb{Z}$ with degree $n-1$. So it also has an irreducible factor with degree $1$, and since its largest degree's term is $1$, it has a zero over $\mathbb{Z}$, which means $f(x)$ also has a zero over $\mathbb{Z}$. But $f(x)$ is always odd, therefore it can't be $0$. Contradiction! So $f(x)$ has a irreducible factor over $\mathbb{Z}$ with degree $n$, which is $f(x)$, QED.

Just edited my post at http://www.mathlinks.ro/viewtopic.php?t=37593 to include this problem as well. Just take $p = 3$ (which is prime) and $q = 1$ (which is squarefree and not divisible by $p$). And consider the case $n=2$ separately. darij

It is a direct consequence of extended Eisenstein's criterion and rational root theorem

you can use peron criterion it's obvious with peron

What is Peron criterion?

He wants to say Perron. It's Theorem A in http://rms.unibuc.ro/bulletin/pdf/53-3/perron.pdf . Applying it here is pretty much overkill, though.

You could use perron's, but saying 5>4 is a little boring, don't you think? Another way to do this problem is to reduce it mod 3. We have $x^n+5x^{n-1}+3 \equiv x^n+2x^{n-1}$ (mod 3). Simplifying gives $x^{n-1}(x-2)$. Suppose f(x)=g(x)h(x), for some $g, h \in \mathbb{Z}[x]$ nonconstant. Since x and x-2 are irreducible in $\mathbb{F}_3[x]$, we have (WLOG) $g(x)=x^k+3g_1(x)$ and $h(x)=x^{n-k-1}(n-2)+3h_1(x)$, for some integer polynomials $g_1$ and $h_1$. First we consider the case where k=0. This means that g is nonconstant, a contradiction. If k=n-1, then h(x) is a linear polynomial, so f must have an integer root. We can easily check that this is false. Finally, if 1<k<n-1, multiplying g and h gives $x^{n-1}(x-2)+3g_1(x)x^{n-k-1}(x-2)+3h_1(x)x^k+9g_1(x)h_1(x)$. Setting this equal to our original polynomial and plugging in x=0 gives $9g_1(0)h_1(0)=3$. Since $g_1, h_1 \in \mathbb{Z}[x]$, this is clearly a contradiction. Thus, our polynomial is irreducible in $\mathbb{Z}[x]$. I think this problem could also be classified as number theory. Irreducible polynomials is one of the biggest overlaps of NT and algebra.

EDIT: Ignore this.

So, first, from $f(a_i) = a_i^n + 5a_i^{n-1} + 3 = 0$, you deduce $a_i^n + 5a_i^{n-1} = -3$, which is correct, only that you write $f(a_i) = a_i^n + 5a_i^{n-1} = -3$. Nice piece of algebra! All we have is $f(a_i) -3 = a_i^n + 5a_i^{n-1} = -3$. And now we will have $g(a_i)h(a_i) -3 = -3$, i.e. $g(a_i)h(a_i) = 0$; obviously, since $g,h$ are the factors of $f$. Therefore $(g(a_i), h(a_i)) = (\pm 1, \mp 3)$ is clearly wrong, since at least one of them must be $0$. Moreover, in your mistaken way, you miss the possibility $(g(a_i), h(a_i)) = (\pm 3, \mp 1)$. Nevermind, indeed under these wrong conclusions we would have $p(a_i) = g(a_i)+h(a_i) \in \{-2,2\}$, which you then write $p(a_i) =\pm 2$. True, $\deg p \leq n-1$. But you don't know that the $a_i$'s, $1\leq i \leq n$ are distinct, and even if they were, this does not contradict that Fundamental Theorem (rather the simple theorem that a polynomial cannot have more roots than its degree), since $\pm 2$ is not just one value; for example for the polynomial $p(x) = x^2-3$ we have $p(\pm 1) = -2$ and $p(\pm\sqrt{5}) = 2$. So even if your argumentation up to this point were correct, you still have no contradiction. When only knowing $\deg p \leq n-1$, you need $p(x) = \pm 2$ for at least $2n-1$ distinct arguments, in order to get a contradiction.

Suppose f(x) = $(x^r + a_{r-1}x^{r-1} + ... + a_1x + 3)(x^s + b_{s-1}x^{s-1} + ... + b_1x + 1)$. We show that all the a's are divisible by 3 and using that we will establish a contradiction .[Here , we will show using only + ve sign of 3 , the other case is f(x) = $(x^r + a_{r-1}x^{r-1} + ... + a_1x - 3)(x^s + b_{s-1}x^{s-1} + ... + b_1x - 1)$ , in which constant terms contains only - ve terms and the casee follows only the + ve case . So , we will show here only the first case] . r and s must be greater than 1.Because for if r = 1, then 3 is a root . Now we will make two cases : case 1: n is even, then it follows that 0 = $3^n +5\cdot$$3^{n- 1} + 3 = 3^{n-1}( 3 +5)+ 3$, which is false since 3+5 = 8. case 2 : if n is odd we would have 0 = $3^{n-1}(3 + 5) + 3$, which is false since 3 + 5 = 8. If s = 1, then 1 is a root and we will argue by contradiction in the same way . So r$\leq$n - 2, and hence the coefficients of x, $x^2, ... , x^r$ are all zero. Since the coefficient of x is zero, we have: $a_1+3b_1 = 0$, so $a_1$ is divisible by 3. Now , we will use the induction hypothesis . We can now proceed by induction. Assume $a_1, ... , a_t$ are all divisible by 3. Then consider the coefficient of $x_{t+1}$. If s-1 $\geq$t+1, then $a_{t+1}$ = linear combination of $a_1,... , a_t + 3b_{t+1}$. If s-1 $\leq$ t+1, then $a_{t+1}$ = linear combination of some or all of $a_1,... , a_t.$ Either way, $a_{t+1}$ is divisible by 3. Now we will consider the coefficients of x, $x^2$, ... , $x^{r-1}$ which gives us that all the a's are multiples of 3. Now consider the coefficientof $x^r$ which is also zero. Now we will get , that is a sum of of terms which are multiples of 3 . Then it does not becomes 0. So , follows a contradiction ! So , the factorization is not possible .( proved ). -NEELANJAN MONDAL.

Extended Eisenstein $->$ RRT $->$ $\mod 2$ $->$ Done.

My point is, would your solution even count if you directly apply Eisenstein on this problem, because it completely trivialises the problem... (apparently any use of a theorem is prohibited if it trivialises the problem, and this theorem certainly does, right?)

It is a direct result of Perron's criterion. Alternatively, suppose $x^n+5x^{n-1}+3 = f(x)g(x)$. Reduce it modulo 3 to get $f(x)g(x) \equiv x^{n-1}(x+5)$, so we can assume that $f(x) = x^{p}(x+5) + 3F(x)$, $g(x) = x^{q} + 3G(x)$. Multiply them to get $x^qF(x)+x^p(x+5)G(x)+3F(x)G(x) = 1$. Plug in $x=0$, then $3F(0)G(0)=1$, clearly impossible.

pi_is_3.141 wrote:

oh lol someone is taking AMSP Alg 3...

fukano_2 wrote:

I think this is wrong? $\overline{f(x)}$ only needs to be irreducible $\pmod 5$, not completely irreducible (for example, if I took $f(x)=x^2+2x+1$ and had $x^2+2x+1\equiv x^2+1\pmod 2$, $x^2+1$ being irreducible doesn't imply $x^2+2x+1$ is irreducible, since $x^2+1$ could still be reducible $\pmod 2$).

This can be done by using perrons criterian

By pure coincidence, I had been looking at irreducibility criterion when I encountered this problem. Perron's kills it. Since $5>1+3$, $f$ is irreducible over $\mathbb Z[x]$. $\square$

What on earth?!

orl wrote: Let $n > 1$ be an integer and let $f(x) = x^n + 5 \cdot x^{n-1} + 3.$ Prove that there do not exist polynomials $g(x),h(x),$ each having integer coefficients and degree at least one, such that $f(x) = g(x) \cdot h(x).$ 1 liner by Perron's By IG's inequality, $5$ is a greater number than $1+3=4$. Hence, we are done since Perron's finishes over $\mathbb{Z}\left[x\right]$ $\square$ Good thing i still have my irreducibility handouts it's also not too hard to prove perron's irreducibility criterion in olympiads, assume the assertion and suppose that $f(x)=g(x)h(x)$. This means that $f$ has only 1 root of modulus greater than 1, which means either $g$ or $h$ has roots not outside the unit circle. You'll reach a contradiction that $|g(0)| < 1$ yet $g(0)$ is, by definition, a nonnegative integer.

Everyone says "Perron's" but there's no explanation of what Perron's Criterion is, so I'll put the general statement here. Quote: Let $f(X)=X^n+a_{n-1}X^{n-1}+\cdots+a_1X+a_0$ be a polynomial with integer coefficients such that $a_0\neq 0$ and $$|a_{n-1}|>1+|a_{n-2}+\cdots+|a_1|+|a_0|.$$ Then $f(X)$ is irreducible in $\mathbb{Z}[X].$ We come back to the original problem. Quote: Prove that the polynomial $X^n + 5X^{n-1} + 3$ is irreducible in $\mathbb{Z}[X].$ Direct application of Perron's gives $5>1+3,$ so the polynomial is irreducible as required. Below is an alternate solution through Eisenstein's Criterion, of which here is the statement: Quote: Let $f(X)=a_nX^n+a_{n-1}X^{n-1}+\cdots+a_1X+a_0$ be a polynomial with integer coefficients. Then $f(X)$ is irreducible in $\mathbb{Z}[X]$ if there exists a prime $p$ such that (i) $p \mid a_0, p \mid a_1, \cdots, p \mid a_{n-1},$ and (i) $p \nmid a_n, p^2 \nmid a_0.$ It is easy to verify by the rational root theorem that no linear factors divide $X^n+5X^{n-1}+3.$ Assume on the contrary that $P(X)=X^n+5X^{n-1}+3=f(X)g(X).$ Taking mod three, we get $$f(X)g(X)\equiv X^{n-1}(X-1)\pmod 3.$$ Let $f(X)\equiv X^a\pmod 3,g(X)\pmod X^b(x-1)\pmod 3.$ Now, $a,b\neq 0$ since $f(X),g(X)$ both have degree at least two. Thus, we have $3\mid f(0)$ and $3\mid g(0)$ so $9\mid P(0)$ which is clearly false because $P(0)=3.$

Wow, I have finally done an irreducibility problem. Let's not use Perron's Criterion. Write $x^n + 5x^{n-1} + 3 = g(x) h(x)$ for some polynomials $g\in \mathbb Z[x]$ and $h\in \mathbb Z[x]$. Plugging in $x = 0$ yields $g(0)h(0) = 3$, so without loss of generality $3\nmid h(0)$. However, taking $f$ modulo $3$ yields $$x^n - x^{n-1} \equiv \bar g(x) \bar h(x)\pmod 3.$$ Thus, $x$ cannot divide $\bar h(x)$. There are two cases to consider. In the first case, $g(x) = x^{n-1} + 3p(x)$ and $h(x) = x - 1 + 3q(x)$ for some polynomials $p\in \mathbb Z[x]$ and $q\in\mathbb Z[x]$. Since $\deg g \geq n - 1$ and $\deg h \geq 1$, these inequalities are actually equalities. That is, $h$ is linear and $f$ has a rational root. But the only rational roots $f$ can possibly have are $-1$ and $-3$ (RRT combined with the fact that $f$ has no positive roots), and both of these fail. In the second case, $g(x) = x^n - x^{n-1} + 3p(x)$ and $h(x) = 1 + 3q(x)$ for some polynomials $p\in \mathbb Z[x]$ and $q\in\mathbb Z[x]$. Comparing degrees in the same way implies that $h$ is a constant. In turn, $f$ is irreducible.

orl wrote: Let $n > 1$ be an integer and let $f(x) = x^n + 5 \cdot x^{n-1} + 3.$ Prove that there do not exist polynomials $g(x),h(x),$ each having integer coefficients and degree at least one, such that $f(x) = g(x) \cdot h(x).$ Also PEN Q7

For storage: FTSOC assume the contrary and set $f(x)=h(x)\cdot g(x)$ where $h(x),g(x) \in \mathbb{Z}[x]$. plugging in $x=0$ yields $h(0)g(0)=3$ and plugging $x=-5$ we get $h(-5)g(-5)=3$. now by RRT, we can clearly observe that there is no integer root of $f(x)$ hence $h(x)$ and $g(x)$ are not linear. set $h(x)=(x-z_{1})(x-z_{2})\cdots (x-z_{r})$ where $\text{deg(h(x))}=r$ and $z_{i}$'s are root of $h(x)$ for $1\leqslant i \leqslant r$ now WLOG take $h(0)=\pm 1$ ( since $h(x) \in \mathbb{Z}[x]$) we get $\left|\prod_{i=1}^{r} z_{i}\right|=1$ and $\left|\prod_{i=1}^{r}(z_{i}+5)\right|=|(z_{1}+5)(z_{2}+5)\cdots (z_{r}+5)|$ now notice for $z_{l} \in \{z_{1},z_{2},\cdots z_{r}\}$ we get $z_{l}^{n-1}(z_{l}+5)=-3$ hence we get: $\left|\prod_{i=1}^{r}(z_{i}+5)\right|=\left|\prod_{i=1}^{r}\frac{-3}{z_{i}^{n-1}}\right|=3^{r}$ which gives that $|h(-5)|=3^{r}$ but also since $|h(-5)||3$ ( as $h(-5)g(-5)=3$ and $h(x)\in \mathbb{Z}[x]$) we have that $3^{r}|3$ for $r>1$ which gives a contradiction , and hence the result follows $\blacksquare$

Using Einstein's Criterion we take p=3, in this case 3 divides a0 , 3 dosent divide an and 3^2 dosent divide 3 therefore by Einstein's criterion it implies that f(x) is irreducible.

@above: that doesn't work. Eisenstein's Criterion requires $p = 3$ to divide every coefficient except the leading one. Because $3$ does not divide $5$, you can't naively use Eisenstein here.

Yes my mistake

It is enough to show that $f$ is irreducible in $\mathbb{Q}$ since it is primitive. Observe that $p(x) = 5x^{n-1} + 3$ is irreducible in $\mathbb{Q}$ by Eisenstein. Then $x^n+p \in \mathbb{Q}[x][x]$, where $p$ is taken as the constant coefficient, is irreducible in $\mathbb{Q}[x]$ by the general Eisenstein criterion, hence $f$ is irreducible in $\mathbb{Q}$.

That doesn't work. Unless I'm misunderstanding your argument, by that logic, if $p(x)$ is any irreducible polynomial of degree less than $k$, then $x^k + p(x)$ is also irreducible. This is clearly false, take $p(x) = 3x^2 + 3x + 1$ and $k = 3$. (Also, what is $\mathbb Q[x][x]$? If you mean "the ring of polynomials in $x$ whose coefficients are polynomials in $x$", then this really is the same thing as $\mathbb Q[x]$. In particular, given a ring $K$, the polynomial ring $K[X]$ can be thought of taking the ring $K$ and adding a new variable $X$ which commutes with elements of $K$ but otherwise has no additional properties. This means something like $\mathbb Q[x][x]$ is inherently problematic, because the first $x$ and the second $x$ interact with each other nontrivially.)

You're right. I misremembered the generalized Eisenstein criterion.