# 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.

-

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.

-
In case it is an Euclidean domain, how would an implementation of the extended Euclidean algorithm look like? I mostly wonder about how to define/implement the division with remainder. -- Also, why would the non-Euclidean but UFD fail there? -- Is it easy to give an example where you cannot find $x,y$ in a non-UFD? – Albert May 13 '13 at 8:56
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. – Albert May 13 '13 at 9:05
If you have a UFD, you can quickly find GCD by computing the explicit factorizations of each term. In cases where you have a non-Euclidean UFD, it just means that there is no Euclidean algorithm that can be used find GCD (not that there isn't a GCD). In Euclidean integer rings, the Euclidean algorithm is typically given by minimizing successive norms. A good example of this is in the Gaussian integers (the whole process looks very geometric). – A Walker May 13 '13 at 17:13