We see the following in an answer to This Question : (mangled by me for my purposes, all errors my fault)

Dedekind stated (in 1871) that the ring of algebraic integers is a Bezout Domain. He calls it an important but difficult theorem, and only presents it as an easy corollary after he has developed all the theory, including (if memory serves) finiteness of the class number.

That is: Given any algebraic integers $a$ and $b$, there is a common divisor $d$ which is a linear combination of $a$ and $b$. Even more specifically, there exist algebraic integers $x,y,d,a'$ and $b'$ such that $ax+by=d$ $a=da'$ and $b=db'$. (So the common divisor $d$ is a greatest common divisor of $a$ and $b$ in that any common divisor of $a$ and $b$ also divides $d$.)

My question is: How constructively can this be established?

Is there a satisfying algorithm which given algebraic integers $a$ and $b$ produces algebraic integers $x$ and $y$ such that (the algebraic integer) $d=ax+by$ is a common divisor of $a$ and $b$?

I hasten to add that of course I know that what works in Euclidean Domains won't work here. The question above is the one I really want the answer to, but I'll throw in the following (which might be very easy)

• Is the answer yes at least for the special case that $a$ is a rational integer and $b$ is a root of a monic quadratic equation?

• Can a bound be given for the degree of the minimal polynomials of $x$ and $y$ (and/or $d$) in terms of those for $a$ and $b$? (That is, can the statement be strengthened to something like: "there exist $x,y,d$ all with degree no larger than $\deg(a)\deg(b)$ such that ...")

I remember that I once found a good $x$ and $y$ for $a=2$ and $b=1+\sqrt{-5}$ and that it involved cube roots of unity (if I recall correctly). I'm sure that that example is well known, but I did it by a very hit and miss process and can't recreate the answer on the spot.

We see the following in an answer to This Question : (mangled by me for my purposes, all errors my fault)

Dedekind stated (in 1871) that the ring of algebraic integers is a Bezout Domain. He calls it an important but difficult theorem, and only presents it as an easy corollary after he has developed all the theory, including (if memory serves) finiteness of the class number.

That is: Given any algebraic integers $a$ and $b$, there is a common divisor $d$ which is a linear combination of $a$ and $b$. Even more specifically, there exist algebraic integers $x,y,d,a'$ and $b'$ such that $ax+by=d$ $a=da'$ and $b=db'$. (So the common divisor $d$ is a greatest common divisor of $a$ and $b$ in that any common divisor of $a$ and $b$ also divides $d$.)

My question is: How constructively can this be established?

Is there a satisfying algorithm which given algebraic integers $a$ and $b$ produces algebraic integers $x$ and $y$ such that (the algebraic integer) $d=ax+by$ is a common divisor of $a$ and $b$?

I hasten to add that of course I know that what works in Euclidean Domains won't work here. The question above is the one I really want the answer to, but I'll throw in the following (which might be very easy)

• Is the answer yes at least for the special case that $a$ is a rational integer and $b$ is a root of a monic quadratic equation?

• Can a bound be given for the degree of the minimal polynomials of $x$ and $y$ (and/or $d$) in terms of those for $a$ and $b$? (That is, can the statement be strengthened to something like: "there exist $x,y,d$ all with degree no larger than $\deg(a)\deg(b)$ such that ...")

I remember that I once found a good $x$ and $y$ for $a=2$ and $b=1+\sqrt{-5}$ and that it involved cube roots of unity (if I recall correctly). I'm sure that that example is well known, but I did it by a very hit and miss process and can't recreate the answer on the spot.