<s>[INST] 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?
 [/INST] 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. 
</s>