Constructive Bezout cofactors in the ring of algebraic integers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T16:12:04Z http://mathoverflow.net/feeds/question/50634 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50634/constructive-bezout-cofactors-in-the-ring-of-algebraic-integers Constructive Bezout cofactors in the ring of algebraic integers Aaron Meyerowitz 2010-12-29T08:39:37Z 2010-12-29T11:03:00Z <p>We see the following in an answer to <a href="http://mathoverflow.net/questions/50557/-" rel="nofollow">This Question</a> : (mangled by me for my purposes, all errors my fault)</p> <hr> <p>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.</p> <hr> <p>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 <em>greatest</em> common divisor of $a$ and $b$ in that any common divisor of $a$ and $b$ also divides $d$.)</p> <p>My question is: How constructively can this be established?</p> <blockquote> <p>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$?</p> </blockquote> <p>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)</p> <ul> <li><p>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? </p></li> <li><p>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 ...")</p></li> </ul> <p>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. </p> http://mathoverflow.net/questions/50634/constructive-bezout-cofactors-in-the-ring-of-algebraic-integers/50642#50642 Answer by Franz Lemmermeyer for Constructive Bezout cofactors in the ring of algebraic integers Franz Lemmermeyer 2010-12-29T10:30:38Z 2010-12-29T11:03:00Z <p>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).</p>