Quotient ring of Gaussian integers $\mathbb{Z}[i]/(a+bi)$ when $a$ and $b$ are NOT coprime 
The isomorphism $\mathbb{Z}[i]/(a+bi) \cong \Bbb Z/(a^2+b^2)\Bbb Z$ is well-known, when the integers $a$ and $b$ are coprime. But what happens when they are not coprime, say $(a,b)=d>1$? 


— For instance if $p$ is prime (which is not coprime with $0$) then
$$\mathbb{Z}[i]/(p) \cong \mathbb{F}_p[X]/(X^2+1) \cong
\begin{cases}
\mathbb{F}_{p^2} &\text{if } p \equiv 3 \pmod 4\\
\mathbb{F}_{p} \times \mathbb{F}_{p} &\text{if } p \equiv 1 \pmod 4
\end{cases}$$
(because $-1$ is a square mod $p$ iff $(-1)^{(p-1)/2}=1$).
— More generally, if $n=p_1^{r_1} \cdots p_m^{r_m} \in \Bbb N$, then 
each pair of integers $p_j^{r_j}$ are coprime, so that by CRT we get
$$\mathbb{Z}[i]/(n) \cong \mathbb{Z}[i]/(p_1^{r_1}) \times \cdots \times \mathbb{Z}[i]/(p_m^{r_m})$$
I was not sure how to find the structure of $\mathbb{Z}[i]/(p^{r}) \cong (\Bbb Z/p^r \Bbb Z)[X] \,/\, (X^2+1)$ when $p$ is prime and $r>1$.
— Even more generally, in order to determine the structure of $\mathbb{Z}[i]/(a+bi)$ with $a+bi=d(x+iy)$ and $(x,y)=1$, we could try to use the CRT, provided that $d$ is coprime with $x+iy$ in $\Bbb Z[i]$. But this is not always true: for $d=13$ and $x+iy=2+3i$, we can't find Gauss integers $u$ and $v$ such that $du + (x+iy)v=1$, because this would mean that $(2+3i)[(2-3i)u+v]=1$, i.e. $2+3i$ is a unit in $\Bbb Z[i]$ which is not because its norm is $13 \neq ±1$.
— I was not able to go further. I recall that my general question is to known what $\mathbb{Z}[i]/(a+bi)$ is isomorphic to, when $a$ and $b$ are integers which are not coprime (for instance $a=p^r,b=0$ or $d=(a,b) = a^2+b^2>1$).
Thank you for your help!
 A: The best approach is to recall that $\mathbb{Z}[i]$ is a PID (Principal Ideal Domain), which is in fact an Euclidean domain with respect to its usual norm.
Once you notice this, you will realize that your approach using the Chinese Remainder Theorem is the correct one. The only problem is that you are factoring over $\mathbb{Z}$ instead that over $\mathbb{Z}[i]$. In this way, take $z\in\mathbb{Z}[i]$, factor it over $\mathbb{Z}[i]$ as $\prod q_k^{r_k}$ and you will obtain by the CRT that
$$\mathbb{Z}[i]/(z)\cong \prod_k\mathbb{Z}[i]/(q_k^{r_k})$$For example, in your example with $13(2+3i)$, write it as $(2+3i)^2(2-3i)$ and so you obtain
$$\mathbb{Z}[i]/(13(2+3i))\cong \mathbb{Z}[i]/(2+3i)^2\times \mathbb{Z}[i]/(2-3i)$$
Now, the only problem is studying which are the primes of $\mathbb{Z}[i]$ and determining the structure of $\mathbb{Z}[i]/(q^r)$ for $q$ prime in $\mathbb{Z}[i]$. The first question is can be answered using the fact that $z$ is prime in $\mathbb{Z}[i]$ iff $\mathbb{Z}[i]/(z)$ is a field (you have worked which primes of $\mathbb{Z}$ are primes of $\mathbb{Z}[i]$ without noticing and I let the proof to you), so we obtain:

The primes of $\mathbb{Z}[i]$ are of the form:
  
  
*
  
*$(1+i)$. Up to multiplication by units, $1+i$ is the only prime associated to $2$. 
  
*$p\in \mathbb{Z}$ prime integer with $p \equiv 3$ (mod 4). Up to multiplication by units, $p$ is the only prime of this form for a
  given integer prime $p \equiv 3$ (mod 4).
  
*$q=(x+iy)\in\mathbb{Z}[i]$ with $q\overline{q}$ prime integer. Up to multiplication by units, $q$ and $\overline{q}=(x-iy)$ are the only
  primes of this form for a given integer prime $q\overline{q}\equiv 1$
  (mod 4).
  

Once this is known, one should determine the structure of $\mathbb{Z}[i]/(q^n)$ for each one of these primes. We only have to distinguish three cases (we just use the the isomorphism theorems):

  
*
  
