abstract algebra - Proving the remainder when a polynomial is divided by an integer.

How should I go around proving that $\forall x \in \mathbb{Z}$, the remainder when $x^2+2x$ is divided by $3$ is $0$ or $2$?

Do I use the division algorithm for this one?

Answer

As one can show, the remainder of a sum equals the sum of the remainders*

$$(a+b)\text{ rem } m=((a\text{ rem } m)+(b\text{ rem } m))\text{ rem } m.$$
And the remainder of a product equals the product of the remainders*
$$(a\cdot b)\text{ rem } m=((a\text{ rem } m)\cdot(b\text{ rem } m))\text{ rem } m.$$
(*provided you take the reminder once again to avoid exceeding the divisor.)

Then

$$(x^2+2x)\text{ rem }3=(x^2\text{ rem }3+2x\text{ rem }3)\text{ rem }3=((x\text{ rem }3)^2+2(x\text{ rem }3))\text{ rem }3.$$
As $x\text{ rem }3$ can take only the values $0,1,2$, it suffices to evaluate for these.