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 = (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).

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