# Find all positive integers $n > 1$ such that the polynomial $P(x)$ belongs to the ideal generated by the polynomial $x^2 +x +1$ in $\Bbb Z_n[x]$

Find all positive integers $n > 1$ such that the polynomial $x^4 + 3x^3 + x^2 + 6x + 10$ belong to the ideal generated by the polynomial $x^2 + x + 1$ in $\Bbb Z_n[x]$.

My attempt: I was using the Division Algorithm $$P(X)= X^4 + 3x^3 + X^2 +6X + 10 = (X^2 + x + 1)( x^2 + 2x -2) + (6x + 12).$$

Here I got the remainder $6x + 12$ not equal to $0$, so $P(x)$ is irreducible over $\Bbb Z_n[x]$ because it cannot be factored into the product of two non-constant polynomials.

My thinking is that $\Bbb Z_3[x]$ is only the satisfied $x^2 + x + 1$

$$(1)^2 + 1 + 1 =3$$ and we if we divide $3/3 =1$ and remainder $= 0$.

Therefore $3$ is the only positive integer $n > 1$ such that the polynomial $P(x)$ belong to the ideal generated by the polynomial $x^2 + x + 1$ in $\Bbb Z_n[x]$.

Is my answer is correct or not? I would be more thankful to rectifying my mistake.

Hint $\ 6x\!+\!12 = 0\,$ in $\,\Bbb Z_n[x]\iff 6=0=12\in \Bbb Z_n\!\iff n\mid 6,12\iff n\mid (6,12) = 6.$

• thanks @ Bill Dubuque – user396850 Aug 26 '17 at 22:32
• Notice $\,f = x^2\!+\!x\!+\!1\mid 6x\!+\!12 \!\iff\! 6x\!+\!12 = 0,\,$ since all nonzero multiples of $f$ have degree $\ge 2$ by examining lead coef's (this can fail if $f$ has nonunit lead coef, e.g. $\, (3x\!+\!2)(2x\!+\!3) = x\!\pmod{\!6}\,$) – Bill Dubuque Aug 26 '17 at 22:39

Because $x^4+3x^3+x^2+6x+10$ is in the ideal,

$p(x)=x^4+3x^3+x^2+6x+10-(x^2 + x + 1)( x^2 + 2x -2)=6x+12$ is also in the ideal.

So $6x+12=q(x)*(x^2+x+1)=q(x)x^2+(x+1)q(x)$.

As $deg(6x+12)=1$, $q(x)x^2=0$. Also $deg q(x)=1$, which leads to $6x+12=0$.

Therefore, n=2,3 or 6.

• im not getting why u write degq(x) = 1@ Will cai – user396850 Aug 26 '17 at 22:31
• if deg q(x)=k>1, q(x)=x^2*q_1(x)+q_2(x), deg(q(x)(x+1))>=2 – Will Cai Aug 26 '17 at 22:41
• thanks @ will chai – user396850 Aug 27 '17 at 4:20

I think Bill Dubuque addressed the problem, but I would note that when you were looking at the remainder $r(x) = x^2 + x + 1$, you were trying to plug in values for $x$ to show that $r = 0$. This is not what you want to do.

A polynomial is zero if and only if all its coefficients are zero. Like in your example, you can find polynomials that always evaluate to zero, but the polynomial itself is not zero. E.g. $x^2 + x + 1$ in $\mathbb{Z}/3\mathbb{Z}$ or $x^p - x$ in $\mathbb{Z}/p\mathbb{Z}$ if $p$ is prime. That is why in Hoffman and Kunze's Linear Algebra, they define polynomials abstractly in terms of their coefficients. That is, $x^2 + x + 1$ in $\mathbb{Z}/3\mathbb{Z}$ would be $(1, 1, 1, 0 , 0, \dots) \in \{(a_0, a_1, a_2, \dots): a_i \in \mathbb{Z}/3\mathbb{Z} \mbox{ are nonzero for only finitely many } i\}$. And the addition and multiplication of polynomials are done abstractly, just like complex numbers are: Construction of Complex Numbers Inside of Set Theory