Proving the kernel of $\phi: \mathbb{Z}[x] \to \mathbb{Z}[i],\ p(x) \mapsto p(i)$ is the ideal generated by $(x^2+1)$ There are a few posts about proving that $\mathbb{Z}[x]/(x^2+1)\simeq \mathbb{Z}[i]$. For example, in this post, the answer requires that we convice ourselves that kernel of the map is $(x^2+1)$. I use this notation for the ideal generated by $x^2+1$. So I am trying to make a complete proof that this.
As in the title, we define the homomorphism as follows. It is surjective since $bx+a \mapsto a+bi$ for any $a,b\in \mathbb{Z}$.
$$\phi: \mathbb{Z}[x] \to \mathbb{Z}[i],\ p(x) \mapsto p(i)$$
We can see that if $p(x) \in (x^2+1)$, then $p(x) = q(x)(x^2+1)$ for some $q(x) \in \mathbb{Z}[x]$. 
$$\phi(p(x))=\phi(q(x))\phi(x^2+1)=\phi(q(x))(i^2+1)=0$$
The harder part is to show that $\phi(p(x)) \ne 0$ when $p(x) \in \mathbb{Z}[x] \setminus (x^2+1)$, i.e., when $p(x)$ is not a multiple of $x^2+1$.
This is where I am having trouble. Since $\mathbb{Z}[x]$ is not a Euclidean domain, I don't have an explicit form for representing $p(x)=q(x)(x^2+1)+r(x)$, which I thought would be nice, but can't use here. 
Updated Attempted Answer
After looking back through my notes, $\mathbb{Z}[x]$ is a unique factorization domain because $\mathbb{Z}$ is as well. This means that any polynomial, $p(x)$, in $\mathbb{Z}[x]$ can be factored into a product of irreducible elements, $q_i(x)$.
$$p(x)=q_1(x)q_2(x)...q_n(x)$$
I can show by brute force that $x^2+1$ is irreducible in $\mathbb{Z}[x]$. This means that
$$p(x)\in(x^2+1) \iff q_k(x)=x^2+1$$
for some $k \in {1,...,n}$.
I am still having trouble pulling the last bit together, that when $(x^2+1)$ is not a factor of $p(x)$, then this needs to imply that $\phi(p(x))\ne 0$.
 A: By the fundamental theorem of algebra every polynomial $p$ can be written as $p(x)=c \prod (x-a_l)$. So if $p(x) \in \mathbb{R}[x] \supset \mathbb{Z}[x]$, then $p(i)=0$ if and only if $a_j=i$ for some $j$. Now since $0=\overline{p(i)} = p(\overline{i})$, where $\overline{a+ib} = a-ib$ denotes the complex conjugation in $\mathbb{C}$, we also have $a_k=-i$ for $k \neq j$ (because $\deg(p) \geq 2$). Thus $x^2+1$ divides $p$ and hence $p(i)=0$ if and only if $x^2+1$ is a divisor of $p(x)$. 

$\textbf{Update:}$ I think I have figured out what your real problem is now. I will explain what is meant by @Jyrki Lahtonen in the comments.
  You can also write $p(x) \in \mathbb{Z}[x]$ as $p(x) = \sum\limits_{k =0}^n p_k x^k$ with $p_k \in \mathbb{Z}$. Now from what we have seen before $p(i) = 0$ if and only if $x^2+1$ divides $p(x)$ in $\mathbb{R}[x]$. But then the euclidean algorithm in $\mathbb{R}[x]$ is valid for $p(x)$, that is $p(x) = (x^2+1)q(x)$ for $q(x) \in \mathbb{R}[x]$, right? Now note, that 
  \begin{eqnarray}
\sum\limits_{k=0}^n p_k x^k \colon (x^2+1) = p_n x^{n-2} + p_{n-1}x^{n-3} + (p_{n-2}-p_{n})x^{n-4} + ... = q(x)
\end{eqnarray}
  So we see, if we carry on with that division, that all coefficients of $q(x)$ are generated by subtracting or summing up some coefficients $p_j$ of $p(x)$. Since all $p_j \in \mathbb{Z}$ by assumption, we deduce, that $q(x) \in \mathbb{Z}[x]$. Thus we have proven
  \begin{eqnarray}
p(x) \in \ker(\phi) \iff p(i) = 0 \iff p(x) \in (x^2+1)
\end{eqnarray}
  and therefore $\ker(\phi) = (x^2+1)$.

