Which values of $a$ and $b$ will give $x^{2}+2$ as a factor of $x^{17}+ax+b$ over $\mathbb{Z}_{3}$? 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.
 A: 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.
A: 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$.
A: 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}$
