extended Euclidean (xgcd) in quadratic integer rings Given a discriminant $D < 0$, I have the quadratic imaginary field $\mathbb{K} := \mathbb{Q}(\sqrt{D})$. And the quadratic integer ring is given by
$\mathcal{O} = \mathbb{Z} + \mathbb{Z} \frac{D + \sqrt{D}}{2}$.
For $a,b \in \mathcal{O}$, is it possible to calculate some numbers $p,q \in \mathcal{O}$ such that $ap + bq = d$ where $d$ is a divisor of $a$ and $b$?
$d$ must not be the greatest common divisor for my application, although I guess it would be? For some norm? (I'm not that much into this area.)
I was trying to generalize the extended Euclidean algorithm but I wasn't sure how to do division with remainder.
A bit more generic, where I need that: Given a matrix $M \in \operatorname{Sp}_2(\mathbb{K})$, I want to find $\gamma \in \operatorname{Sp}_2(\mathcal{O})$, $R \in \operatorname{Sp}_2(\mathbb{K})$ such that $M = \gamma \cdot R$ and I want the left lower $2 \times 2$ matrix of $R$ to be zero. In my construction, I heavily depend on the extended Euclidean algorithm.
 A: Given $a,b \in \mathcal{O}$, suppose that we can always find $x,y \in \mathcal{O}$ such that
$$ax+by=d,$$
with $d$ is a common divisor to $a$ and $b$.  If $d'$ is another common divisor, then $d' \mid (ax+by)$, hence $d'$ divides $d$.  Thus $d$ is a greatest common divisor (GCD) for $a$ and $b$.  In particular, $\mathcal{O}$ is a GCD-domain.
A GCD-domain is a (unique factorization domain) UFD if and only if it satisfies the ascending chain condition on principal ideals.  This chain condition holds for rings of integers, because such rings are Noetherian.  Thus it follows that $\mathcal{O}$ is a UFD.
For $\mathcal{O}$ the ring of integers in an imaginary quadratic field, unique factorization has been widely studied.  As a result of the Class Number Problem, we know that
$$-1,-2,-3,-7,-11,-19,-43,-67,-163$$
are the unique negative integers $d$ such that $\mathbb{Q}(\sqrt{d})$ generates a UFD, which answers your question negatively.
In general, if you wanted to classify $a,b \in \mathcal{O}$ such that we can find a GCD for $a,b$, I imagine that you would want to measure the degree to which unique factorization fails (i.e. over which primes).  This is measured, in some sense, by the class number, which is where I would look next.
Edit: You mentioned that this question arose in an attempt to generalize the Euclidean algorithm on $\mathbb{Z}$.  It should be noted that there exist GCD-domains that are not Euclidean domains (i.e. domains for which there exist analogues of the Euclidean algorithm).  These are not necessarily exotic, either: the integers $−19, −43, −67, −163$ from before give rise to PIDs (hence GCD-domains) that are not Euclidean domains.
