Which values of $a$ and $b$ will give $x^{2}+2$ as a factor of $x^{17}+ax+b$ over $\mathbb{Z}_{3}$?

Question

The question:

Let $x^{17}+ax+b$ be a polynomial over $\mathbb{Z}_{3}$. For which values of $a$ and $b$ will $x^{2}+2$ be a factor?

I know that I can find a solution by a brute force technique, but is there a more efficient way to solve this problem? Thanks.

Answer 1

If $x^2+2$ is a factor of that polynomial p, then every root of $x^2+2$ will be a root of p. $\mathbb{Z}_{3}$ only has 3 elements. Check which ones are roots of $x^2+2$. Then those same roots need to be roots of the polynomial. So $p(x_1)=0$ and $p(x_2)=0$. You get two equations with two unknowns, so you can solve for a and b.

Answer 2

If $x^2 + 2$ is a factor of

$p(x) = x^{17} + ax + b, \tag 0$

any zero of $x^2 + 2$ must also satisfy $p(x)$;. the zeroes of $x^2 + 2$ in $\Bbb Z_3$ are $1$ and $2$:

$1^2 + 2 = 3 \equiv 0 \mod 3, \tag 1$

$2^2+ 2 = 4 + 2 = 6 \equiv 0 \mod 3; \tag 2$

indeed

$(x - 1)(x - 2) = x^2 - 3x + 2 = x^2 + 2 \mod 3; \tag 3$

if $1$ and $2$ are roots of $p(x)$, then

$1 + a + b = 1^{17} + a \cdot 1 + b = p(1) = 0 \mod 3, \tag 4$

$2^{17} + a \cdot 2 + b = p(2) = 0 \mod 3; \tag 5$

now,

$2^{17} = 2(2^4)^4 = 2(16)^4 = 2(1)^4 = 2 \mod 3; \tag 6$

thus (5) becomes

$2 + 2a + b = p(1) = 0; \mod 3; \tag 7$

thus (4) and (7) form the system

$a + b = -1 = 2 \mod 3, \tag 8$

$2a + b = -2 = 1 \mod 3; \tag 9$

we subtract (8) from (9):

$a = -1 = 2 \mod 3, \tag{10}$

and then substitute this into (8):

$b + 2 = 2 \mod 3, \tag{11}$

whence

$b = 0 \mod 3; \tag{12}$

therefore

$p(x) = x^{17} + 2x. \tag{13}$

Note that

$p(1) = 1 + 2 \cdot 1 = 3 = 0 \mod 3 \checkmark \tag{14}$

and

$p(2) = 2^{17} + 2 \cdot 2 = 2 + 4 = 6 = 0 \mod 3 \checkmark \tag{15}$

Answer 3

Here's the efficient method :-)

In $\Bbb{Z}_3$ we have $2=-1$, so $x^2+2=x^2-1$. This is clearly a factor of $x^{2n}-1$ for all positive integers $n$. In particular $x^2-1\mid x^{16}-1$. Consequently $$x^2+2\mid x^{17}-x.$$ We can deduce that the remainder of $x^{17}+ax+b$ in long division by $x^2+2$ is thus $$ r(x)=(a+1)x+b. $$ Obviously this vanishes if and only if $a=-1=2$ and $b=0$.