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?

Exhaust the possibilities:

When $x\equiv 0$: $x^2+2x\equiv 0+0\equiv 0$.

When $x\equiv 1$: $x^2+2x\equiv 1+2\equiv 0$.

When $x\equiv 2$: $x^2+2x\equiv 4+4\equiv 2$.

• How can you affirm that this exhausts the possibilities ? You should explain the relation between $x\bmod3$ and $P(x)\bmod3$.
– user65203
Jan 7 '15 at 10:36

Well, if $x=3k+r$ where $r\in\{0,1,2\}$ then $$x^2+2x=(3k+r)^2+2(3k+r)=3(\dots)+r^2+2r$$

You have $x^2 + 2x = (x + 1)^2 - 1$. Now one of the following happens for any $x \in \mathbb{Z}$.

$$x \equiv 0 \mod 3 \Rightarrow x+ 1 \equiv 1 \mod 3 \Rightarrow (x+1)^2 - 1 \equiv 0 \mod 3$$

$$x \equiv 1 \mod 3 \equiv (x+1)^2 \equiv 4 \equiv 1 \mod 3 \Rightarrow (x+1)^2 - 1 \equiv 0 \mod 3$$

$$x \equiv 2 \mod 3 \Rightarrow (x+1)^2 \equiv 9 \equiv 0 \mod 3 \Rightarrow (x+1)^2 -1 \equiv -1 \equiv 2 \mod 3$$

And there you have it.