Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

This is completely constructive. Given elements $a, b \in O_K$, the ring of integers in some number field, let $A = (a,b)$ denote the ideal generated by these elements. Compute the class number $h$ of $K$ (or, if you want, the order you are working in), compute a generator $c$ with $A^h = (c)$, and set $L = K(\gamma)$ with $\gamma = \sqrt[h]{c}$. Then $A$ becomes principal in $L$, and computing the coefficients $ax + by = \gamma$ is linear algebra (this should be in Cohen's books).

share|improve this answer
    
Do you perhaps mean "compute a generator $c$ with $A^h = (c)$"? –  David Loeffler Dec 29 '10 at 10:46
    
David: yes, thanks! –  Franz Lemmermeyer Dec 29 '10 at 11:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.