*$q=1+i$. When $r=2s$ is even, we reduce to $$\mathbb{Z}/(2^s)[X]/(X^2+1)$$ that can be realized as the matrix
  subalgebra of $M_2(\mathbb{Z}/(2^s))$ given by
  $$\mathbb{Z}/(2^s)\left[\begin{pmatrix}0&-1\\1&0\end{pmatrix}\right]$$
  Note that for $s=1$, this is just $\mathbb{Z}/(4)$. When $r=2s-1$ is
  odd, we reduce to $$\mathbb{Z}/(2^s)[X]/(X^2+1,2^{s-1}(X+1))$$ which
  the better realization I can think of is a quotient of the subalgebra
  of $M_2(\mathbb{Z}/(2^s))$
$$\mathbb{Z}/(2^s)\left[\begin{pmatrix}0&-1\\0&0\end{pmatrix}\right]$$
  by the ideal generate by
  $$\begin{pmatrix}2^{s-1}&2^{s-1}\\2^{s-1}&2^{s-1}\end{pmatrix}$$
  
*$q=p$ is an integer prime. Then as noted by you, we reduce to $$\mathbb{Z}/(p^r)[X]/(X^2+1)$$ A concrete realization can be obtained
  by considering the matrix subalgebra of $M_2(\mathbb{Z}/(p^r))$ given
  by
  $$\mathbb{Z}/(p^r)\left[\begin{pmatrix}0&-1\\1&0\end{pmatrix}\right]$$
  
*$q=a+bi$ is not an integer prime. In this case, it should be noted that for $(a+bi)^n=a_n+b_ni$, $a_n$ and $b_n$ should be coprime
  because otherwise it would be divisible by a prime non equivalent to
  $a+bi$ violating the unique factorization. Hence
  $$\mathbb{Z}[i]/(q^r)\cong \mathbb{Z}/((q\overline{q})^r)$$ in this
  case by your cited result.
  

This settles the question in general and in a completely satisfactory way in many case. In your considered example, we obtain $\mathbb{Z}/(13)\times \mathbb{Z}/(13^2)$. However, maybe there are better presentations for some of the above cases. In any case, the strategy I give works for any PID.
A: Question: "Thank you for your help!"
Answer: One of the above isomorphisms may be made explicit. One wants an explicit isomorphism of rings
$$\mathbb{Z}[i]/(a+ib) \cong \mathbb{Z}/(a^2+b^2).$$
Construction: Let $w:=a+ib \in R:=\mathbb{Z}[i]$ with $(a,b)=1, ua+vb=1$ and let $z:=va-ub$. Let $N(w):=a^2+b^2$ and let $B:=\mathbb{Z}/(N(w))$ and $A:=R/(a+ib)$.
Define the map
$$\varphi: A \rightarrow B$$
by $\varphi(m+in):=m-zn$. Let $\psi: B \rightarrow A$ be the canonical map.
Lemma. The maps $\varphi$ and $\psi$ are well defined isomorphisms.
Proof: You may check the following:
$$\varphi(a+ib)=u(a^2+b^2)=0$$
and
$$\varphi(i^2+1)=(u^2+v^2)(a^2+b^2)=0.$$
Moreover
$$\psi(\varphi(m+in))=m-zn$$
and
$m+in-(m-zn)=(i+z)n=iu(a+ib)=0$ in $A$.
Hence the maps $\varphi$ and $\psi$ are inverses of each other.
Example: It is fun to verify you get an isomorphism for "large" numbers $a,b$. Such a non trivial isomorphism is instructive for students wanting to learn about ideals, equivalence relations etc.
Verify that $\mathbb{Z}[i]/(5+11i) \cong \mathbb{Z}/(146)$.
We see that $(-2)5+(1)11=11-10=1$, and we let $u:=-2, v:=1$ and $z:=5-(-2)11=27$. We get the map
$$\varphi: \mathbb{Z}[i]/(5+11i) \cong \mathbb{Z}/(146)$$
defined by
$$\varphi(i):=-z=-27.$$
It follows $\phi(5+11i)=5+11(-27)=-292=(-2)146$ and
$$\phi(i^2+1)=(-27)^2+1=730=(4)146\cong 0 (mod(146)).$$
The map is well defined and an isomorphism: If $\psi$ is the inverse map you get for any $m+in$ the following calculation:
$$\psi( \varphi(m+in)):=\psi(m+27n)\cong m-27n(mod(5+11i))$$
and you get the following:
$$m+in-(m-27n)=(i+27)n(mod(5+11i)).$$
You get
$$i+27=i+(2)11+5 =i+2(5i)+5\cong 5+11i\cong 0 (mod(5+11i)).$$
Hence $\psi \circ \varphi = Id$.  You check that $\varphi \circ \psi=Id$ and it follows the map $\varphi$ is an isomorphism of rings.
