Calculations in polynomial quotient rings e.g. $\mathbb{Z}[X]/(X^2+1)$ Is there a nice way to perform calculations within a quotient ring? for instance, an exercise I had was to show $\mathbb{Z}[X]/(X^2+1) \cong \mathbb{Z}[i]$, but this got me thinking; If I didn't know this, how could I calculate in $\mathbb{Z}[X]/(X^2+1)$ easily?  (and of course any other general quotient ring)? 
 A: Modular polynomial arithmetic is analogous to modular integer arithmetic since, in both cases, we have available an (Euclidean) algorithm for Division with Smaller Remainder. This allows us to efficiently calculate canonical normal-form reps of cosets, viz. those of least size, i.e. remainders.
If $R$ is a ring and $\,f\in R[x]\,$ has lead coeff $1$ (or any invertible) then we can divide by $f$ with unique remainder: for any $\,g\in R[x]\,$ there are $\,q,r\in R[x]\,$ with $\,g = q f + r,\,$ with $\,\deg r < \deg f.\,$  Said equivalently, $\,r\,$ is the least degree element of the coset $\,g + fR[x]$ in the quotient ring $\,S = R[x]/f.\, $ This easily implies that a complete system of reps for the quotient ring $S$ are all such remainders mod $\,f,\,$ which is clearly the set of all polynomials of smaller degree than $\,f.$
Then, just like in $\,\Bbb Z/m,\,$ we transport the ring structure to this set of normal reps, e.g. to calculate the product of two reps, we multiply them as elements of $\,R[x]$ then reduce the result $\,{\rm mod}\ f\,$ to obtain the least degree rep of the product, i.e. $\,g * h = (g h\,\ {\rm mod}\,\ f).\,$ For example, in your ring $\,\Bbb Z[x]/(x^2\!+1)\,$ our reps are all $\, a+bx,\,$ for all $\,a,b\in \Bbb Z,\,$ with product $(a\!+\!bx) * (c\!+\!dx)\,$ being
$$\begin{eqnarray} {\rm mod}\,\ x^2\!+1\!:\ \  (a\!+\!bx)\,(c\!+\!dx) \,&=&\, ac + \color{#c00}{bd\,x^2}\! &+& (ad\!+\!bc)\,x \\ \,&\equiv&\, ac \color{#c00}{- bd} &+& (ad\!+\!bc)\,x,\ \ {\rm by}\ \ \color{#c00}{x^2\equiv -1}\\
\Rightarrow \ \ (a\!+\!bx)*(c\!+\!dx) \,&=&\,  ac-bd &+& (ad\!+\!bc)\,x\\
\end{eqnarray}$$
This is just the usual rule for multiplication of complex numbers, once we rename $\,x\,$ to $\:i.\,$
This normal form rewriting using the polynomial division algorithm  generalizes to multivariate rings over nice coefficient rings (e.g. fields, Euclidean domains) - see the Gröbner basis algorithm.
A: In $\mathbb{Z}[x]/(x^2+1)$ you can simply calculate as in $\mathbb{Z}[x]$ on representants of equivalence classes and then, if you need it, reduce them applying polynomial division by $x^2+1$ and keeping the remainder. The only "complicated" operation is to check if two elements $p(x)$ and $q(x)$ and  are equal, for which you must show (again using polynomial division) that
$$p(x)-q(x)\equiv 0\mod{x^2+1}$$
